> TOWER OF HANOI
The idea in plain English: Three pegs. A stack of disks on the left peg, largest at the bottom, smallest at the top. Your goal: move the entire stack to the right peg. You can only move one disk at a time, and you can never place a larger disk on top of a smaller one. That's it — yet the optimal solution requires 2n − 1 moves for n disks.
Why this really exists: The Tower of Hanoi is a classic recursion exercise in computer science. Any algorithm that can solve this is also demonstrating the power of recursion — a function that calls itself with smaller and smaller sub-problems until it reaches a base case. It appears in software engineering interviews, algorithm textbooks, and as a benchmark for planning in AI.
▸ Concrete Example: 3 Disks
For 3 disks, the optimal solution takes 2³ − 1 = 7 moves:
Move 2: disk 2 → peg B
Move 3: disk 1 → peg B (on top of disk 2)
Move 4: disk 3 → peg C
Move 5: disk 1 → peg A
Move 6: disk 2 → peg C (on top of disk 3)
Move 7: disk 1 → peg C (on top of disk 2)
Done! All 3 disks on peg C.
▸ How to Solve (Recursive Algorithm)
1. Move n−1 disks from peg A to peg B (using peg C as spare)
2. Move the largest disk (n) from peg A to peg C
3. Move n−1 disks from peg B to peg C (using peg A as spare)
def hanoi(n, source, target, spare):
if n == 0: return
hanoi(n−1, source, spare, target)
print(f"Move {source} → {target}")
hanoi(n−1, spare, target, source)
hanoi(3, 'A', 'C', 'B')
💡 The puzzle answer is the single largest disk moved: the letter (A–G) corresponding to the largest disk's final move destination.
▸ Real-World Applications
- Recursion training: Every CS student learns recursion by implementing this puzzle
- AI planning: Used as a benchmark for AI search algorithms (A*, BFS, IDDFS)
- Backup rotation: The Tower of Hanoi backup strategy rotates tapes using the same optimal pattern
- Neuropsychology: Used in cognitive tests to assess planning ability and frontal lobe function