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.