God’s Number: Why a Rubik’s Cube Needs at Most 20 Moves

Quick answer: God’s number is the smallest number of moves that is always enough to solve a standard 3×3 Rubik’s Cube from any legal position (one reachable by turning, not by taking the cube apart). It is 20, counting any turn of a face (including half turns) as one move. Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge proved this in 2010 using about 35 CPU-years of computer time donated by Google. Counting only quarter turns, God’s number is 26 (proved in 2014 by Tomas Rokicki and Morley Davidson). The cube has about 43 quintillion positions.

Scramble a Rubik’s Cube as badly as you like. If an all-knowing being solved it using the fewest possible moves, how many would it need in the worst case? That number is called God’s number, and after 30 years of effort it was finally pinned down in 2010: it is 20.

How Many Positions?

A standard 3×3×3 cube has

\[ \frac{8! \times 3^7 \times 12! \times 2^{11}}{2} = 43{,}252{,}003{,}274{,}489{,}856{,}000 \]

positions, about 43 quintillion. The factors count arrangements of the 8 corners, their twists, the 12 edges and their flips, divided by 2 because of a parity constraint. Review permutations to see where factorials come from.

What Counts as a Move?

MetricWhat counts as one moveGod’s numberProved
Half-turn metricAny face turn: 90°, 180° or 270°202010
Quarter-turn metricOnly 90° turns (a 180° turn counts as 2)262014 (Rokicki and Davidson)

The Long Search

YearLower boundUpper bound
19811852 (Morwen Thistlethwaite)
199520 (Michael Reid: the “superflip” needs 20)29
20082022 (Tomas Rokicki)
20102020 (Rokicki, Kociemba, Davidson, Dethridge)

The lower bound came from one position, the superflip (every edge flipped in place), which Reid showed needs exactly 20 moves. The challenge was showing that no position needs 21.

How the Proof Worked

Checking 43 quintillion positions one by one was impossible. The team used group theory to split the positions into about 2.2 billion sets (cosets) of about 19.5 billion positions each, then used symmetry and a set-covering trick to reduce the work to about 56 million sets. A fast program solved each set in about 20 seconds. The total was about 35 CPU-years, run on computers donated by Google, in a few weeks of 2010.

Fun Facts

  • The team estimated that about 490 million positions need exactly 20 moves, and that most positions have shortest solutions of 17 or 18 moves (half-turn metric). These are estimates: the theorem fixes the maximum, not the exact count at each distance. The cube20.org project also keeps a growing catalogue of specific positions confirmed to need 20 moves; that list is still being extended.
  • Speedcubers usually use around 50 to 60 moves, because human methods trade move count for steps that are quick to recognize and execute.
  • The cube’s moves form a group with 43 quintillion elements, a favorite example in abstract algebra.

Common Misconceptions

“Any cube can be solved in 20 moves by anyone.” The theorem says a solution of 20 moves or fewer always exists. It does not give an easy way to find a shortest solution for every scramble, so humans use longer methods (though a cube one turn from solved is easy, of course).

“God’s number is 26.” Only if you count a half turn as two moves (the quarter-turn metric). In the standard half-turn metric it is 20.

Watch: God’s Number in Video

If you learn better by watching, these videos are worth your time.

God’s Number and Rubik’s Cube – Numberphile (Numberphile). How the 20-move answer was proved.
The Search For God’s Number (J Perm). The history of the search, from 52 moves down to 20.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What is God’s number in the half-turn metric?
Found a bug? Let us know!
2. What is God’s number in the quarter-turn metric?
Found a bug? Let us know!
3. About how many positions does a Rubik’s Cube have?
Found a bug? Let us know!
4. Which position showed that at least 20 moves are sometimes needed?
Found a bug? Let us know!
5. Which company donated computer time for the 2010 proof?
Found a bug? Let us know!

Frequently Asked Questions

What is God’s number for the Rubik’s Cube?

20. Every legal position of the standard 3×3×3 cube can be solved in 20 face turns or fewer (half-turn metric), and some positions, such as the superflip, need exactly 20.

What is the superflip?

The position where every edge piece is flipped in place and everything else is solved. Michael Reid showed in 1995 that it needs 20 moves, which proved God’s number is at least 20.

Who proved God’s number is 20?

Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge, in 2010, using computer time donated by Google.

How many positions does a Rubik’s Cube have?

43,252,003,274,489,856,000, about 43 quintillion.

Why is God’s number 26 in some sources?

That is the quarter-turn metric, where a half turn counts as two moves. In the usual half-turn metric it is 20.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "God’s Number: Why a Rubik’s Cube Needs at Most 20 Moves - Effortless Math"?

No one replied yet.

Leave a Reply