The Tower of Hanoi Explained: Rules, Recursion and the 2^n − 1 Rule

By the Happy Life Games team · Updated October 19, 2026 · 6 min read

Few puzzles pack so much into so little. The Tower of Hanoi is three pegs and a handful of disks, and it fits in your pocket. It also turns up in math and programming classes, and its basic idea sits under a whole family of modern phone puzzles. If you have ever poured colored water between tubes or spun nuts from one bolt to another, you have already played a cousin of this 140-year-old toy.

The rules in thirty seconds

You start with a stack of disks on the left peg, largest at the bottom and smallest at the top, so the stack looks like a little cone. The goal is to rebuild the same stack on another peg. Three rules apply:

1. Move one disk at a time.
2. Only the top disk of a stack can move.
3. A disk may never sit on top of a smaller disk.

The third peg is your workspace, and the size rule is what makes the puzzle hard.

Where it came from

The puzzle was published in 1883 by the French mathematician Édouard Lucas. He first sold it under the playful pen name "N. Claus de Siam," an anagram of "Lucas d'Amiens." The toy came with a legend about a temple where priests move 64 golden disks between three diamond needles, and the world ends when they finish. The story was a marketing flourish, but as we'll see, the math behind it means nobody needs to worry.

Solving it by thinking backward

The trick to the Tower of Hanoi is to stop thinking about the first move and start thinking about the biggest disk. At some point the largest disk has to travel from the starting peg to the target peg. For that single move to be legal, two things must be true at that moment:

• The largest disk has nothing on top of it, so every other disk is somewhere else.
• The target peg is empty, because nothing is allowed under the big disk except the floor.

So all the smaller disks must be stacked on the third peg. That gives the full plan for a tower of n disks:

1. Move the top n − 1 disks from the start peg to the spare peg.
2. Move the largest disk to the target peg.
3. Move the n − 1 disks from the spare peg onto the largest disk.

Steps 1 and 3 are just smaller Tower of Hanoi puzzles, so you solve them the same way. That is recursion: a problem solved by breaking it into smaller copies of itself until you reach one disk, which you can simply move.

A worked example with three disks

Call the pegs A (start), B (spare) and C (target), and the disks 1 (small), 2 and 3 (large). Following the plan:

1. Disk 1 from A to C
2. Disk 2 from A to B
3. Disk 1 from C to B. The two small disks are now parked on B.
4. Disk 3 from A to C. The big move.
5. Disk 1 from B to A
6. Disk 2 from B to C
7. Disk 1 from A to C. Done.

Seven moves. Notice that the smallest disk moves on every other turn, and it always cycles in the same direction. With an odd number of disks it goes A to C to B to A, and with an even number it goes A to B to C to A. On the turns in between there is only ever one legal move that doesn't involve the smallest disk. That gives you a handy way to solve any size of tower without keeping the recursion in your head.

Why the minimum is 2^n − 1

Let M(n) be the fewest moves needed for n disks. The recursive plan uses M(n − 1) moves, then one move, then M(n − 1) moves again, so M(n) = 2 × M(n − 1) + 1. Starting from M(1) = 1, you get 1, 3, 7, 15, 31, 63… Each number is one less than a power of two, so M(n) = 2^n − 1.

The plan isn't just one way to do it. It's provably the shortest. The argument above showed that any solution must clear n − 1 disks off the big one and later rebuild them on top of it, and each of those jobs needs at least M(n − 1) moves. Nothing can be skipped.

Doubling grows frighteningly fast. Ten disks need 1,023 moves. For the 64 disks of the legend you'd need 2^64 − 1, a little over 18 quintillion moves. At one move per second, that's roughly 585 billion years.

How color-sorting games borrow the idea

Modern sorting puzzles keep the Hanoi skeleton: several containers, a stack inside each one, and the rule that only the top item can move. What they change is the stacking rule. Instead of "smaller on larger," the rule becomes "same color on same color."

Color Rings is the closest relative. Like Lucas's disks, you lift one ring at a time, so the "move a small stack out of the way, then rebuild it" thinking carries straight over. When you need to reach a buried ring, ask yourself where the rings on top of it can go, just as you would for the big disk in the recursive plan.

Water Sort, Nut Sort and Bird Sort move whole same-color groups in one go. That makes each move more powerful, but it also means a careless pour can bury a color you needed. In Bird Sort, a full branch of matching birds flies off and the branch is freed. Because of that, finishing a color early buys you an empty workspace, much like an empty peg in Hanoi.

Lessons that carry over

• Empty containers are precious. In Hanoi the spare peg is what makes the puzzle solvable. In sorting games an empty tube or bolt plays the same role. Avoid filling it with a mixed stack unless you have a plan to empty it again.
• Work backward from the item that's hardest to reach. Find the color buried deepest and ask what has to move first to free it.
• Count your moves before you commit. The 2^n − 1 rule is a reminder that unbuilding and rebuilding a stack is expensive. A move that saves you from moving a stack twice is usually worth it.
• Use undo to explore. Every one of these games has an undo button. Trying a line and backing up is how you learn to spot opening traps.

Frequently asked questions

Can a color-sorting level have no solution?

A badly generated one could, but the levels in our sorting games are checked by a solver, so every one can be finished. If you feel stuck, you've most likely blocked yourself with an earlier move. Undo a few steps, or tap hint to see the next move.