# Rubik's cube can be solved in 38 quarter turns max

Silviu recently posted a result where he provides move sequences to solve all positions of the corners with an even corner permutation in 22 quarter turns or less without any net effect on the edges. This, combined with a result by Tomas Rokicki that the edges can be solved in 18 quarter turns or less, allowed Silviu to conclude that Rubik's cube can always be solved in 18+22 = 40 quarter turns or less. I have used a C++ program to verify Silviu's sequences do not exceed 22 quarter turns; and combined with applying "M-symmetry" and inverses to those sequences, correctly solve all even permutation and orientation possibilities for the corners with no net effect on the edges.

Looking at Rokicki's analysis further, one can see that there are relatively few positions in the edges-only case that require more than 16 quarter turns. For the cases of 16 or less quarter turns, the edges can be solved, and then the corners can be solved with Silviu's sequences, in no more than 38 quarter turns. Showing that the other cases in the edges-only analysis of more than 16 quarter turns can be solved in 38 quarter turns or less (including corners) would therefore mean that all positions of Rubik's cube can be solved in 38 quarter turns or less.

I have determined what the edges-only positions of distance larger than 16 must be, and have used a "fast" solving algorithm to solve all the possible cases of the corner configurations combined with those edge configurations. None of the positions was found to require more than 38 quarter turns. (Actually it solved only cases that are unique with respect to the symmetries of the cube, but that is sufficient.) This algorithm was designed to be very fast, but tends to average about 32 quarter turns for the lengths of the solutions it finds, much higher than good 2-phase solvers. However, it did in fact produce solutions of 38 or less for the edges-only antipode configurations, and 37 or less for the configurations that are at distance 17 in the edges-only analysis. I have produced text files with these solution sequences for these cases. (These are large files, total size about 1GB.) I therefore conclude that Rubik's can always be solved in 38 quarter turns or less.

Note that the edges-only analysis by Tom Rokicki indicates that there is a unique antipode. There are only four configurations of the edges with the degree of symmetry required for such uniqueness. From these choices it was found that the edge configuration of the antipode is that of Pons Asinorum composed with the superflip. I found a post in the speedsolvingrubikscube Yahoo group (http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/8310) that also confirms the antipode position.

For the positions at distance 17, Rokicki's analysis indicated 3 positions unique wrt M, the symmetry group of the cube. These correspond to 30 cube positions if symmetry is not considered. From the antipode, any of the twelve possible quarter turns results in getting to a distance 17 position, and these are all symmetrically equivalent to each other. That means there must be two other positions (unique wrt M) at distance 17 that are local maxima. These correspond to 30 - 12 = 18 positions in the full cube group. Since the number of full cube group positions for each of the two positions unique wrt M must equal a factor of 48, and the two numbers must add to 18, the possibilites were (2, 16) and (6, 12). I performed a search for edges-only odd permutation positions unique wrt M corresponding to these numbers of positions in the full cube group. I found the following number of such positions:

```           number of positions
elements     (unique wrt M)

2               0
6              96
12            3560
16            1900
```

Since no positions with two elements were found, the two positions must have 6 and 12 elements. I used a bidirectional search going distance 8 from these positions and distances out to 7 from the identity position. This showed that of these positions only three were not within a distance of 15 from the identity position. Since the have an odd edge permutation, they must be at distance 17. These positions can be reached with the following (non-optimal) sequences:

```R D2 L' B2 R' B2 R U2 F2 B2 L' F2 D2 R' D' R' B D L' U' R' U F' R' D'

L' D2 L' F2 R' L' B2 R B2 R2 U2 R' B2 R' B' D' L' U' F R B D'

F2 U D R2 L2 D' R2 U' B2 U L2 D' L2 F' B2 R' B D L B U F' U' B' U'
```

The third one is the position adjacent to the antipode.

So the above positions along with the antipode position, for all the necessary corner configurations, were solved as mentioned earlier. The tables below give the distribution in terms of solution lengths for the solutions my solver found. The important thing is that the antipode cases were all solved within 38 quarter turns and the others within 37 quarter turns.

```Pons Asinorum composed with superflip edge configuration

(Note: For this case, the data is for all 44,089,920
positions in the full cube group with this edge
configuration. To get a smaller result file, I've
redone this for just the positions unique wrt M with a
slightly improved version of my solver in terms of
average solution lengths, but I don't seem to have the
summary information available.)

solution
length       count
18            40
20           332
22          2846
24         22176
26        153416
28        963499
30       4656631
32      13817591
34      17408560
36       7064629
38           200
--------
44089920

R D2 L' B2 R' B2 R U2 F2 B2 L' F2 D2 R'
D' R' B D L' U' R' U F' R' D'
(local maximum in edges-only)

solution  distance
length
19           22
21          316
23         2708
25        20881
27       139100
29       746105
31      2252760
33      2069747
35       282204
37         1981
-------
5515824

L' D2 L' F2 R' L' B2 R B2 R2 U2 R' B2
R' B' D' L' U' F R B D'
(local maximum in edges-only)

17            4
19           43
21          603
23         5993
25        44784
27       301012
29      1574945
31      4605276
33      4033286
35       463677
37         1929
-------
11031552

F2 U D R2 L2 D' R2 U' B2 U L2 D' L2 F'
B2 R' B D L B U F' U' B' U'

17           12
19           95
21          880
23         6935
25        49919
27       327748
29      1708017
31      4765543
33      3794362
35       369520
37          769
-------
11023800
```

Thanks to Silviu for his help and suggestions.

- Bruce Norskog

## Comment viewing options

### a confirmation of 39 quarter turns as an upper bound

Silviu has informed me that he has verified my set of solutions for covering all the cases for the Pons Asinorum composed with superflip edge configuration. This provides one independent confirmation that all "legal" cube positions can be solved in 39 quarter turns or less. (I have confirmed Silviu's solutions of 22 quarter turns or less for the identity edge configuration, and he has confirmed my solutions of 38 quarter turns or less for the Pons Asinorum composed with superflip edge configuration.) I do not have independent confirmation at this time for the additional cases needed to confirm 38 as an upper bound.

Well, for the record, I am not personally aware if there is an independent verification of the edges-only analysis done by Tomas Rokicki. The claims being made of 40, 39, or 38 as an upper bound depend upon that analysis being correct. I may attempt to perform an independent verification of that analysis myself.

- Bruce Norskog

### confirmation of 38 quarter turns as an upper bound

Silviu has confirmed my solutions for all the cube positions having the edge configurations corresponding to the two local maximum positions of distance 17 in the edges-only (technically edges plus centers) analysis that was done by Tomas Rokicki. There is one other position (unique wrt M) in that edges-only analysis that is not a local maxima. This position is one quarter turn away from the antipode position, of course. Silviu and I have also each determined that all cube positions with the edge configuration corresponding to the antipode of the same edges-only analysis can all be solved in 36 quarter turns are less. (There were just 7 cases where my original solutions were of length 38, and we found shorter solutions for these cases.) Thus, the cube positions with the edge configuration corresponding to this non-local-maximum position of the edges-only analysis can all be solved in no more than 37 quarter turns (since we could make one quarter turn to reach the antipode position for the edges, and then still solve in 36 quarter turns).

I have also completed an independent analysis to verify the results of Tomas Rokicki's analysis for the edges in the quarter-turn metric. I have verified the number of cube positions is correct for each distance, and also the number of cube positions that are unique wrt M for each distance. In particular, I have verified the 3 positions (unique wrt M) of distance 17 in the edges only analysis that I found previously, are in fact the only positions of that distance. I should soon also have a verification of the number of positions unique wrt M+inv for each distance.

In summary, I have verified Tomas Rokicki's analysis of edges-only in the quarter-turn metric. I have also verified Silviu's solutions of 22 quarter turns maximum for solving corners without affecting edges. And Silviu has confirmed my results that all cube positions with an edge configuration corresponding to those of distance 17 or higher in the edges-only analysis can be solved in 38 (actually 37) quarter turns or less. Thus, we have at least one independent confirmation of each of the analyses we have used in showing that Rubik's cube can always be solved in 38 quarter turns or less.

I have also determined the 750 positions (unique wrt M) of distance 16 in the edges-only analysis. Solving all cube positions with these edge configurations could be used to further reduce the upper bound for the quarter-turn metric to 37, but that has not been done yet.

- Bruce Norskog