Tower of Hanoi

How to solve the Tower of Hanoi

The puzzle obeys one neat recursive idea. To move a stack of four disks to the far peg, first move the three disks above the biggest one onto the spare peg, then slide the biggest disk to its destination, then move the stack of three on top of it. Moving three disks is the same problem one size smaller, and moving two is smaller still, all the way down to a single disk you simply pick up. Every layer repeats the same instruction: to free any disk, park the entire tower above it on the peg you are not using.

Watch it happen with three disks. Call the pegs left, middle and right, number the disks 1 to 3 from smallest, and start everything on the left. Disk 1 goes to the right. Disk 2 to the middle. Disk 1 onto disk 2. Disk 3, finally free, crosses to the right. Now rebuild: disk 1 back to the left, disk 2 onto disk 3, disk 1 on top. Seven moves, none wasted. The four-disk solve is that entire dance performed once to clear the way, one move of disk 4, then the dance again on top of it: fifteen moves. Five disks need 31 and six need 63; each extra disk doubles the work and adds one more move.

A rule that plays perfectly without thinking

• The smallest disk moves on every other turn, and always travels in the same direction around the three pegs.
• For an even number of disks, cycle the smallest disk one peg to the right each time, wrapping around; for an odd number, cycle it to the left.
• On the turns when you are not moving the smallest disk, there is only ever one other legal move: make it.
• Never place a larger disk on a smaller one; a disk may go only onto a bigger disk or an empty peg.
• Repeating smallest-disk, then the only-other-move, then smallest-disk again solves the tower in the minimum number of moves with no forward planning at all.

The binary machinery underneath

Number the moves of a perfect solve from 1 and something elegant appears: the binary form of the move number names the disk that moves. Odd turns always move disk 1. Turns divisible by 2 but not by 4 move disk 2; divisible by 4 but not 8, disk 3; and so on, the same rhythm as the depth marks on a ruler. The whole optimal solution is a binary counter acting itself out, which is one reason computer-science courses treat this puzzle as the first recursion exercise. Draw every reachable position as a dot, connect positions one legal move apart, and a second surprise appears: the map of the puzzle is the Sierpinski triangle, the famous fractal, with the three fully stacked positions sitting at its corners. Add a fourth peg and everything changes again; the Frame-Stewart method from 1941 solves that version far faster, and proving it truly optimal took until 2014.

Where move counts leak

Two habits ruin scores. The first is shuttling the smallest disk back and forth between the same two pegs, which burns turns without changing the position; in a perfect solve disk 1 always travels one consistent direction around the pegs, so if yours keeps reversing, moves are leaking. The second is freeing a big disk before its landing spot is ready: sliding the bottom disk across only helps when the target peg is empty, so consult the recursion about where the tower above it should be parked first. If your four-disk games keep finishing above fifteen, replay with the smallest-disk rule and note the first move where your path differs. That move is the leak.

Lucas, Brahma and the end of the world

The Tower of Hanoi was created in 1883 by the French mathematician Edouard Lucas, who sold it as a toy under the pseudonym N. Claus de Siam, professor at the college of Li-Sou-Stian: unscramble the names and you get Lucas d'Amiens and his own school, Saint Louis. A year later the science writer Henri de Parville dressed the puzzle in the myth everyone now repeats, priests in a great temple forever transferring a tower of 64 golden disks, the world ending when the last disk lands. The arithmetic keeps the myth safely fictional. Sixty-four disks need two multiplied by itself sixty-four times, minus one: over eighteen quintillion moves. At one move per second that is more than 585 billion years, dozens of times the current age of the universe.

The puzzle leads a second life in the lab. Psychologists use tower tasks, this one and its cousin the Tower of London, to measure planning and working memory, because solving them means holding a stack of sub-goals in your head, which is exactly what the recursion asks of you.