God's Number is 26 in the Quarter-Turn Metric

U U F U U R- L F F U F- B- R L U U R U D- R L- D R- L- D D Superflip composed with fourspot, the first position proven to require 26 moves.
Every position of Rubik's Cube™ can be solved in 26 quarter moves or less.

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.

What is the Quarter-Turn Metric?

In the early days of cube mathematics, two camps emerged on how to measure the difficulty of a position. West coast and Stanford mathematicians, free thinkers all, tended to prefer the half-turn metric, where any twist of any face, whether 90 degrees, 180 degrees, or 270 degrees counted as a single move. The east coast crowd, including MIT, tended to prefer the rigor of the quarter-turn metric, where a half-turn counted as two moves, since of course it could be accomplished by two consecutive quarter turns.

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.

A History of God's Number in the Quarter-Turn Metric

By 1980, a lower bound of 19 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions of odd parity. The first upper bound was probably around 140 or so, by analyzing the worst-case move count of the early solution booklets. This table summarizes the subsequent results.

DateLower boundUpper bound GapNotes and Links
Jan, 198121140119Dan Hoey first shows that there are positions that require 21 moves.
July, 19812110483 Morwen Thistlethwaite proves 52 moves suffice; doubling this gives a bound of 104 in the quarter-turn metric.
May, 1992215635 Michael Reid proves 56 moves suffices.
Jan, 1995214221 Michael Reid proves 42 moves suffices.
Jan, 1995224220 Michael Reid finds that some position requires at least 22 moves.
Aug, 1998264216 Michael Reid proves superflip plus fourspot requires 26 moves.
Nov, 2005264014 Silviu Radu reduces the upper bound to 40 moves.
Jan, 2006263812 Bruce Norskog reduces the upper bound to 38 moves.
Jan, 2006263610 Silviu Radu reduces the upper bound to 36 moves.
Mar, 200626359 Silviu Radu reduces the upper bound to 35 moves.
Jul, 200726348 Silviu Radu reduces the upper bound to 34 moves.
Jan, 200926326 Tomas Rokicki reduces the upper bound to 32 moves.
Jan, 200926315 Tomas Rokicki reduces the upper bound to 31 moves.
Feb, 200926304 Tomas Rokicki reduces the upper bound to 30 moves.
Jun, 200926293 Tomas Rokicki reduces the upper bound to 29 moves.
Aug, 201426260 Tomas Rokicki and Morley Davidson finally prove that God's Number in the Quarter-Turn Metric is 26.

How We Did It

How did we solve all 43,252,003,274,489,856,000 positions of the Cube?
DistanceCount of Positions DistanceCount of Positions
01 1450,729,620,202,582
112 15472,495,678,811,004
2114 164,393,570,406,220,123
31,068 1740,648,181,519,827,392
410,011 18368,071,526,203,620,348
593,840 19about 3,000,000,000,000,000,000
6878,880 20about 14,000,000,000,000,000,000
78,221,632 21about 19,000,000,000,000,000,000
876,843,595 22about 7,000,000,000,000,000,000
9717,789,576 23about 24,000,000,000,000,000
106,701,836,858 24about 150,000
1162,549,615,248 2536?
12583,570,100,997 263?
135,442,351,625,028 >260

Contact

This work was performed by Tomas Rokicki, a programmer from Palo Alto, California, and Morley Davidson, a mathematician from Kent State University. Email may be sent to rokicki@gmail.com or to davidson@math.kent.edu.

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.