Four-Peg Tower of Hanoi

Play four-peg Hanoi

The board above is the four-tower puzzle, and it plays exactly like the three-tower one: drag a disk, or click a tower to lift its top disk and click another to drop it. Keys 1 to 4 reach the four towers. Undo, the move timeline, hints and Auto Solve all work the same way — and from the starting stack, Auto Solve plays the proven shortest solution. From a position you have scrambled it plays a short route instead; the reason is below.

It is worth playing three disks on both boards before reading any further. On three towers the shape of the solution is forced and you can feel it; here there is a decision on the very first move, and that decision is the whole subject of this page.

What changes with a fourth tower

Nothing in the rules. One disk at a time, only the top disk of a tower, never a larger disk onto a smaller one, and the goal is still the whole stack on the far tower. The only difference is that there are now two spare towers instead of one.

That sounds minor and is not. On three towers you never choose anything: to move the largest disk you must first pile every smaller disk onto the single spare, because there is nowhere else for them to go. The forced move is what makes the count 2ⁿ − 1 — every added disk means solving the smaller stack twice, plus one move for the disk itself, which is why the count doubles.

With two spares, the small disks can be split. Some go on one spare, some on the other, and the expensive part of the job is then done on a shorter stack. The doubling breaks, and the numbers stop being astronomical: fifteen disks fall from 32,767 moves to 129.

The Frame–Stewart algorithm

The method is named after the two people whose solutions the American Mathematical Monthly printed side by side in 1941. B. M. Stewart had set the problem there himself in 1939, for any number of pegs, and J. S. Frame was one of the readers who answered it. They arrived at the same idea.

The idea is a split. Pick a number k, and then:

The middle step is the part that repays the attention. Once the k smallest disks are parked, the tower holding them cannot be used for anything else — so the remaining disks have exactly three towers to work with, which is the ordinary puzzle, at a cost of 2^n−k − 1. The first and last steps are the four-tower problem again on k disks, so the whole thing is a recurrence:

FS(n) = the smallest value of 2·FS(k) + 2^n−k − 1, trying every k from 1 to n − 1, starting from FS(1) = 1.

The k that wins is a genuine trade. Parking more disks makes the cheap steps dearer and the expensive step much cheaper, and the balance shifts as n grows: the best split for six disks is 3, for ten it is 6, and for fifteen it is 10. There is no formula for it — you try every value and keep the smallest total, which is exactly what the solver on this page does before it plays a move.

How many moves it takes

The left column is the puzzle everyone knows; the right is the same disks with one more tower. The last column is the winning split — how many of the smallest disks get parked before the rest cross.

Read down the two middle columns and the difference is not a discount, it is a change of kind. The three-tower column doubles every row — that is what an exponential does, and it is why sixty-four disks outlast the sun. The four-tower column climbs in steps: it holds still for a while, then jumps. Twenty disks are 289 moves — under five minutes at a move a second, against twelve days of non-stop play on three towers.

The counts are not a formula and cannot be simplified into one, but they are not mysterious either: they are OEIS A007664, and they are what the recurrence above produces when you actually run it.

Seventy-three years unproven

Here is the part of this story that surprises people. Frame and Stewart published in 1941. Everyone agreed the method looked optimal. Computer searches confirmed it for every size anyone could check. And for seventy-three years nobody could prove that no shorter solution existed.

The difficulty is exactly the freedom that makes four towers fast. On three towers the proof is short because every move is forced: there is only one place the small disks can go, so you can reason about all solutions at once. On four towers a solution might in principle shuffle disks between the two spares in some clever pattern nobody thought of, and ruling out every such pattern is a different order of problem.

Thierry Bousch closed it in 2014, for four pegs. So the numbers in the table are not "the best anyone has found" — they are the shortest solutions that exist. For five towers and more, the same algorithm generalises and is still only conjectured to be optimal, which makes this one of the tidiest open problems in recreational mathematics: everybody knows the answer, and only one case of it has been proved.

The board above therefore plays a proven optimum from its starting stack. Scramble it yourself and the solver still finds a short route, but no formula or fast method is known for the true shortest distance between two arbitrary four-tower positions. A brute-force search could find it, but at fifteen disks that means labelling over a billion positions — too much for a page to do while you play — so the board says how many moves its solver would take rather than claiming a gap it cannot justify.

Questions about four-peg Hanoi