How to Solve Tower of Hanoi — Algorithm + Iterative Shortcut
Tower of Hanoi looks intimidating but it’s actually one of the simplest puzzles to solve algorithmically. Here’s the algorithm, why it works, and how to apply it to puzzles up to 64 discs (you won’t finish, but you’ll know what to do).
The setup
Three pegs. Start: 64 discs stacked on the leftmost peg (largest on bottom, smallest on top). Goal: move all 64 discs to the rightmost peg. Rules: move one disc per move; never place a larger disc on a smaller one.
Minimum moves: 2^N – 1 where N is the number of discs. For 3 discs: 7 moves. For 5: 31. For 10: 1,023. For 64 (the Brahmin legend): 18,446,744,073,709,551,615 — about 585 billion years at one move per second.
The recursive algorithm
Suppose you can solve N-1 discs. To solve N:
1. Move N-1 discs from source to spare peg. (Recursive call.)
2. Move disc N from source to target.
3. Move N-1 discs from spare to target. (Recursive call.)
This works because the recursive calls solve smaller versions of the same problem. The base case is N=1: just move the single disc.
Why this is the minimum
Each disc must move at least once. The smallest disc must move (2^(N-1)) times. The next smallest moves 2^(N-2) times. The largest disc moves only once.
Total moves = 2^(N-1) + 2^(N-2) + … + 2^1 + 2^0 = 2^N – 1. This is the geometric series formula.
The iterative shortcut (without recursion)
Number the discs 1 (smallest) to N (largest). Number the pegs 1, 2, 3.
Rule 1: The smallest disc (disc 1) moves every other turn (odd turns).
Rule 2: Disc 1 moves in a fixed direction: clockwise (1 → 2 → 3 → 1 → …) if N is even; counterclockwise if N is odd.
Rule 3: On even turns, only one legal move exists. Make it.
Following these rules solves the puzzle in 2^N – 1 moves without recursion. Most experienced solvers use this iterative pattern.
Practical solving
In our 5-disc Tower of Hanoi, the optimal solution is 31 moves. Practice the iterative shortcut: at each step, the smallest disc moves in a fixed direction. The remaining move forces itself.
If you make a mistake (wrong direction for disc 1), the minimum moves go up. You can complete the puzzle from any valid state, but the cost rises.
Practice
Play our Tower of Hanoi. Start at 3 discs (7 moves). Move to 5 (31). Then 7 (127). Each disc count tests your algorithm execution.
