Tower of Hanoi

The Tower of Hanoi is the 1883 mathematical puzzle invented by French mathematician Édouard Lucas. Three pegs, N disks stacked on the leftmost peg in decreasing size (biggest at the bottom). Move all the disks to the rightmost peg, one at a time, never placing a larger disk on a smaller one. The puzzle is a cornerstone of recursive algorithm teaching in computer science — and at 7+ disks it becomes maddeningly engaging.

How to play

• Click a peg to pick up its top disk (the peg highlights green).
• Click another peg to drop the disk there.
• You can never place a larger disk on a smaller one — invalid moves are rejected.
• Goal: move every disk from the leftmost peg to the rightmost peg.
• Optimal move count = 2^N – 1 (3 disks = 7 moves, 5 = 31, 8 = 255).

The recursive algorithm

The elegant solution to Tower of Hanoi is recursive. To move N disks from peg A to peg C using peg B as workspace:

1. Move the top N-1 disks from A to B (using C as workspace).
2. Move disk N (the bottom one) from A to C.
3. Move the N-1 disks from B to C (using A as workspace).

This gives T(N) = 2·T(N-1) + 1, which solves to 2^N – 1. The Auto-solve button runs exactly this algorithm.

The iterative trick (for humans)

There’s also a non-recursive method that humans can execute by hand:

• (1) Move the smallest disk one peg clockwise (for even N) or counter-clockwise (for odd N).
• (2) Make the only other legal move that doesn’t involve the smallest disk.
• Repeat until done.
• This works because the smallest disk moves once every two steps in an optimal solution.

The Tower of Brahma legend

Lucas accompanied his puzzle with a legend: monks at a temple in Hanoi were moving 64 golden disks between three diamond needles, and when they finished, the world would end. At optimal speed (1 move per second), 2^64 – 1 moves would take about 585 billion years — about 42 times the current age of the universe. So we’re probably fine.

Beginner strategy

• Visualize the recursion. Start with 3 disks and watch the pattern emerge.
• Use the auto-solve to learn. Watch the optimal sequence, then try to replicate.
• Don’t restart on small errors. Many mistakes are recoverable.
• Optimal moves vs all moves. Every disk move that ISN’T part of an optimal sequence is “wasted.” Try to play perfectly.
• Move count = 2^N – 1. Memorize: 3 disks=7, 4=15, 5=31, 6=63, 7=127, 8=255.

Computer science connection

• Standard CS teaching example. Tower of Hanoi is the canonical introduction to recursion.
• Time complexity. O(2^N) — exponential. Demonstrates how recursion can have terrible complexity.
• Stack depth. Recursive Tower of Hanoi uses O(N) stack space.
• State space. 3 pegs, N disks, total positions = 3^N. Only some are reachable.
• Graph theory. Tower of Hanoi state graph is a Sierpinski triangle.

Variants

• 4 pegs Tower of Hanoi (Frame-Stewart): with 4 pegs, the optimal move count drops dramatically.
• Circular Tower of Hanoi: moves restricted to adjacent pegs only.
• Bicolor Tower of Hanoi: disks alternating colors; specific patterns required.
• 3D Tower of Hanoi: some implementations add a third dimension.
• Reverse Tower of Hanoi: larger disks can sit on smaller ones; different rules.

Common mistakes

• Trying to plan all moves ahead. Even with 8 disks, that’s 255 moves. Plan the recursion, not individual moves.
• Moving the wrong disk. The optimal sequence has a specific rhythm. Track which disk should move next.
• Restarting too often. Most mistakes are recoverable. Continue and learn.
• Not using auto-solve to study. The optimal pattern is hard to internalize without watching it.

FAQ

• Q: How many moves for N disks optimal? A: 2^N – 1. For N=8, 255 moves.
• Q: Why use recursion? A: It’s the cleanest description of the solution. Iterative versions exist but are harder to derive.
• Q: Can the puzzle be solved without recursion in your head? A: Yes — the iterative trick lets humans solve manually without recursive reasoning.
• Q: Is the puzzle real (the monks)? A: No — it’s a folk legend Lucas invented to dramatize the puzzle.

For other logic puzzles, try 15 Puzzle, Lights Out, Sokoban, or Sudoku.