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

Submitted by silviu on Thu, 07/27/2006 - 17:07.

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.

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,829I 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.