Tower of Hanoi

The Tower of Hanoi is one of the most famous mathematical puzzles ever invented. At first it looks like a simple game with rings and sticks. Very quickly, though, it turns into a lesson about patterns, recursion, powers of 2, and elegant strategy.

History first

The puzzle was created in 1883 by the French mathematician Edouard Lucas. He wrapped it in a dramatic story about monks moving a sacred tower of 64 golden discs from one peg to another, one careful move at a time. In the legend, the world ends when they finish.

That story is memorable because the puzzle grows astonishingly fast. With 64 rings on 3 sticks, the minimum number of moves is

[ 2^{64} - 1 ]

which is far beyond anything a human team could finish in ordinary time.

The rules

You have a tower of rings arranged from largest at the bottom to smallest at the top.

Your goal is to move the whole tower from the starting stick to another stick.

The rules are:

1. move only one ring at a time;
2. only the top ring on any stick may be moved;
3. never place a larger ring on top of a smaller ring.

Why pattern-lovers enjoy it

This puzzle is beautiful because each larger tower secretly contains the smaller tower inside it.

Suppose you want to move (n) rings from Stick A to Stick C.

You cannot move the largest ring until the (n-1) smaller rings are out of the way.

So the plan is always:

1. move the top (n-1) rings to a spare stick;
2. move the largest ring once;
3. move the (n-1) rings onto the largest ring.

That means the minimum move count, call it (M_n), satisfies

[ M_n = 2M_{n-1} + 1. ]

Starting from (M_1 = 1), the pattern becomes:

• 1 ring → 1 move
• 2 rings → 3 moves
• 3 rings → 7 moves
• 4 rings → 15 moves
• 5 rings → 31 moves

Each step is double the previous total, then add 1.

That is why Tower of Hanoi is such a lovely first example of recursion: a big problem is solved by solving a slightly smaller copy of the same problem.

A tiny worked example

For 3 rings, the minimum is 7 moves:

1. move the small ring aside;
2. move the middle ring;
3. put the small ring on top of it;
4. move the large ring;
5. move the 2-ring tower back on top.

So even the 3-ring puzzle already has the whole recursive structure hidden inside it.

What changes when you add more sticks?

The classical version uses 3 sticks, which is the version in the tracked practice set below.

But in the sandbox you can also try more sticks. Extra sticks often let you move the tower in fewer moves, which opens the door to richer experimentation:

• how much do extra sticks help?
• what patterns survive?
• which part of the 3-stick recurrence still feels familiar?

Why mathematicians love it

Tower of Hanoi connects several beautiful ideas:

• recursion and self-similarity;
• binary growth through the pattern (2^n - 1);
• algorithm design, because every correct solution follows a precise structure;
• mathematical storytelling, because a simple rule creates a surprisingly deep problem.

If you enjoy spotting structure, this puzzle rewards you every time you add one more ring.

Try the tracked 3-stick challenges below, then open the sandbox to design custom towers and watch the solver animate a correct solution without marking the problem as solved.