The ordinary Tower of Hanoi has three poles. So what happens if you add one pole and make it four? The rules are the same: you move the tower to another pole one disk at a time, never putting a large disk on a small one.

Just One More Pole Cuts the Moves a Lot

With one more place to put disks, moving them out of the way becomes much easier. Compare the fewest moves, and the gap grows as the number of disks increases.

Number of disksThree polesFour poles
3 disks7 moves5 moves
4 disks15 moves9 moves
5 disks31 moves13 moves
6 disks63 moves17 moves
7 disks127 moves25 moves
8 disks255 moves33 moves
10 disks1,023 moves49 moves
64 disksAbout 18.4 quintillion moves18,433 moves

With three poles, moving 64 disks takes about 584.5 billion years even at one move per second (How Many Years Would 64 Disks Take?). With four poles, though, it is 18,433 moves, or about 5 hours at one move per second. If the monks in the legend had added one pole, the world would have ended that same day.

Dudeney’s “Cheese Puzzle”

The English puzzle writer Henry Dudeney introduced the four-pole Tower of Hanoi widely. In his 1907 book The Canterbury Puzzles, he posed it as “The Reve’s Puzzle”. A reeve was the manager of a manor.

In Dudeney’s puzzle, instead of disks, eight cheeses of different sizes are moved among four stools. You must not put a large cheese on a small one. The answer is 33 moves, the same as the 8 disks in the table above.

The Frame–Stewart Method

In 1941, J. S. Frame and B. M. Stewart each published the same idea for moving a tower in few moves with four poles. To move a tower of n disks, you split it into three parts:

  1. Move the top k disks to a pole other than the destination, using all four poles.
  2. Move the remaining n − k disks to the destination using only three poles, without using the pole that has the k disks (2ⁿ⁻ᵏ − 1 moves).
  3. Move the k disks you set aside in step 1 to the destination, using all four poles.

Steps 1 and 3 are smaller versions of the same problem, so the idea of recursion applies (the algorithm article). All that is left is to choose how many disks (k) to leave on top to get the fewest moves. With 8 disks, setting aside the top 4 or 5 first gives the fewest, 33 moves.

The “Fewest” That Went Unproved for Nearly 100 Years

It was clear that the Frame–Stewart method moves the tower in few moves. But for a long time, nobody could prove that there is really no method with fewer.

With three poles, the fewest moves can be proved right away from one fact: “when you move the largest disk, all the other disks must be gathered on one pole” (the minimum-moves formula). With four poles, when you move the largest disk, the other disks can be split between the remaining two poles in any way, so the number of possible solutions suddenly explodes.

Computers checked all the arrangements, and the method had been confirmed as the fewest up to about 30 disks. Then in 2014, about 100 years after Dudeney posed the puzzle, the French mathematician Thierry Bousch proved that the Frame–Stewart method is the fewest for any number of disks. With five or more poles, it is said to remain unproved today.

You Can Try It Yourself

You can make a four-pole Tower of Hanoi by drawing four circles for the places in the cardboard version in the article on making one. See whether you can move 3 disks in 5 moves and 4 disks in 9 moves. You can feel the difference from three poles with your own hands.