How to Compute Optimal Solutions for All 164,604,041,664 Symmetric Positions of Rubik's Cube

Using some new ideas, techniques, and computer programs, we have successfully found optimal solutions to all symmetric positions of Rubik's cube in the face turn metric (FTM). Furthermore we have maneuvers for 1,091,994 20f* (positions whose optimal solutions have 20 face turns) cubes and proven that there are no symmetric 21f* cubes. So if there are any cubes at depth 21 then these must be unsymmetrical. To the best of our knowledge, at the start of this investigation in January, only a few such positions were known (less than a dozen). Expressions for all these cubes can be found on Rokicki's home page http://tomas.rokicki.com/all20.txt.gz.

The symmetric cubes have been of great interest because the first high distance positions found are symmetric. Classification of these positions began with Michael Reid and continued with the work of Herbert Kociemba. In the past few months some newly developed techniques of computing certain groups have appeared, first published by the author in a preliminary form but independently used by Tomas Rokicki to compute cosets of the "group that fixes edges". Here we present a method of generalizing these techniques to a special class of groups. After that we compute the remaining symmetry groups. The idea of this method is using IDA* technique to search for all solutions to elements that lie in a given group. That is actually exactly what Michael Reid's solver does. However the solver ignores all solutions to elements in the target group except the one that we want to solve. Instead of ignoring this solutions we register them in a bit vector depth by depth and hence get optimal solutions for each element in the target group.

Several computations of this type has been presented on the cube forum by Rokicki and myself. This has enabled us to compute several optimal solutions per second comparing with the older solvers that gave a solution per hour at the best. Rokicki found a way to improve the search algorithm. His idea is to exclude from the search solutions that begins and ends with a move that lie in the target group. This solutions are computed instead by taking all solutions in the previous depths and multiply them by these moves. For certain groups such as ( U,D,F2,B2,L2,R2 ) this gives an imense speed up. For example this group can be computed about 300x faster then using IDA* only. We are also going to take advantage of this method for some of our computations.

To use this idea for an arbitrary target group complicates things because we don't have a general method to map the elements in the target group on numbers. This is needed in order to register them in a bit vector. Furthermore we need a method to map the cosets G/T where T is the target group on numbers. We present a simple solution to this problem by using the computer algebra GAP to do this work. This program will build for us the move tables and sym tables that are needed for the action on cosets. After that we read the move tables in a C program that builds the actual pruning.

In order to identify the elements of the target group we build a list in GAP with all elements in the target group restricted to corners respective edges. This list is divided in orientations and permutations. This lists can be used to compute an index in the bit vector. Actually the index is simply the position of the given element in this list. Some more discussions and computations of this type can be seen on the this forum.

This article is not yet finished and we only give a summary of the results: See Herbert Kociemba's home page for other interesting details.

	Group Ci

      0f              1  
      1f              0  
      2f              9  
      3f              0   
      4f             63    
      5f            120   
      6f            694   
      7f          2,562    
      8f         11,338  
      9f         44,853  
     10f        194,740  
     11f        788,992  
     12f      3,315,172  
     13f     13,445,694 
     14f     54,961,138 
     15f    271,122,047 
     16f  1,585,605,201 
     17f  9,134,397,172 
     18f 27,801,243,853 
     19f  6,999,321,491 
     20f        259,100
 
     Group C2(a)

     0f               1 
     1f               6  
     2f              15
     3f              72
     4f             343
     5f           1,060
     6f           4,570
     7f          17,960
     8f          60,136 
     9f         226,199 
    10f         805,260 
    11f       2,602,404 
    12f       9,295,556 
    13f      30,949,920 
    14f     101,692,042 
    15f     363,402,817 
    16f   1,333,918,995 
    17f   4,550,677,966 
    18f   7,774,262,733 
    19f   1,120,268,931 
    20f          51,094

    Group Cs(a)

     0f               1
     1f               4
     2f              13
     3f              48
     4f             159
     5f             464
     6f           1,554
     7f           4,758 
     8f          13,810 
     9f          40,353 
    10f         114,084 
    11f         324,496 
    12f       1,019,512 
    13f       4,128,898 
    14f      20,060,486 
    15f     103,107,447 
    16f     607,357,293 
    17f   3,601,456,840 
    18f  11,082,306,785 
    19f   2,925,751,099 
    20f         197,592 

    Group C2(b)

    0f                1 
    1f                0  
    2f                3  
    3f                0  
    4f                1  
    5f                0 
    6f               44  
    7f              180  
    8f              460  
    9f            1,587  
   10f            8,072  
   11f           28,146  
   12f          119,054  
   13f          473,702  
   14f        2,168,270  
   15f       12,440,909  
   16f       84,769,773  
   17f      548,185,762  
   18f    1,583,371,387  
   19f      316,458,701  
   20f           13,628  

   Group Cs(b)

    0f                1 
    1f                2  
    2f                1  
    3f                0  
    4f                1  
    5f                4  
    6f               24  
    7f               50  
    8f              126  
    9f              533  
   10f            1,956  
   11f            6,478  
   12f           25,130  
   13f          114,700  
   14f          546,558  
   15f        3,102,247  
   16f       19,703,503  
   17f      110,503,448  
   18f      252,385,203 
   19f       38,279,025  
   20f            4,290 

   Group C3 

    0f                1  
    1f                0  
    2f                0  
    3f                0  
    4f                0  
    5f                0  
    6f                1  
    7f                0  
    8f                4  
    9f               18 
   10f               28    
   11f               26
   12f              162 
   13f              288  
   14f            1,711  
   15f            8,924  
   16f           67,176  
   17f          481,063  
   18f        2,083,458  
   19f        1,133,447  
   20f            2,829  
  

   

I want to thank my advisor Gert Almkvist who inspired me to start working on the cube and provided me with the high speed computers on which all the computations have been done. I further want to thank Herbert Kociemba for help, support and inspiration throughout this project. I further want to thank Tomas Rokicki who guided and supported me throughout this work and for the many improvements he has done to this work. I also want to thank Michael Reid who shared his solver and I have used his program structure to make my own programs. Because I am not a C programmer this really was a lot of help. At last but not least I want to thank all the people that contributed to GAP development and made this computer algebra program possible.