# 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.

```
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.