God's number — how a computer thinks

43,252,003,274,489,856,000

That's how many positions a Rubik's cube has — forty-three quintillion. Make a cube of the ordinary size, 5.7 centimeters across, for every one of those positions, and you could cover the entire surface of the Earth about 275 layers deep. And if you went through them at one position per second, the job would take nearly a hundred times the age of the universe.

And yet every one of them has a shortest way home. This chapter is about how long that way is, and how a computer finds it without trying everything.

God's number

Picture an all-knowing being who glances at any cube and instantly sees the shortest solution. How many moves would it need in the very worst case? That number was jokingly named God's number.

The answer is 20. Here a half turn counts as a single move. Count it as two, and the answer is 26 — that was proved later, in 2014.

On the cube is one of the hardest positions of all, the superflip. Every corner and every edge is in its place, but every single edge is flipped. It looks almost solved, yet there's no way to solve it in fewer than 20 moves: Michael Reid proved that back in 1995. Here are those twenty moves: U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2. Tap them and notice: the same algorithm both scrambles and unscrambles. The superflip is its own inverse.

Thistlethwaite's staircase

Brute force won't work, not even for a computer. Checking a billion positions a second, it would grind away for nearly 1,400 years. You need a trick.

In 1981 the mathematician Morwen Thistlethwaite had the idea of walking down to the solution step by step. At each step, the cube is led into a "world" where some of the turns are no longer needed. First the top and bottom may only be turned by 180°. Then the front and back as well. Then every face turns only by 180°. Each world is thousands, or even millions, of times smaller than the one before, and easier to search. Four steps, and any cube is solved in at most 52 moves.

On the cube is the last step. The faces turn only by 180°, and each one shows just two colors: its own and the opposite one.

Try it yourself: checkerboard

Take a look inside the world of the last step. Make a "checkerboard" — a pattern where the squares on every face alternate like a chessboard. The rule is simple: turn each face once by 180°, doing opposite faces as a pair, back to back — right with left, top with bottom, front with back. The pairs can go in any order.

Kociemba — two steps instead of four

In 1992 Herbert Kociemba cut the staircase down to two steps.

Phase 1 — tidy up. The goal is for every piece to be oriented correctly, and for the four middle-layer edges to sit in the middle layer, even if not in their own spots. From the outside it looks like this: the top and bottom are made of nothing but yellow and white stickers.

Right now only the yellow and white stickers on the cube are in color, and they're scattered across every face. Tap B' L U' R F' — just five moves, and they all gather on the top and bottom. Mixed together, but on their own faces.

Why bother? From a position like this, the cube can be solved without ever leaving the "world": turning only the top and bottom freely, and the other faces by 180°. That world holds about 19.5 billion positions. A lot — but next to forty-three quintillion, a mere handful.

Phase 2 and pruning tables

Phase 2 — put everything in place. From here on only the allowed turns are used, so the order from phase 1 can't be undone. All that's left is to move the pieces to their spots: U2 F2 D2 R2 U L2 B2 D R2 F2 U'. Look: not a single quarter turn of a side face.

How does the computer find these moves? It searches, but cleverly. Before the search even begins, it builds pruning tables. For every "simplified" state — say, looking only at how the corners are twisted — they record the fewest moves it takes to fix it. It's like a navigation app that knows home is at least five kilometers away as the crow flies. If you have three moves left and the table says "you need at least five," you can abandon that branch without looking any deeper. That prunes away almost every path.

The first solution found is often on the long side. But the program doesn't stop there. It tries a slightly longer phase 1 so that phase 2 gets shorter, and within a second or two it works its way down to solutions of around 20 moves. Not always the very shortest, but almost always close.

How twenty was proved

The hunt for God's number took thirty years. In 1981 we knew that 52 moves were enough; by 2008, 22. From below, the bound was propped up by counting: the number of distinct move sequences up to 17 moves long, once you throw out obviously wasteful ones like R R', is smaller than the number of cube positions. So some positions need at least 18. The superflip raised that bar to 20. All that remained was to close the gap.

In July 2010 it was done by Tomas Rokicki, Herbert Kociemba — yes, the same one — Morley Davidson and John Dethridge. They split all the positions into 2.2 billion groups of 19.5 billion each, every group built just like the world of phase 2. The cube's symmetries and a couple of other tricks cut the work down to 56 million groups, and the program got through each one in about 20 seconds. In all, it took about 35 years of CPU time, donated by Google. The verdict: no position needs more than 20 moves.

How many times to repeat

The cube is also a textbook of group theory. Repeat any algorithm over and over, and sooner or later it brings the cube back to where it started. There are only finitely many positions, so at some point the cube has to land somewhere it has already been. And since every move can be undone, the first position to come round again is the starting one. The number of repetitions it takes to get back is called the order. The sexy move, as you'll remember, comes back after 6.

But humble little R U has order 105. Why so many? Seven edges travel round a single loop — they need 7 repetitions. Five corners go round a loop too, but come back twisted, so they need 15. And one more corner just spins in place — 3 is enough for it. Everything lines up when the number of repetitions is divisible by 7, by 15 and by 3. The first time that happens is at 105.

There are small miracles along the way. On the cube is R U repeated 35 times: every edge is home, and six corners are in their places, but twisted. After 15 repetitions it's the other way round: the corners are home, and seven edges are shuffled. The largest order on the cube is 1260: there's a sequence of just five moves that you have to repeat 1260 times to get back.

Try it yourself: think backwards

This cube was scrambled with just three moves. Try to solve it in three as well. Hint: think like a computer, starting from the end. Which layer was turned last? Unwind that one first.

Three solutions for one cube

On the Solve my cube page you can enter your own cube and see three solutions side by side. The beginner's one: layer by layer, 100–150 moves, with every step familiar from this textbook. The speedcuber's one: CFOP, about 60 moves. And the computer's one: Kociemba's, about twenty.

Compare them on the same cube. The human solutions are long but readable — you can see what's being built and why. The computer's is short and mysterious: the cube looks scrambled until almost the last few moves, and then it all falls into place at once. That's the difference between understanding and finding — and it's good to be able to do both.