God's Number: Every Rubik's Cube Can Be Solved in 20 Moves

God's number is 20. Every one of the 43,252,003,274,489,856,000 positions of a Rubik's Cube can be solved in 20 moves or fewer, when any turn of a face counts as one move. Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge proved it in July 2010 (cube20.org; paper: SIAM Journal on Discrete Mathematics 27(2), 2013). If a half turn counts as two moves, the answer is 26, proved in August 2014 by Rokicki and Davidson (cube20.org/qtm).

So yes, any scrambled cube can be solved in 20 moves. Finding those 20 moves is another matter. That takes a computer, as you'll see below.

• Counting moves
• History
• The proof
• Hardest positions
• Superflip
• Other puzzles

What "God's Number" Means

Imagine a solver that always knows the shortest possible solution for any position. Puzzle mathematicians call that God's algorithm. God's number is how many moves God's algorithm needs in the worst case: the number of moves the hardest position takes to solve when you play perfectly. For the Rubik's Cube, that's 20.

That doesn't mean a typical cube needs 20. Most random scrambles can be solved in 18 moves. Positions that truly need 20 are extremely rare, as the table further down shows.

Two Ways to Count a Move

The answer depends on what you call one move. Mathematicians use two rules, called metrics:

• Half-turn metric (HTM), also called the face-turn metric. Any turn of one face is one move, whether it's a quarter turn (R, R') or a half turn (R2). God's number here is 20.
• Quarter-turn metric (QTM). Only quarter turns count as one move, so R2 counts as two. God's number here is 26.

For example, the algorithm R U R' U R U2 R' is 7 moves in the half-turn metric and 8 in the quarter-turn metric, because U2 counts twice. When people say "20 moves" without saying which, they mean the half-turn metric. It's also how our solver counts. If the letters are new to you, see the notation guide.

History of God's Number

For 30 years, people knew only a range. Lower bounds came from finding positions that provably need many moves. Upper bounds came from methods that provably solve every position within some number of moves. By 1980, counting arguments had shown that some positions need at least 18 moves. Here's how the gap closed, in the half-turn metric, as listed by cube20.org:

Two milestones stand out. In 1995, Michael Reid showed that one position, the superflip, cannot be solved in fewer than 20 moves. That set the lower bound for good. In 2010, the team above showed that no position needs more than 20, so the two bounds finally met.

The quarter-turn metric took longer. Michael Reid showed in 1998 that one position (the superflip combined with a pattern called "fourspot") needs 26 quarter turns. Rokicki and Davidson showed in 2014 that nothing needs more (cube20.org/qtm).

How It Was Proved

Solving 43 quintillion positions one by one is impossible, so the team split the problem up. This is how they describe it on cube20.org:

• Cosets. They divided every position into 2,217,093,120 sets of 19,508,428,800 positions each. Each set is a coset of the group of positions reachable with U, D and half turns of the other four faces, the same group Kociemba's two-phase algorithm uses. One whole set fits in a PC's memory and can be solved together.
• Symmetry. A cube turned upside down or seen in a mirror is no harder to solve. With 24 ways to hold the cube and a mirror, that cuts the work by a factor of about 48. Symmetry and a "set cover" calculation brought the number of sets to solve down to 55,882,296.
• Good enough, not optimal. Since the superflip already needed 20, they didn't have to find the shortest solution for every position. They only had to show each one could be done in 20 or fewer. That is much faster. Their program finished one set in about 20 seconds.
• Google's computers. Google donated about 35 CPU-years of idle computer time. The whole run took just a few weeks.

This is a computer-assisted proof. It is accepted because the method is published in a peer-reviewed paper (Rokicki et al., 2013) and the source code is public.

How Many Positions Need 20 Moves?

About 490 million, an estimate from cube20.org. That sounds like a lot, but it's fewer than one in a billion positions. The exact number is still unknown. Here is the full table of how many positions sit at each distance from solved (half-turn metric). Counts up to 15 are exact. From 16 on, they are estimates.

Distance 18 is by far the most common, about two thirds of all positions. That's why "most scrambles take 18 moves" is a fair rule of thumb.

The Superflip

The superflip is the most famous hard position. Every edge sits in its correct spot but is flipped the wrong way round, while the corners and centers are solved. It was the first position proven to need 20 moves. The 20-move sequence below, from cube20.org, makes it from a solved cube. Press Play to watch:

The sequence is R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U: 20 moves in the half-turn metric, or 28 quarter turns. The superflip undoes itself, so doing the same 20 moves again returns the cube to solved. It's also a striking pattern to show friends. See more Rubik's Cube patterns.

Can a Person Solve a Cube in 20 Moves?

Not reliably. Finding a 20-move solution means searching through billions of possibilities, which is a job for a computer. Methods a person can memorize typically need more than forty moves (cube20.org), and the beginner method needs more than that.

The closest human version is the World Cube Association's Fewest Moves event: competitors get 60 minutes, pen and paper to find the shortest solution they can, and the result is the number of moves (WCA Regulations, E2b and E2d). If you only want a short solution for the cube in your hand, our Rubik's Cube solver finds one in about a second.

Why Our Solver Doesn't Always Find 20

Our solver uses Kociemba's two-phase algorithm with a time limit. It finds a short solution quickly, keeps looking for a shorter one for a fraction of a second, then stops. That gives short solutions, but not proven-shortest ones. A position the solver answers in 21 moves may well have a 19-move solution it didn't have time to reach.

We tested it on 10,000 random cubes with a 300 ms limit each, and replayed every solution to check it. The average was 19.85 moves, the shortest 15 and the longest 22.

• 3,011 (30%) were solved in 19 moves or fewer.
• 4,785 (48%) took exactly 20 moves.
• 2,204 (22%) took more than 20 moves.

Compare that with the table above: almost every real position can be done in 18 or 19, so a solution of 20 or more is usually not the shortest one. Finding the optimal solution for one position takes far longer, which is why cube20.org lists the optimal rate as well under one position per second, against thousands per second for "20 moves or less". Our results say nothing about God's number itself. That came from the 2010 proof.

Other Puzzles

2x2 cube: 11 moves (14 quarter turns)

The 2x2 has 3,674,160 positions, few enough to check them all. Every position can be solved in 11 moves, or 14 if half turns count as two (Jaap's Puzzle Page). Our 2x2 solver lists every position too, and our tests confirm both numbers from its own table: 2,644 positions need 11 moves, and 276 need 14 quarter turns. Every row of our table matches Jaap's.

Pyraminx: 11 moves, plus tips

Leaving out the four loose tips, the Pyraminx has 933,120 positions and every one can be solved in 11 moves (Jaap's Puzzle Page). Our Pyraminx solver's table agrees: 32 positions need all 11. Each tip then takes at most one more turn.

4x4 and bigger: unknown

Nobody knows God's number for the 4x4 or any larger cube. They have far too many positions for the kind of search used on the 3x3, and nobody has proved a matching lower and upper bound.

FAQ