# New optimal solutions for an important group

0q 1 1q 4 2q 10 3q 36 4q 123 5q 368 6q 1,320 7q 4,800 8q 15,495 9q 54,016 10q 194,334 11q 656,752 12q 2,222,295 13q 7,814,000 14q 26,402,962 15q 89,183,776 16q 297,590,924 17q 929,624,528 18q 2,573,889,614 19q 5,506,671,444 20q 6,551,983,325 21q 3,219,955,376 22q 301,913,989 23q 249,300 24q 8 F R F R' L F R L' B L' F' B2 R L' F U2 R' B' L' B R' F (24q*, 22f)The 24q position is a local maxima so this table actually gives a simple proof for the fact that Rubik's cube is solvable in 36q max. I personally like the old proof better.

## Comment viewing options

### How did you manage to do this

### In order to explain it in a e

Let us now consider a standard optimal solver like Reid's. How does it work? Giving it an arbitrary position it finds out in which coset it is. Then he finds maneuvers that takes this coset to the identity coset. However this maneuvers need not to solve the position but they allways take the position into the target group H. This should be well known.

So actually what Reids solver does for each depth is that it finds all solutions that take the given position that we want to solve to the identity coset. Normally we stop when the maneuver is taken to identity itself.

Here we introduce a bit vector that registers all solutions to the identity coset and in this way we find for each depth each solution from the position in question to the identity coset. If we choose as position to solve the identity

(Reids solver will stop direct but we modify it so that it continues)

and let the solver run through all depths we get the above table.

To repeat all of this in other words the solver will then begin from identity and find all solutions of length 0 that takes the identity to the group H.

Next he finds all solutions of length 1 that takes the identity to the group H and so on.

And once a solution is found we mark in the bit vector the element in the group H in question.

### It's a simple coset search.

I'm jealous; I didn't think such an approach would complete in any reasonable amount of time. I'm hoping he posts more about this search here.

### This is absolutely amazing; o

### the fraction of cube space

As there are two other obvious subgroups isomorphic to this subgroup, I believe this effectively means approximately 3 times as many positions can be regarded as having been solved. That's about 58*10^9 out of the 43*10^18 positions. I believe it corresponds to about 600 million positions unique wrt M+inv (out of approx. 450*10^15). Either way, it's more than 10^-9 of cube space! Right?

Another note: the 24q* position is 16f* (U B2 U B2 D' F2 D L2 U F2 U' F2 U R2 F2 U') according to Cube Explorer (3.67). I'll note that almost all the positions in the subgroup can be solved in 16f or less without even leaving the subgroup, so I guess 16f* should not be surprising. (1575608 positions 17f and 1352 positions 18f, staying within the subgroup. This means solving using only U,U',U^2,D,D',D^2,L^2,R^2,F^2, and B^2. Optimal FTM solving would reduce these numbers further. The numbers are from a Michael Reid post on the old Cube-lovers mailing list.) The 24q* position has order 4, meaning that if you perform either the 24q* or 16f* sequence 4 times in succession, you get back to the starting position.

## Tom encouraged me to post som

First of all. I run as we both described up to depth 21. This took 130 hours on an 2.53Ghz AMD Opteron with 1Mb cache. 3x faster than a P4.

I listed all remaining odd positions i.e. depth 23,25,27...

I took each position multiplied it by either U2,L2,F2,B2,R2,D2. And if the new element took me out of the remaining odd set then this position had depth 23. This allowed me to find all depth 23 positions.

Than I continued in the same manner as Tom and I described with depth 22 but did not run it to completion. I run it until there where 476 even positions left. I took each position multiplied it by either U,D,U3,D3 and saw if it takes me to depth 23 if not then it must be depth 22. I was left with 5 pos unique M+inv that I run optimally.

And so the result.

the partial depth 22 took about 100 hours. So total runtime and all say 300 hours.