Tower of Hanoi Solution Explained

Updated 5 October 2026 · 7 min read

The Tower of Hanoi looks simple: three pegs and a stack of discs. Yet it's one of the most famous puzzles in mathematics and computer science. This guide shows the exact solution for 3 and 4 discs, the trick that solves any size, and why the minimum number of moves is always 2ⁿ − 1.

🗼 Play Tower of Hanoi alongside this guide

The rules

1. All discs start on peg A, largest at the bottom.
2. Move one disc at a time, always the top disc of a peg.
3. Never put a larger disc on a smaller one.
4. Move the whole tower to peg C.

The 3-disc solution (7 moves)

Discs are numbered 1 (smallest) to 3 (largest).

Look at moves 1–3: they move the top two discs out of the way to B. Move 4 moves the biggest disc. Moves 5–7 move the two small discs back on top of it. That's the whole secret.

The recursive method (works for any size)

To move n discs from A to C, using B as the spare:

1. Move the top n − 1 discs from A to B (using C as the spare).
2. Move the largest disc from A to C.
3. Move the n − 1 discs from B to C (using A as the spare).

Steps 1 and 3 are just smaller Tower of Hanoi puzzles, solved the same way. This is recursion: solving a problem by breaking it into smaller copies of itself. For 4 discs you move 3 discs (7 moves), the big disc (1 move), then 3 discs again (7 moves): 15 in total.

The easy pattern (no thinking required)

If recursion feels abstract, follow this rule. It always produces the minimum solution:

• On every odd-numbered move (1st, 3rd, 5th…), move the smallest disc one peg along in a fixed direction:
  • odd number of discs: A → C → B → A → …
  • even number of discs: A → B → C → A → …
• On every even-numbered move, make the only legal move that doesn't involve the smallest disc.

Check it against the 3-disc table above: the smallest disc moves on moves 1, 3, 5 and 7, going A → C → B → A → C.

Why the minimum is 2ⁿ − 1

Let T(n) be the fewest moves for n discs. The largest disc can only move when all the other discs are stacked on the spare peg. So you must first move n − 1 discs (T(n − 1) moves), then the large disc (1 move), then the n − 1 discs again (T(n − 1) moves):

T(1) = 1
T(n) = 2 × T(n − 1) + 1

T(2) = 3,  T(3) = 7,  T(4) = 15,  T(5) = 31 …  which is 2ⁿ − 1

A neat extra fact: in the optimal solution, the smallest disc moves on every other turn, 2ⁿ⁻¹ times in total. The largest disc moves exactly once.

The algorithm in code

The recursive method translates almost word for word into code. Here it is in Python:

def hanoi(n, source, spare, target):
    if n == 0:
        return
    hanoi(n - 1, source, target, spare)   # move n-1 discs out of the way
    print(f"Move disc {n} from {source} to {target}")
    hanoi(n - 1, spare, source, target)   # put them back on top

hanoi(3, "A", "B", "C")   # prints the 7 moves

That's why the puzzle is a favourite in programming courses: a few lines of code solve a problem that feels hard by hand.

The legend of the 64 discs

When French mathematician Édouard Lucas published the puzzle in 1883, he added a story of priests moving 64 golden discs, with the world ending when they finished. With 2⁶⁴ − 1 moves at one move per second, the job would take about 585 billion years, so there's no need to worry.

🗼 Try a perfect 15-move solve with 4 discs

More puzzle guides: How to Solve Nonograms · How to Play Minesweeper · Benefits of Logic Games