With about 29 CPU-years of idle computer time at the Ohio Supercomputing Center, two researchers have essentially solved every position of the Rubik's Cube™ in the quarter-turn metric, and shown that no position requires more than 26 moves.
Indeed, the mathematics of the quarter-turn metric are very interesting. The positions of the cube can be separated by a concept called permutation parity into even and odd positions. Every quarter turn from an odd position yields and even position, and vice versa, so any move sequence in the quarter-turn metric ping-pongs between even and odd positions. This is not true of the half-turn metric. Simply by examining a position, without any search, one can determine whether the optimal sequence length of any position is even or odd.
Further interest comes from the nature of the antipodes in the two metrics. An antipode is a distance that is maximally far from solved, one that requires the maximum number of moves to solve. In the half-turn metric, with a God's Number of 20, we know there are hundreds of millions of such positions. Surprisingly, in the quarter-turn metric, only a single position (and its two rotations) is known that requires the maximum of 26 moves. Despite significant effort, no additional distance-26 positions have been found.
Even at distance 25, only two positions (and their rotations) are known to exist. At distance 24, perhaps 150,000 positions exist.
|Date||Lower bound||Upper bound||Gap||Notes and Links|
|Jan, 1981||21||140||119||Dan Hoey first shows that there are positions that require 21 moves.|
|July, 1981||21||104||83||Morwen Thistlethwaite proves 52 moves suffice; doubling this gives a bound of 104 in the quarter-turn metric.|
|May, 1992||21||56||35||Michael Reid proves 56 moves suffices.|
|Jan, 1995||21||42||21||Michael Reid proves 42 moves suffices.|
|Jan, 1995||22||42||20||Michael Reid finds that some position requires at least 22 moves.|
|Aug, 1998||26||42||16||Michael Reid proves superflip plus fourspot requires 26 moves.|
|Nov, 2005||26||40||14||Silviu Radu reduces the upper bound to 40 moves.|
|Jan, 2006||26||38||12||Bruce Norskog reduces the upper bound to 38 moves.|
|Jan, 2006||26||36||10||Silviu Radu reduces the upper bound to 36 moves.|
|Mar, 2006||26||35||9||Silviu Radu reduces the upper bound to 35 moves.|
|Jul, 2007||26||34||8||Silviu Radu reduces the upper bound to 34 moves.|
|Jan, 2009||26||32||6||Tomas Rokicki reduces the upper bound to 32 moves.|
|Jan, 2009||26||31||5||Tomas Rokicki reduces the upper bound to 31 moves.|
|Feb, 2009||26||30||4||Tomas Rokicki reduces the upper bound to 30 moves.|
|Jun, 2009||26||29||3||Tomas Rokicki reduces the upper bound to 29 moves.|
|Aug, 2014||26||26||0||Tomas Rokicki and Morley Davidson finally prove that God's Number in the Quarter-Turn Metric is 26.|
|Distance||Count of Positions||Distance||Count of Positions|
Rubik's Cube is a registered trademark of Seven Towns, Ltd.
Thanks to Lucas Garron for writing the Cube animator on this page.
This work was supported in part by an allocation of computing time from the Ohio Supercomputer Center.