Home »

New optimal solutions for an important group

Submitted by silviu on Wed, 03/15/2006 - 03:32.
I have computed optimal solutions for every element in the group <U,D,L^2,R^2,F^2,B^2>. For this task I made some minor modifications to Reid's solver. I would like to thank him for sharing it. 

   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.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Tom encouraged me to post som

Submitted by silviu on Thu, 03/16/2006 - 12:18.
Tom encouraged me to post some more details about this.
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.
» login or register to post comments

How did you manage to do this

Submitted by Herbert Kociemba on Thu, 03/16/2006 - 08:42.
How did you manage to do this? You surely did not run the optimal solver over each of these positions one by one. But I also do not see how for example a breadth first search could be done here.
» login or register to post comments

In order to explain it in a e

Submitted by silviu on Thu, 03/16/2006 - 11:24.
In order to explain it in a easy way:

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.
» login or register to post comments

It's a simple coset search.

Submitted by rokicki on Thu, 03/16/2006 - 11:11.
It's a simple coset search. He simply uses a pruning table (in this case the standard U/D/F2/B2/R2/L2 table) to guide an iterative deepening search; for each solution found, he indexes the whole-cube position and looks it up in a big bit vector; if this is the first time that whole-cube solution was found, that's an optimal solution for this cube. It's the same approach I used for my edge space searches, only much larger (solving many more cubes at a time) and much faster (because this pruning table is much faster than the whole edgespace pruning table).

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.
» login or register to post comments

This is absolutely amazing; o

Submitted by rokicki on Wed, 03/15/2006 - 17:08.
This is absolutely amazing; over 19B cubes optimally solved. That's a pretty big fraction of the entire cube space! I think this is the first time such a big chunk has been explored (at least, a chunk that doesn't implicitly exclude deep cubes).
» login or register to post comments

the fraction of cube space

Submitted by Bruce Norskog on Thu, 03/16/2006 - 18:31.

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.

» login or register to post comments

Interestingly, even if you le

Submitted by rokicki on Fri, 03/24/2006 - 11:01.
Interestingly, even if you leave the subgroup, in the face turn metric, there are still positions that require 18f*.
» login or register to post comments

Mark I have submitted this bu

Submitted by silviu on Wed, 03/15/2006 - 03:37.
Mark I have submitted this but can not change it. Could you replace "in the group" with "in the group < U,D,L^2,F^2,B^2,R^2 >." Thanks in advance.
» login or register to post comments

Made a minor edit

Submitted by cubex on Wed, 03/15/2006 - 04:13.
I made a minor edit replacing the less than symbol and greater than symbol with their html equivalents. I don't think using "<" and ">" works too well without double quotes around them so perhaps using the html version is better. Everything after that looked a bit mangled but it looks ok now.
» login or register to post comments

Thank you for the improvement

Submitted by silviu on Wed, 03/15/2006 - 04:30.
Thank you for the improvement. I will keep that in mind.
» login or register to post comments