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