Korf's Algorithm: How a Computer Finds the Shortest Cube Solve

Korf's algorithm is the method Richard Korf used in 1997 to write the first program that solved randomly scrambled cube puzzles optimally, in the fewest moves possible. It searches with a technique called IDA* and cuts the search down with three lower bounds, each from a smaller puzzle hidden inside the cube. This guide explains how it works in plain words, walks through one pruning step with simple numbers, and shows why each extra move of search costs so much.

If you like to see what a single move changes, Evolved 2048 puts the 2048 puzzle on a cube you twist and turn in your browser, and counts every move you make.

What Korf's algorithm does

Wikipedia's article on optimal solutions for the Rubik's Cube lists several computer methods. The earlier ones aimed for short answers, not the shortest. Thistlethwaite's method averages about 31 moves and can never promise the best one, as our post on Thistlethwaite's algorithm explains. Kociemba's two-phase method finds short answers fast, again with no promise, as covered in our post on Kociemba's algorithm.

Korf's program was different. It always finds an optimal solution. The article says that of the ten random cubes Korf solved, none needed more than 18 face turns. The price is time: its search takes considerably longer than Kociemba's.

Korf described the method in his paper "Finding Optimal Solutions to Rubik's Cube Using Pattern Databases". Both parts of that title matter: the search, and the tables.

IDA*: searching longer and longer

Korf's own description, quoted in the article, is that IDA* "is a depth-first search that looks for increasingly longer solutions in a series of iterations, using a lower-bound heuristic to prune branches once a lower bound on their length exceeds the current iterations bound."

In plain words, the search runs in rounds:

1. Pick a move budget, say 1 move. Try every list of moves that fits.
2. If none solves the cube, raise the budget by one and try again.
3. Keep going until some list solves it.

Because the budget grows one move at a time, the first solution found is the shortest one there is. That is what makes the answer optimal. Starting from a cube C, the program first makes every cube one move away (C then F, C then U, and so on), then every cube two moves away, then three.

Done blindly, that explodes. Each round is far bigger than the one before. The trick is to stop exploring a branch the moment you know it cannot finish within the budget.

Three smaller puzzles as lower bounds

To know a branch is hopeless, you need a lower bound: a number of moves the cube needs at the very least. Korf found his in three subproblems small enough to solve exactly:

• The corners only, ignoring every edge.
• Six of the edges only, ignoring the corners and the other edges.
• The other six edges only.

As the article puts it, the moves needed to solve any of these is a lower bound for the whole cube. You cannot finish the cube without also finishing its corners. So for any position, the search can look up all three answers in tables, take the largest, and know the cube needs at least that many more moves.

These tables are the "pattern databases" in the paper's title. The article notes that Korf's, Kociemba's and Feather's methods all use IDA*. They differ in which parts of the cube their tables cover.

A worked example: pruning one branch

Here is one pruning step with simple numbers. They are made up to show the rule, not taken from a real cube.

Suppose the search is in the round with a budget of 16 moves. It has made 5 moves down one branch. It looks up the three tables for that position:

• Corners need at least 9 more moves.
• The first six edges need at least 8.
• The other six edges need at least 12.

The largest is 12, so the cube needs at least 12 more moves. Add the 5 already made and the branch needs at least 17. The budget is 16, so the search drops the whole branch and everything below it, without trying a single further move.

Now suppose the third table had said 10 instead. Then 5 plus 10 is 15, inside the budget, and the search tries each next move and checks again. Most branches get cut early this way, which is what makes an exact search possible at all.

Why each extra move costs so much

Even with pruning, the search grows fast. The article gives the branching factor for Korf's, Kociemba's and Feather's methods as about 13.35. That means a search one move deeper takes about 13.35 times longer.

Work it through. Two moves deeper is about 13.35 times 13.35, roughly 178 times longer. Three moves deeper is about 2,380 times. That is why the length of the answer matters so much. Wikipedia says a random cube is most likely solvable in 18 moves, about 67 percent of the time, and the most any position needs is 20, as our post on God's number explains.

The article also says the cube has 48 symmetries, and that optimal solvers for Korf's method use none of them, while Kociemba's optimal solver can use 16 and Feather's all 48. Using symmetry is one way the later solvers save time.

Lower bounds 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.

There is no shortest solution to search for, but Korf's lower bound is a habit you can use. Before a merge, ask: how many counted moves does this need at the very least? In one test of the game, a 16 sat on the front's middle left square and another 16 on the right face's top left square. Shift and 1 twisted the right face's 16 onto the front, above the other one, and Up merged them into a 32: two moves, no fewer. A twist counts a move and adds a new tile, while a whole-cube turn is free.

So count the least number of counted moves each merge needs, and drop the plans that cost more than they are worth, the way IDA* drops a branch. Our guide to planning three moves ahead shows a longer version of the same idea.

Frequently asked questions

What is Korf's algorithm?

It is the method Richard Korf used in 1997 to solve random cubes in the fewest moves. It runs IDA*, a search that tries longer and longer move lists, and prunes branches using lower bounds from three smaller puzzles.

Does Korf's algorithm always find the shortest solution?

Yes. Because it raises its move budget one move at a time, the first solution it finds is optimal. The cost is a much longer search than Kociemba's method.

What is a pattern database?

It is a table that gives the exact moves needed for a smaller puzzle, such as the corners alone. That number is a lower bound for the whole cube.

How many moves did Korf's random cubes need?

Wikipedia says none of the ten random cubes Korf solved needed more than 18 face turns.

Get started

Korf's algorithm wins by knowing early when a plan cannot work. On a 2048 cube you can do the same: turn the cube for free to look, count the least moves a merge needs, and skip the plans that cost too many tiles.

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