# how many PLL time attack orders return to solved state?



## whauk (Apr 26, 2011)

title says it all.
you are allowed to do rotations/AUFs in between. (otherwise it would make not much sense)
i was not even able to find an approach for this problem. i hope you come up with some solutions 



additional (easier?) problem: we do not use only PLLs but all possible states after OLL. (288 if i am not mistaken)


----------



## RyanReese09 (Apr 26, 2011)

Too many variables to take into account.


----------



## MaeLSTRoM (Apr 26, 2011)

All of them? If you can AUF, then you would always be able to plan out an order that returns to the starting position. At least I think so.


----------



## DavidWoner (Apr 26, 2011)

A lot, since you can insert cancelling pairs of algs (Gs, Us, As, NNH, TFH, etc etc) in so many places and so many orders.


----------



## MaeLSTRoM (Apr 26, 2011)

OK, let's flip the question, can anyone find one that *doesn't* work?


----------



## Lucas Garron (Apr 26, 2011)

Interesting problem. I suspect the answer is a high proportion, if not all. I'm too lazy/busy to DP it up right now, though.


----------



## vcuber13 (Apr 26, 2011)

thered be 21! combinations right?
that would be too many to count


----------



## Stefan (Apr 26, 2011)

vcuber13 said:


> thered be 21! combinations right?



No, more. Because of the AUFs/angles.



vcuber13 said:


> that would be too many to count



No, not for a computer.


----------



## vcuber13 (Apr 26, 2011)

Stefan said:


> No, more. Because of the AUFs/angles.


well an alg could start with a U or whatever changing the AUf or angle. 



Stefan said:


> No, not for a computer.


it would still take a while to do 10^19 combinations


----------



## Stefan (Apr 26, 2011)

vcuber13 said:


> well an alg could start with a U or whatever changing the AUf or angle.



Uh... your point is?

Well ok, there are at most 21! different permutations, your "combinations" threw me off a bit. Sorry about that.



vcuber13 said:


> it would still take a while to do 10^19 combinations



Not more than a few seconds if done right, I think. Of course they shouldn't be counted one by one, but rather using DP (dynamic programming) like Lucas said.


----------



## deathbypapercutz (Apr 26, 2011)

I'm trying to write something, mostly for my own educational purposes. But I am by no means a good programmer. Or even a programmer at all. So I could use some help.

I want to represent the edges and corners as indices 1 through 8, and each PLL as a permutation of these indices, which I'd probably represent with one-line notation implemented as lists. The recursive method would look something like

permute(list of PLLs already applied, current permutation, list of PLLs not yet applied).

It would go through the list of PLLs not yet applied, apply it to the current permutation, add it to the list of PLLs already applied, and call permute on each one. I'd memoize based on current permutation and list of PLLs not yet applied. The list of PLLs already applied would just be for reference at the end. So that's around 8! * 2^21 subcases (probably a few factors less than that, since not all 8! permutations of corners and edges can be attained). Correct? Viable?

[EDIT: I forgot that I'd also have to account for AUFs in between PLLs. But that's my general intent/idea.]


----------



## vcuber13 (Apr 26, 2011)

Stefan said:


> Uh... your point is?
> 
> Well ok, there are at most 21! different permutations, your "combinations" threw me off a bit. Sorry about that.



actually it may be more, since there 21! permutations for just the plls themselves TFGGHV etc but most of them have 4 reflections. so if VTGG were the only plls it would be 4*4*3*4*2*4*1*4 or no?



deathbypapercutz said:


> So that's around 8! * 2^21 subcases (probably a few factors less than that, since not all 8! permutations of corners and edges can be attained). Correct? Viable?


 
it wouldnt be 8! it would be 2*4! and where is the 2^21 coming from?


----------



## Stefan (Apr 26, 2011)

deathbypapercutz said:


> [EDIT: I forgot that I'd also have to account for AUFs in between PLLs. But that's my general intent/idea.]



That's my general plan as well, but those pesky AUFs give me trouble. Also, but just for fun: The PLLs don't have to be applied to just one layer. You could apply some to U and some to R and still end up with a solved cube. That might provide even more possibilities. But I don't want to go there 



vcuber13 said:


> actually it may be more, since there 21! permutations for just the plls themselves TFGGHV etc but most of them have 4 reflections. so if VTGG were the only plls it would be 4*4*3*4*2*4*1*4 or no?



Yeah, that's what I meant.



vcuber13 said:


> it wouldnt be 8! it would be 2*4!



It's not 2*4! and not even 4!^2 but rather 4!^2 / 2 (because of parity) or 4!^2 / (2*4) (with normalization).



vcuber13 said:


> where is the 2^21 coming from?



The subsets of PLLs already applied.


----------



## vcuber13 (Apr 26, 2011)

Stefan said:


> It's not 2*4! and not even 4!^2 but rather 4!^2 / 2 (because of parity) or 4!^2 / (2*4) (with normalization).


woulnt it be 4! for the corners * 4! for the edges (and then divide by 2 for parity and /4 for mirrors)?

edit: ahh, for some reason i thought 4!*4! was 4!*2 :fp :fp


----------



## Stefan (Apr 26, 2011)

Not mirrors (because when talking about 21 PLLs, we're not considering mirroring) but AUFs.


----------



## qqwref (Apr 26, 2011)

Stefan said:


> That's my general plan as well, but those pesky AUFs give me trouble. Also, but just for fun: The PLLs don't have to be applied to just one layer. You could apply some to U and some to R and still end up with a solved cube. That might provide even more possibilities. But I don't want to go there


It doesn't feel right to have a PLL attack that involves doing some PLLs on the wrong face. I think we should ignore this possibility.


----------



## Stefan (Apr 26, 2011)

Yeah, that's partly why I didn't want to go there. It's not just the fear of complexity 

Though I'd love to see a PLL attack that mid-way has F2L solved and all LL pieces misoriented (and ends up with the cube solved).


----------



## vcuber13 (Apr 26, 2011)

Stefan said:


> Not mirrors (because when talking about 21 PLLs, we're not considering mirroring) but AUFs.


 
for mirrors i meant that it is "unaufable"


----------



## deathbypapercutz (Apr 26, 2011)

Stefan said:


> It's not 2*4! and not even 4!^2 but rather 4!^2 / 2 (because of parity) or 4!^2 / (2*4) (with normalization).


 
Oh right. My bad.



deathbypapercutz said:


> [EDIT: I forgot that I'd also have to account for AUFs in between PLLs. But that's my general intent/idea.]



There are only four possibilities for AUFs (none, U, U', U2), so I'd probably just call permute four times for each possible next PLL.


----------



## Lucas Garron (Apr 26, 2011)

deathbypapercutz said:


> There are only four possibilities for AUFs (none, U, U', U2), so I'd probably just call permute four times for each possible next PLL.


I was just going to keep track of all 72 in equivalence classes; it's easier to build up "transition tables" for partial work and reduce over the PLLs or something. Maybe not, I'm just blabbing. Just be aware of Z, E, N, N, H.

(*Stop tempting me to go solve this right now.*)


----------



## cuBerBruce (Apr 27, 2011)

There was a similar thread awhile back where I posted Visual C++ source code in [post=536867]this post[/post] for a program that did something similar to what is being discussed in this thread. I note I only considered 13! letter orderings rather than full 21! orderings. But I posted source code so you can try to adapt it as you please.


----------



## Michiel van der Blonk (Apr 27, 2011)

maybe this helps: http://www.speedsolving.com/forum/showthread.php?27624-PLL-triplets

I never finished it completely, I lost interest. Sorry!


----------



## Stefan (Apr 29, 2011)

I now have doubts about the feasibility. At least it's not trivial. The AUFs are killing it.

I'd like to use dynamic programming with a table like this:
ways[SET][CASE] = number of ways to order the PLLs in the set SET and end up with case CASE

This would start with:
ways[NONE][SOLVED] = 1

Then fill the table from there and read the result from:
ways[ALL][SOLVED]

Here's my problem: Let's say
ways[{Aa,R,J,H}][H] = 23
ways[{Aa,R,J,H}][E] = 42

and I'd like to compute
ways[{Aa,R,J,H,T}][F]
and consider T as the last in the order.

Using T we can get to F from both H and E, so we should add their numbers to the new cell, right? Sadly not, as because of AUFs, *the same* order of {Aa,R,J,H} can lead to both H and E, so just adding them together we'd double count.



However, this still works to tell *whether* there is any way to use a set of PLLs to reach a case. And I've envisioned that as the main application anyway - starting your PLL attack some way you want, and have the program tell you whether you can get back to solved using the remaining PLLs (and perhaps show one or several possible ways). On the other hand, I suspect that with six or so left, it's always possible, and that's small enough to brute-force anyway.


----------



## crashdummy001 (Apr 29, 2011)

over 9000


----------

