Tower of Hanoi — Recursive Puzzle Logic

1 2 3 4 5 6 7

difficulty levels — click green to claim

> TOWER OF HANOI

tower-of-hanoi difficulty: 2–3 also known as: Tower of Brahma

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 2ⁿ − 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 1: disk 1 (smallest) → peg C
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)

# Python (recursive):
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

← Back to all ciphers