Tower of Hanoi

Move the whole tower to the right-hand peg. Move one disk at a time, and never put a bigger disk on a smaller one.

Moves 0
Fewest possible 15

Click a peg to pick up its top disk, then click where to put it. Number keys work too.

Watch the computer solve it

It solves from wherever the disks are now, always choosing a move on the shortest path to the goal.

The recursive idea

To move a tower of n disks from peg A to peg C:

  1. Move the top n − 1 disks from A to B (using C as the spare).
  2. Move the biggest disk from A to C.
  3. Move the n − 1 disks from B onto C (using A as the spare).

Steps 1 and 3 are the same puzzle with one fewer disk. Each extra disk doubles the work, plus one move, so n disks need 2n − 1 moves.

How long would it take?

DisksFewest movesAt 1 move per second
About the puzzle

The French mathematician Édouard Lucas invented the puzzle in 1883 and sold it as a toy. It came with a made-up legend: in a temple, priests move 64 golden disks between three diamond needles, and when they finish, the world will end.

At one move per second with no mistakes, 64 disks take 264 − 1 = 18,446,744,073,709,551,615 moves: about 585 billion years, over 40 times the age of the universe.

The puzzle is a favorite first example of recursion in computer science: a problem solved by solving smaller copies of itself.

Four pegs: an extra peg makes the puzzle much faster (8 disks take 33 moves instead of 255), but finding the fewest moves turned out to be hard. J. S. Frame and B. M. Stewart proposed a method in 1941: park some of the small disks on one spare peg, move the rest with the three-peg method, then bring the small disks back. Nobody could prove it was the best possible until Thierry Bousch did in 2014, 73 years later. With five or more pegs, it is still an open question.