Tower of Hanoi: The Optimal Solution Explained

The Puzzle In One Sentence

Tower of Hanoi gives you three pegs and a stack of disks of decreasing size on the leftmost peg. Your job is to move the entire stack to the rightmost peg, one disk at a time, never placing a larger disk on a smaller one. That single rule is the entire constraint, and from it flows one of the cleanest recursive patterns in all of mathematics.

The Minimum Move Count

For n disks, the minimum number of moves is 2^n - 1. Three disks takes 7 moves. Four disks takes 15. Five disks takes 31. Six disks takes 63. The number doubles (plus one) with each added disk, which is why Tower of Hanoi escalates so quickly — by disk 10 you are looking at 1,023 moves.

You do not need to memorize this formula to solve the puzzle, but knowing it lets you check your progress: if you are 50 moves into a 5-disk run, you have used more than half your allowance and should consider restarting.

The Recursive Idea (Read This Slowly)

To move n disks from peg A to peg C using peg B as a helper:

1. Move the top n - 1 disks from A to B, using C as the helper. 2. Move the largest disk (the bottom one) from A directly to C. 3. Move the n - 1 disks from B to C, using A as the helper.

That's it. Step 1 and step 3 are the *same problem* with one fewer disk, just with the pegs relabeled. That self-similarity is what recursion captures.

Why This Is Optimal

Every solution must move the largest disk from A to C exactly once, and the largest disk can only move when all n - 1 smaller disks are stacked on B (because they cannot be on C, or the largest disk could not land there). So the minimum sequence is forced: stack n - 1 on B (which itself takes at least 2^(n-1) - 1 moves), move the big one (1 move), re-stack n - 1 onto C (another 2^(n-1) - 1 moves). Total: 2 × (2^(n-1) - 1) + 1 = 2^n - 1. There is no shortcut.

The Iterative Trick (No Recursion Required)

If recursion is not your style, there is an iterative version that produces the same optimal sequence. For any number of disks:

• On odd-numbered moves, move the smallest disk one peg clockwise (A → C → B → A, wrapping around).
• On even-numbered moves, make the only legal move that does not involve the smallest disk.

That's it. The smallest disk dances around the pegs in a fixed cycle, and every other move is forced. This is a beautiful result — the iterative algorithm is shorter to execute than the recursive one, yet produces the exact same 2^n - 1 move sequence.

Practical Tips For Solving By Hand

Work backwards from the goal. Before moving anything, picture the final state: all disks on the rightmost peg in decreasing size. Ask "what is the *last* move?" — it is the largest disk moving from A to C. For that move to be legal, all smaller disks must be on B. So your real goal is "move n - 1 disks to B", which itself has the same structure. Working backwards keeps you from getting lost.

Don't move a disk back to where it just was. A common beginner mistake is to undo the previous move because it "feels safe". This wastes a move and breaks the optimal sequence. If you catch yourself reversing, stop and re-plan.

For 4+ disks, write down the recursive plan first. A 4-disk puzzle is 15 moves; trying to hold that in your head is fragile. A 5-disk puzzle is 31 moves and is essentially impossible to track mentally on the first try. Sketching "move 3 disks to B, move 4 to C, move 3 to C" before you touch a single disk prevents mid-puzzle confusion.

The Most Common Mistake

The single most common mistake is treating the smallest disk as a "wildcard" that can go anywhere. The smallest disk is in fact the *most* constrained disk in the optimal algorithm — it moves on every odd-numbered turn, in a strict clockwise cycle. Letting it roam breaks the pattern and inflates your move count.

Summary

• Minimum moves for n disks: 2^n - 1.
• Recursive rule: move n - 1 to the helper, move the big one, move n - 1 onto the target.
• Iterative rule: smallest disk goes clockwise on odd moves; the other move is forced.
• Work backwards from the goal to plan.
• Never undo a move.
• Write down the plan for 4+ disks.

Tower of Hanoi is one of the rare puzzles where the optimal solution is also the easiest to execute — once you see the pattern. The recursive structure is so clean it is used as the canonical example in computer science courses worldwide.