Two-Phase-Algorithm and God's Algorithm:
God's number is 20
|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. After 30 years it has finally been shown in July 2010, that all cube positions can be solved within 20 moves or less.|
God's Number is 20
An overview is given on the webpage http://cube20.org/.
Our proof was recently published in SIAM Journal on Discrete Mathematics (Volume 27, Issue 2).
A tried to make a few webpages, which give more detailed information about the proof without being too technical.
The Two-Phase-Algorithm gives near optimal solutions
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.
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
Nevertheless the computation of God's number showed, that there some very rare positions which are quite hard to solve within 20 moves with the two-phase algorithm, for example the cube generated by the maneuver
Optimal Cube Solver
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).
In January 2010 Tomas Rokicki even solved 1 million random cubes optimally and got the following distribution, which is very close to the distribution I got:
As you can see, it is unlikely to find a cube position which really needs 20 moves by random. Presumably the chance is less than 10-11, see here for details.
The first cube proved in 1995 to need 20 moves was the superflip, a highly symmetric cube position.
Theoretical Probability Distribution
Though we now know, that all positions can be solved within 20 moves, the theoretical distribution for the maneuver length of God's Algorithm for Rubiks Cube is only known for maneuver lengths less than 16.
Because there are 1, 18, 243, 3240, 43239, 574908, 7618438, 100803036,1332343288, 17596479795, 232248063316, 3063288809012, 40374425656248, 531653418284628, 6989320578825358, 91365146187124313 positions which have a shortes maneuver length of n moves for n = 0 to 15 (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:
Important milestones on the path towards God's number
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
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). See this well written paper for details.
In July 2010 Morley Davidson, John Dethridge, Tomas Rokicki and me proved that God's Number for the Cube is exactly 20.