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.

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.

How We Did It

How did we solve all 43,252,003,274,489,856,000 positions of the Cube?
Distance Count of Positions Distance Count of Positions
0 1 14 50,729,620,202,582
1 12 15 472,495,678,811,004
2 114 16 4,393,570,406,220,123
3 1,068 17 40,648,181,519,827,392
4 10,011 18 368,071,526,203,620,348
5 93,840 19 about 3,000,000,000,000,000,000
6 878,880 20 about 14,000,000,000,000,000,000
7 8,221,632 21 about 19,000,000,000,000,000,000
8 76,843,595 22 about 7,000,000,000,000,000,000
9 717,789,576 23 about 24,000,000,000,000,000
10 6,701,836,858 24 about 150,000
11 62,549,615,248 25 36?
12 583,570,100,997 26 3?
13 5,442,351,625,028 >26 0

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.