Tower of Hanoi
PuzzleHow to Play
Goal: Move the entire stack of disks from the left peg to another peg in as few moves as possible. The fewest moves possible is 2n − 1, where n is the number of disks.
Controls: Tap or click a peg to lift its top disk, then tap or click the peg you want to drop it on. You can also drag a disk from one peg to another.
Rules: Move only one disk at a time, take only the top disk of a stack, and never place a larger disk on top of a smaller one. Use Undo to take back a move, Reset to restart the current puzzle, or Auto-Solve to watch the optimal solution.
About the Tower of Hanoi
The Tower of Hanoi was invented by the French mathematician Édouard Lucas in 1883, wrapped in an invented legend about temple priests moving 64 golden disks as the world's lifespan ticks away. The math behind the legend is real: at one move per second, 64 disks would take 2^64-1 moves, around 585 billion years, comfortably outlasting the sun.
Three pegs, a stack of disks, and two rules: move one disk at a time, and never place a larger disk on a smaller one. The optimal solution takes exactly 2^n - 1 moves for n disks and follows a perfectly recursive rhythm, which is why the puzzle appears in every computer science course on recursion, and why it feels so satisfying once the pattern clicks.
Solving Hanoi like a machine
- Move the smallest disk every other turn, on a strict cycle of pegs (left-middle-right for odd disk counts, reversed for even).
- On the turns between, make the only legal move that does not involve the smallest disk, there is always exactly one.
- Think recursively: to move n disks, move n-1 aside, move the big disk, then bring the n-1 back on top.
- To finish on the right peg with an odd number of disks, send the first disk right; with an even number, send it middle.
- Count against perfection: 3 disks = 7 moves, 4 = 15, 5 = 31. If you used more, the smallest-disk cycle broke somewhere.
FAQ
What is the minimum number of moves?
Exactly 2^n - 1 for n disks: 7 moves for three disks, 15 for four, 31 for five. The doubling is the puzzle's soul, every extra disk requires solving the whole previous puzzle twice, plus one move, which is recursion made physical.
Is there a mechanical method that always works?
Yes. Alternate between (1) moving the smallest disk one peg along a fixed direction, wrapping around, and (2) making the only other legal move on the board. Follow that loop and you produce the optimal solution without ever thinking ahead, eerie the first time you try it.
Why do computer science courses love this puzzle?
Because its cleanest solution is self-referential: 'move n disks' is defined in terms of 'move n-1 disks'. It is the canonical first recursion example, small enough to trace by hand, deep enough to show why recursive definitions terminate.
Does the first move matter?
Completely. With an odd number of disks, move the smallest disk to the target peg first; with an even number, to the spare peg. Get that one choice wrong and the optimal path now finishes on the wrong peg, costing you extra moves to repair.
