Tower of Hanoi
The 1883 puzzle โ move the tower in as few moves as the maths allows.
About this puzzle
Move the whole tower to the right peg: one disk at a time, never a larger onto a smaller. Tap a peg to lift, tap another to place; the counter tracks your moves against the mathematical minimum, and your best per disk-count lives on this device.
The exponential in toy form
The minimum is always 2โฟโ1 moves โ 7 for three disks, 255 for eight โ and the doubling-plus-one recurrence is visible in play: to move n disks, move nโ1 aside, shift the big one, restack. รdouard Lucas published the puzzle in 1883 wrapped in the legend of monks moving 64 golden disks, the world ending on completion โ at one move per second that's 2โถโดโ1 seconds, about 585 billion years, which is the same exponential lesson as compound interest wearing robes. The solution has a secret rhythm worth discovering: the smallest disk moves every other turn, always circling the same direction, and the whole solution is the binary counter in disguise โ computer science teachers' favourite recursion example for 140 years. The 15 puzzle and Lights Out share the shelf.
Frequently asked questions
What's the minimum number of moves?
2โฟ โ 1 for n disks: 7 for three, 15 for four, 255 for eight. Matching it earns the perfect badge; the recurrence (move nโ1 aside, shift, restack) explains the formula.
What's the trick to solving it?
The smallest disk moves every second turn, always circling the same direction (right for even disk counts, left for odd) โ between its moves there's only ever one legal play. That rhythm IS the solution.
What's the monks legend?
Lucas's 1883 marketing: monks moving 64 golden disks, the world ending at completion. At a move per second that's 585 billion years โ the puzzle is an exponential-growth lesson in disguise.
Why do computer science courses love it?
It's the cleanest possible recursion example โ the solution literally IS the recurrence โ and it maps onto binary counting exactly.