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.
Click a peg to pick up its top disk, then click where to put it. Number keys work too.
It solves from wherever the disks are now, always choosing a move on the shortest path to the goal.
To move a tower of n disks from peg A to peg C:
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.
| Disks | Fewest moves | At 1 move per second |
|---|
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.