The story of the Tower of Hanoi

The Tower of Hanoi is played with three pegs and disks of different sizes. You move the disks one at a time to carry the tower from the left peg to the right. There is only one rule: never put a larger disk on a smaller one. Yet every extra disk roughly doubles the number of moves you need.

With n disks, the shortest solution is 2ⁿ − 1 moves

To move the biggest disk, everything above it must first be out of the way on another peg. That is a smaller tower-moving job, with one disk fewer. After the big disk has moved, the smaller tower has to be moved again, onto it. So the cost for n disks is “twice the cost for n − 1 disks, plus one move.” Following that through gives 2ⁿ − 1 moves: 7 for three disks, 15 for four, 31 for five, 63 for six, 127 for seven. This site's program searched for the shortest solution with 3 to 7 disks and confirmed that each one matches the formula.

Disks	Fewest moves
3	7
4	15
5	31
6	63
7	127

Now try 64 disks. At one move per second, 2⁶⁴ − 1 moves would take about 585 billion years, roughly 42 times the age of the universe (about 13.8 billion years).

A story that came with the box

The puzzle is said to have been devised by the French mathematician Édouard Lucas and sold in 1883. It came under the name “N. Claus de Siam, professor at the College of Li-Sou-Stian.” Rearranging the letters of that name is said to give “Lucas d'Amiens”, which suggests a mathematician enjoying a joke.

A tale came with the puzzle: in a temple at Benares, priests are moving 64 golden disks one by one, and when they finish, the world will end. This is a story attached to the puzzle when it was sold. No evidence has turned up that it is a genuine ancient legend. And with that 585 billion years in mind, the world seems to be safe for a while yet.

The name “Hanoi” is said to refer to the city in Vietnam, and is explained by the French interest in that region at the time.

Reading the moves as numbers

Call the smallest disk 1, the next 2, and so on. The disk you move on each turn goes 1, 2, 1, 3, 1, 2, 1, 4, … which is the same pattern as the tick lengths on a ruler. The disk for move m depends on how many times 2 divides m. Move 4, for instance: 4 is divisible by 2 twice, so it is the third smallest disk.

Here is another view. Treat each arrangement of disks as a dot, and join two dots when one move turns one into the other. With three disks you get 27 dots (3 × 3 × 3). Add disks and the picture becomes three copies of the smaller picture joined at the corners, which looks more and more like the famous Sierpinski triangle. On the puzzle page, choose 3 disks to see where you have been on that map.

How to think about it

• Watch only the biggest disk. Before it moves, gather everything above it on the peg that is not its destination.
• Moving a smaller tower is the same job again. However many disks there are, the task is “move a tower one disk smaller.”
• Move the smallest disk every other turn. In the 1, 2, 1, 3, 1, 2, … pattern, the smallest disk shows up on every second move.
• Stopping midway is fine. From any position there is a shortest way to finish.

Stuck? The Hint button on the puzzle page shows a next move, and “Play solution” plays a shortest solution through to the end.