Tower of Hanoi with 4 Pegs

Add a fourth peg and the puzzle changes completely: ten disks take 49 moves instead of 1,023. Here is how, and a board to try it on.

What a fourth peg changes

The rules are the same: one disk at a time, only the top disk, never a larger disk on a smaller one. The tower still starts on the first peg and has to end on the last. The extra peg gives you somewhere to park disks, and that saves an enormous number of moves, because every disk you can park is a disk you do not have to carry in two halves.

The four-peg version is often called Reve’s puzzle, after a puzzle in Henry Dudeney’s Canterbury Puzzles.

How many moves

The four-peg numbers grow in a pattern: from one disk to the next they go up by 1, 2, 2, 4, 4, 4, 8, 8, 8, 8, … A power of two appears as many times as its exponent plus one: once 1, twice 2, three times 4, four times 8, and so on. The three-peg numbers, by comparison, double every time.

The Frame–Stewart method

To move n disks with four pegs, pick a number k and then:

1. Move the top k disks to a spare peg, using all four pegs (the same problem, smaller).
2. Move the other n − k disks to the target peg using the three pegs that are left, the ordinary way: 2^n−k − 1 moves. The parked disks sit on the fourth peg, out of the way.
3. Move the k parked disks onto the target peg, again using all four pegs.

The cost is 2 · T(k) + 2^n−k − 1, where T(k) is the four-peg count for k disks. The method is to pick the k that makes this smallest. For five disks, k = 2 gives 2 · 3 + 7 = 13.

Where two values of k tie, the smaller is shown. We checked every number in these tables, from 1 to 10 disks, against a search of every position of the puzzle, and the board above uses that search: it is exact for these sizes. For bigger towers and more pegs the method is the best known; whether it is always optimal is a harder question.

A complete solution for 4 disks

Nine moves, where the three-peg puzzle needs fifteen. This is one of several shortest solutions; the board finds a different one if you press Solve from here. Pegs are numbered 1 to 4 from the left.

1. Disk 1: peg 1 → 2
2. Disk 2: peg 1 → 3
3. Disk 1: peg 2 → 3
4. Disk 3: peg 1 → 2
5. Disk 4: peg 1 → 4
6. Disk 3: peg 2 → 4
7. Disk 1: peg 3 → 1
8. Disk 2: peg 3 → 4
9. Disk 1: peg 1 → 4

Try it

On the board above, 4 pegs is already selected. Play it by hand and watch Fewest from here to see how you are doing, press Shuffle for a random position, or let the solver finish it. The rules of the classic version, with a worked example, are in how to solve the Tower of Hanoi, and the three-peg formula is derived on the formula page.