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 standard-size cube, 5.7 centimeters across, for each one of them, and you could cover the entire surface of the Earth about 275 layers deep. Go through them at one position per second, and 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

Imagine an all-knowing being that can glance at any cube and instantly see the shortest solution. How many moves would it need in the very worst case? That number has been jokingly dubbed God's number.

The answer is 20, counting a half turn as a single move. Count it as two, and the answer is 26, which was proved later, in 2014.

The cube shows 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 seems a hair away from 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 that the same algorithm both scrambles the cube and unscrambles it. 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 came up with a way to walk down to the solution one step at a time. At each step, the cube is steered into a "world" where some of the turns are no longer needed. First, the top and bottom may only be turned 180°. Next, the front and back get the same restriction. Finally, every face turns only 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 52 moves or fewer.

The cube here is already on the last step: the faces turn only 180°, and each one shows just two colors, its own and the opposite face's.

Try it yourself: a checkerboard

Take a peek inside the world of the final step. Make a checkerboard, a pattern where the squares on every face alternate like the squares on a chessboard. The rule is simple: give each face one half turn, doing opposite faces back to back as a pair (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 to orient every piece correctly and get the four middle-layer edges into the middle layer, even if not into their own spots. From the outside, it's easy to spot: the top and bottom are made of nothing but yellow and white stickers. There's also a subtler sign: every middle-layer edge has its green or blue sticker facing front or back.

Right now only the yellow and white stickers are in color, and they're scattered across every face. Tap B' L U' R F': in just five moves, they all gather on the top and bottom. They're mixed together, but on the right two faces.

Why bother? From a position like this, the cube can be solved without ever leaving that "world": you turn the top and bottom freely and the other faces only 180°. This world holds about 19.5 billion positions. That's a lot, but next to forty-three quintillion it's 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 come undone. All that's left is to move the pieces to their spots: U2 F2 D2 R2 U L2 B2 D R2 F2 U'. Notice that there isn't 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 it finds is often on the long side. But the program doesn't stop there. It tries a slightly longer phase 1 so that phase 2 comes out shorter, and within a second or two it works its way down to solutions of around 20 moves. They're not always the very shortest, but they're almost always close.

How twenty was proved

The hunt for God's number took thirty years. In 1981 we knew that 52 moves were always enough; by 2008, 22. The lower bound came from counting: once you throw out obviously wasteful sequences like R R', there are fewer distinct sequences of up to 17 moves than there are 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 the gap was closed 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, the job took about 35 years of CPU time, donated by Google. The verdict: no position needs more than 20 moves.

How many times around

The cube is also a group theory textbook in disguise. 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 around again is the starting one. The number of repetitions it takes to get back is called the algorithm's order. The sexy move, as you'll remember, comes home after 6.

But humble little R U has an order of 105. Why so many? Seven edges travel around a single loop, so they need 7 repetitions. Five corners circle 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 only when the number of repetitions is divisible by 7, by 15 and by 3, and the first time that happens is at 105.

There are little miracles along the way. The cube shows 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 around: 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, too. Hint: think like a computer and start from the end. Which layer was turned last? Undo that one first.

Four solutions for one cube

On the Solve my cube page, you can enter your own cube and see four solutions side by side. The beginner's solution goes layer by layer: 120–180 moves, with every step familiar from this textbook. The in-between one uses intuitive F2L, about 75 moves: pairs, as in the three F2L chapters, and the last layer in four looks, with the 2-look OLL and PLL from the CFOP chapter. The speedcuber's is CFOP, about 55 moves. And the computer's is 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 the last few moves, and then everything falls into place at once. That's the difference between understanding a solution and finding one, and it's good to be able to do both.