References and further reading.

References and further reading.


Main source 1 Wikipedia

Main source 2 Kociemba's website

Articles with short explanation:

Gene Cooperman and Dan Kunkle: Twenty-Six Moves Suffice for Rubik's Cube (2007).

(Warning: This article has a high level of required mathematical knowledge.)

Silviu Radu: New Upper Bounds on Rubik's Cube (2007).

Tomas Rokicki: Twenty-Five Moves Suffice for Rubik's Cube (2008).

Tomas Rokicki: Twenty-Two Moves Suffice for Rubik's Cube (2009).

The above articles all use a smart idea to prove that there cannot exist a position that requires more than 30 moves to be solved. The differences between the articles are the refinements and the amount of computers used to lower the upper bound.

The idea is as follows. We define a subgroup H of the whole group G as follows

*All cubies of all positions in H are corectly orientated.

*Edges that belong in the middle are located in the middle layer.

By counting argumnets we find that the order of H is roughly 19.5 billion. The order of the entire group is roughly 4.3*10^19. Now we can create a coset G/H which has order 2.22*10^9, which is much smaller than the original 10^19. Even more, this set is not too large to work with.

Furthermore, Reid showed that any position from H can be solved in at most 18 moves. On top of that, Reid showed that any position in G can be brought to a position in H by no more than 12 moves. This automatically gives us an upper bound of 30. For we can now create an algorith that contains two phases (also a link on Kociemba's webpage). Phase one brings an arbitrairy position into H. And phase two solves that position in H to the origin.

But we can do more than that. It can easily be possible that the shortest move sequence into H may not give a shortest move sequence in total. So, we can refine the algorithm to select a few 'short' move sequences into H, and for these calculate the remaining distance. Then choose the shortest total and report that output. This is explained in detail in Kunkle and Cooperman and further refined in Radu.

Furthermore, it is not necessary to determine the distance of all positions in G/H of order 2.2*10^9. We can restrict ourselves to these positions that have the greatest inpact on the set. For if some position is solvable in 18 moves, then all neighbors are solvable in at most 19 moves. The trick is to find positions that have the greatest impact and just solve those. If you pick more positions to solve, than you will get a better upper bound, but it'll take you more time.

In the last article (God's Number is 20), this is done. With help from a lot of computer time donated by Google researchers including Rokicki proved with about 35 CPU-years that God's Number is 20. See link below.

God's Number is 20