Kociemba's Algorithm: How Two Phases Solve a Cube Fast

Kociemba's algorithm is a two-phase method that finds a short solution to a scrambled cube puzzle, usually 20 moves or less, in a fraction of a second. Herbert Kociemba published it in 1992 as an improvement on Thistlethwaite's four-phase method. This guide explains the two phases, what the middle stop called domino reduction means, and why a lookup table is what makes the search fast, with a worked count you can check on paper.

If you want to try turns and twists while you read, Evolved 2048 puts the 2048 puzzle on a cube you twist and turn in your browser, and counts every move you make.

Where Kociemba's algorithm comes from

Wikipedia's article on optimal solutions for the Rubik's Cube describes Thistlethwaite's method as a chain of groups. Each group is the set of positions you can reach with a smaller set of turns, and each phase moves the cube one step down the chain. Thistlethwaite used four phases. Our post on Thistlethwaite's algorithm walks through all four.

Kociemba kept the idea and cut the chain to two phases. His groups are:

• G0: every turn of U, D, R, L, F and B. Any scrambled cube is here.
• G1: quarter turns of U and D, but only half turns of R, L, F and B.
• G2: the solved cube alone.

His G1 is the same group as Thistlethwaite's G2. So Kociemba skips one stop on the way down and one stop on the way out, and goes straight to the middle.

Domino reduction: the one stop in the middle

Wikipedia's summary names the middle stop. Thistlethwaite's method runs scrambled cube, edge orientation, domino reduction, half-turn reduction, solved. Kociemba's runs scrambled cube, domino reduction, solved.

Once a cube is in domino reduction, it can be solved without ever making a quarter turn of R, L, F or B. You only need U and D turns of any size, and half turns of the other four faces. That is a much smaller toolbox, and it means a much smaller search.

So the two phases are:

1. Phase 1: take any scrambled cube into G1, using any turn. This needs at most 12 moves.
2. Phase 2: solve the cube from G1, using only G1's turns. This needs at most 18 moves.

Michael Reid showed both limits in 1995. In cube notation, U is a quarter turn of the top face and U2 a half turn; our guide to cube notation covers every letter.

A worked example: count the search

You can check why the method needs a trick with a pencil. Start by counting the moves allowed in each phase.

• Phase 1 moves: six faces, each turned clockwise, anticlockwise or by a half turn. That is 6 times 3, or 18 moves, the number Wikipedia gives.
• Phase 2 moves: U and D can still turn three ways each, which is 6 moves. R, L, F and B can only make a half turn, which is 4 more. That is 10 moves.

Now the size of a blind search for phase 1. Phase 1 can need 12 moves, and each step has 18 choices, so trying every list means up to 18 multiplied by itself 12 times. Wikipedia puts that at over 1 quadrillion cube states. Even a smart search would struggle with that.

Kociemba's fix was a lookup table. For any position, the table gives the exact number of moves still needed to reach G1. With it, the search for a short phase 1 solution barely searches at all: at each of the 12 steps you try the 18 moves, look each result up, and keep the one with the lowest number. That is 18 times 12, or 216 positions looked at, instead of a quadrillion.

Because phase 1 is so cheap, the second phase can use a looser estimate and still finish in reasonable time on a modern computer. The article names the search method in both phases: iterative deepening A*, or IDA*, which searches every move list up to a set length, then tries one move longer, until one works.

Why the solutions come out so short

The limits add up to 12 plus 18, or 30 moves. In 1995 Reid proved a tighter bound using these two groups: every position can be solved in at most 29 face turns, or 42 quarter turns. Silviu Radu brought the quarter turn figure to 40 in 2005. If face turns and quarter turns are new terms, our post on the half turn and quarter turn metrics explains both.

In practice the program does better than its bound. It does not stop at the first phase 1 solution. It also tries slightly longer phase 1 solutions, and checks whether any of them leaves a much shorter phase 2. Wikipedia says this usually gives much shorter solutions overall, typically 20 moves or less.

The catch is that the answer is short but not always the shortest. The method makes no promise of the best solution. You can turn it into one that does, by running phase 1 alone until the cube is solved, but that takes far more computing. Kociemba was later one of the four people behind the 2010 proof that every position can be solved in at most 20 face turns, told in our post on God's number.

Counting your options 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 game has no solved state, so there is no two-phase solver for it. But Kociemba's first step, counting what you are allowed to do, works on any puzzle. Count the moves on the keyboard the same way:

• Slides: the four arrow keys (or W, A, S and D). Each one counts a move.
• Twists: keys 1 to 6, each one way, or the other way with Shift. That is 6 times 2, or 12 twists, and each counts a move, adds a new tile and scores nothing.
• Turns: Shift with an arrow key turns the whole cube. As the first game tip says, "Turning is free."

So each step offers 16 moves that count and 4 turns that do not. Like Kociemba's table, the free turns let you look before you choose: turn to see each face, then pick the one counted move that does the most, usually a slide that merges.

Frequently asked questions

What is Kociemba's algorithm?

It is a two-phase method for solving a cube puzzle by computer. Phase 1 brings the cube to domino reduction, and phase 2 solves it using only U and D turns and half turns of the other faces.

How many moves does Kociemba's algorithm use?

Usually 20 or fewer for a random cube. Michael Reid proved its two groups can solve every position in at most 29 face turns.

Does Kociemba's algorithm find the shortest solution?

Not in its two-phase form: it finds a short solution fast, with no guarantee it is the shortest. Run as a one-phase solver it can find the shortest, but it needs much more computing.

How is it different from Thistlethwaite's algorithm?

Thistlethwaite used four phases and three stops in between. Kociemba uses two phases and one stop, domino reduction, which is the same group as Thistlethwaite's G2.

Get started

Kociemba's algorithm is fast because it knows exactly how far each choice leaves it from the next stop. On a 2048 cube you can do a small version of that: turn the cube for free, look at every face, then spend your counted move where it does the most.

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