Two-Phase-Algorithm and God's Algorithm

The algorithm which gives an optimal solution in the sense that there is no shorter solution is called God's algorithm. There are cube positions (for example the superflip which flips all 12 edges), which are known to have a shortest maneuver length of 20 moves to be solved. It is still an open problem if there are cube positions which require 21 moves or more with God's Algorithm.

I generated 1 million random cubes on a 3 GHz Pentium 4 PC, trying to find a cube which was not solvable within 20 moves with the Two-Phase-Algorithm. This cube then would be a test candidate for a position which would need at least 21 moves to be solved with God's Algorithm.

But the Two-Phase-Algorithm solved all generated random positions within 20 moves. More precisely, it solved about 30000 random cubes per hour and the final distribution of the maneuver length was:
13: 4, 14: 18, 15: 81, 16: 609, 17: 3893, 18: 23411, 19: 141366, 20: 830618.

This shows, that the probability to find a random cube position which cannot be solved within 20 moves with the Two-Phase-Algorithm in a reasonable time must be very low or zero.
It also shows: If there are any cube positions which need at least 21 moves to be solved, these positons are very rare and there is almost no chance to find such positions by random.

In 2009 I used Cube Explorer 4.64s and an Intel Core i7 920 CPU machine (Vista 64 bit with 6 GB of RAM) to solve 100000 random positions optimally in parallel on 8 cores (4 physical and 4 virtual cores).



On average the program solved about 7000 cubes/day ! In this sense Cube Explorer's implementation of God's Algorithm does a decent job, though there theoretically could exist some situations, which need hours, days... to be solved. The average optimal solving length is ~17.7 . If you want to download the 100000 optimally solved cubes for some reason, you can do this here.

The theoretical distribution for the maneuver length of God's Algorithm for Rubiks Cube is only known for maneuver lengths less then 11.

Because there are 1, 18, 243, 3240, 43239, 574908, 7618438, 100803036,1332343288, 17596479795, 232248063316, 3063288809012 positions which have a shortes maneuver length of n moves for n = 0 to 11 (see sequence A080601 in the On-Line Encyclopedia of Integer Sequences) and there are 43252003274489856000 different cube positions, we get for the probability P to solve a random cube optimally in n moves:

Maneuver Length n
Probability P
Branching Factor B
0
2.31203 *10-20
18
1
4.16166*10-19
13.5
2
5.61824*10-18
13.3333
3
7.49098*10-17
13.3454
4
9.99699*10-16
13.2961
5
1.32921*10-14
13.2516
6
1.76141*10-13
13.2315
7
2.3306*10-12
13.2173
8
3.08042*10-11
13.2072
9
4.06836*10-10
13.1986
10
5.36965*10-9
13.1897
11
7.08242×10-8
~13.18 (estimated)
12
~9.3*10-7
~13.18 (estimated)
13
~0.000012
~13.18 (estimated)
14
~0.00016
~13 (estimated)
15
simulation result: ~0.002 ±0.0003*
~12 (estimated)
16
simulation result: ~0.027 ±0.001*
~9.9 (simulation)
17
simulation result: ~0.267 ±0.003*
~2.51 (simulation)
18
simulation result: ~0.671 ±0.003*
~0.054 (simulation)
19
simulation result: ~0.033 ±0.001*
?
20
P > 0
?
21, 22
unknown, but presumably 0
?
*: 95% confidence interval

Phase 1 of the Two-Phase-Algorithm needs at most 12 moves and phase 2 needs at most 18 moves. Michael Reid showed in 1995, that the 18 moves case for phase 2 always can be avoided. So all cubes can be solved within 29 moves.

Gene Cooperman and Dan Kunkle claim in this paper (2007) to have proven that 26 moves suffice, but there is yet a gap in the paper. This gap seems to be fixed meanwhile (August 2007, see Kunkles comment in the Domain of the Cube Forum - you must be logged in there to see the comments) but the corrected paper is not available yet.

Silviu Radu proved in this paper (also 2007) that 27 moves suffice.

In May 2008 Tomas Rokicki proved, that 23 moves suffice, analyzing more than 200000 cosets of the phase 2 subgroup of the Two-Phase-Algorithm (Domain of the Cube Forum). This is indeed a big leap forward! There is still no paper available for the proof, but the method is similar to the method Rokicki describes in this paper (also 2008) for 25 moves.

In August 2008 Tomas Rokicki reduced the upper bound to 22 moves after having analyzed 1.28 million cosets within 50 core-years of CPU time (Domain of the Cube Forum). A paper will be available soon.