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?

We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
We did not find optimal solutions to each position, but instead only solutions of length 26 or less.
We wrote a program that solved a single set in about 17 seconds.
We used about 29 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

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.