Thistlethwaite's Algorithm: Solving a Cube in Four Phases

Thistlethwaite's algorithm is a way to solve a scrambled cube puzzle in four phases, where each phase takes away some of the turns you are allowed to make. Morwen Thistlethwaite found it around 1980, and it showed that any position can be solved in at most 52 moves, later cut to 45. This guide explains the four phases in plain words, shows why the first phase has exactly 2,048 positions, and gives you an exercise to sort move lists into each phase yourself.

If you like seeing what turns do on a real cube, Evolved 2048 puts the 2048 puzzle on a cube you twist and turn in your browser, where every kind of move has its own cost.

What Thistlethwaite's algorithm is

Wikipedia's article on optimal solutions for the Rubik's Cube calls Thistlethwaite's idea a breakthrough known as "descent through nested sub-groups". Details of the method were published in Scientific American in 1981 by Douglas Hofstadter.

The key move was a change in how the problem is split. Methods before it split the cube by the pieces that should stay fixed: solve these pieces, keep them, move on. Thistlethwaite split it by the type of move you may make. At each phase you give up some turns for good, and the cube gets closer to solved because the turns you have left can no longer mess up what the earlier phases fixed.

It is not built to find the shortest solution. The article says its average is about 31 moves, and that it cannot be adjusted to always find the best solution in the half turn metric, unlike the later methods. Its value is the idea, and the proof of an upper bound that it gave.

The four phases: turns you give up one by one

Cube notation names the six faces with letters: L, R, F, B, U and D for left, right, front, back, up and down. A letter alone is a quarter turn, and a letter with 2 is a half turn. If the letters are new to you, start with our beginner's guide to cube notation.

Thistlethwaite's chain is five groups, each a set of positions you can reach with a set of moves:

• G0: every turn, L, R, F, B, U and D. This is any scrambled cube.
• G1: L, R, F and B, but U and D only as half turns.
• G2: L and R, but F, B, U and D only as half turns.
• G3: half turns only, on all six faces.
• G4: the solved cube alone.

Each phase moves the cube from one group into the next. Wikipedia's summary names the targets: phase 1 reaches edge orientation, phase 2 domino reduction, phase 3 half-turn reduction, and phase 4 the solved cube.

Why each phase is small

The whole cube group is huge: Wikipedia gives about 43 times 10 to the 18th positions, the number in our post on cube permutations. No table could hold a move list for each one.

Thistlethwaite's trick is that each phase only has to tell apart the positions that matter for the next group. In group theory these are the coset spaces, and they are small:

• Phase 1: 2,048 positions.
• Phase 2: 1,082,565 positions.
• Phase 3: 29,400 positions.
• Phase 4: 663,552 positions.

For each position in each phase he prepared a move sequence that took it to the next group. Then solving is four look ups: find where the cube is in phase 1, apply that sequence, find it in phase 2, and so on. If you want the background on groups first, our post on cube group theory explains them without the symbols.

The first number is the same as the tile the 2048 game is named after: 2,048 is 2 multiplied by itself 11 times. Phase 1 is about edge orientation, which our post on flipped edges covers from the puzzle side.

From 85 moves to 52, then 45

The algorithm came out of a run of improvements, which the article lists:

1. Thistlethwaite first showed, with a different method, that any position could be solved in at most 85 moves.
2. In January 1980 he brought that to 80.
3. Later that year a new approach gave 63.
4. Then a different approach again gave 52. That one is now called Thistlethwaite's algorithm.

Later, by searching every position in each coset space, people found the worst case for each phase: 7, 10, 13 and 15 moves. Added up, that is at most 45 moves for any cube.

That is still far above the true answer. In 2010 a computer proof by Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge showed every position can be solved in at most 20 face turns, the story told in our post on God's number. Kociemba's own method, from 1992, was built straight on Thistlethwaite's: it keeps only two intermediate groups, and its middle group is the same as Thistlethwaite's G2.

A worked example: sort move lists into the groups

You can feel how the phases work without a cube in your hands. Take a move list and ask: what is the smallest group whose allowed turns cover every move in it? Here are four lists to try.

• R U F2: U is a quarter turn of the top face, and only G0 allows that. Answer: G0.
• F R U2 B': F, R and B' are quarter turns of faces G1 allows, and U2 is a half turn. Answer: G1.
• L F2 R' D2: L and R' are the only quarter turns, and F2 and D2 are half turns. Answer: G2.
• R2 U2 F2 L2: all half turns. Answer: G3.

Now read the chain the other way. Once phase 1 is done, the solver only ever uses moves from G1, so U and D quarter turns never appear again. After phase 2, F and B quarter turns are gone too. By phase 4 the cube is solved with half turns alone. Each phase hands the next one a smaller toolbox and an easier cube.

Try writing a short scramble of your own and sorting it. A list that uses only half turns stays in G3, which is a useful thing to know when you read solves in notation.

Limiting your own moves on a 2048 cube

Evolved 2048 is the 2048 puzzle on a cube you turn like a Rubik's cube: six faces of nine squares, 54 in all. You slide the front face so equal tiles merge, twist a row or column to carry tiles round from the other faces, and turn the whole cube to use its other sides. The keys 1, 2 and 3 twist the top, middle and bottom row right, 4, 5 and 6 twist the left, middle and right column up, and Shift twists the other way.

The game is not a cube to solve, so the algorithm does not carry over. The habit does. Thistlethwaite made progress by choosing which moves to give up. On a 2048 cube each kind of move has its own price:

• Turning the whole cube (Shift with an arrow key) counts no move and adds no tile. The first game tip says it plainly: "Turning is free."
• Twisting a row or column counts one move, adds a new tile and scores no points.
• Sliding the front face is where merges and points come from.

So a simple plan is a chain of your own: turn first to look, slide when a merge is there, and twist only when it carries a tile next to its match. Each step you leave out is a tile you do not have to place.

Frequently asked questions

What is Thistlethwaite's algorithm?

It is a method that solves a cube puzzle in four phases, each one moving the cube into a smaller group of positions reached with fewer kinds of turns. It ends with half turns only.

How many moves does Thistlethwaite's algorithm take?

At most 52 in Thistlethwaite's own version, and at most 45 once every phase was searched for its worst case. Wikipedia gives an average of about 31 moves.

Why does phase 1 have 2,048 positions?

Phase 1 only has to fix edge orientation, and Wikipedia counts 2,048 positions in that coset space. That is 2 multiplied by itself 11 times, the same number as the 2048 tile.

Is Thistlethwaite's algorithm the same as Kociemba's?

No. Kociemba's 1992 method builds on it but uses only two intermediate groups, and it can be set up to find the shortest solution, which Thistlethwaite's cannot.

Get started

Thistlethwaite's algorithm is a lesson in choosing your moves: give up the ones you no longer need and the rest gets easier. On a 2048 cube, turning is free, twists cost a tile, and slides score, so pick each one on purpose.

Play Evolved 2048: it is free and plays in your browser on a computer or a phone.