What are the rules of the Tower of Hanoi?

Move the whole stack from one peg to another. You may move only one disc at a time, only the top disc of a peg, and you may never place a larger disc on top of a smaller one.

What is the minimum number of moves?

For n discs the minimum is 2ⁿ − 1 moves: 7 moves for 3 discs, 15 for 4, 31 for 5, 63 for 6, 127 for 7 and 255 for 8.

Who invented the Tower of Hanoi?

The French mathematician Édouard Lucas introduced the puzzle in 1883, along with a legend about priests moving 64 golden discs.

How long would 64 discs take?

64 discs need 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves. At one move per second that is roughly 585 billion years.

Tower of Hanoi 🗼

Move the whole tower to the right-hand peg. One disc at a time, and never a big disc on a small one.

👣 Moves: 0

🎯 Minimum: 15

⏱ 0s

Tap a peg to pick up its top disc, then tap where to put it.

C (goal)

Rules of the Tower of Hanoi

All discs start on the left peg, largest at the bottom.
Move one disc at a time, always the top disc of a peg.
Never place a larger disc on a smaller one.
Get the whole tower onto the right-hand peg.

Minimum number of moves

For n discs the fewest possible moves is 2ⁿ − 1. Each extra disc doubles the work and adds one:

Discs	3	4	5	6	7	8
Minimum moves	7	15	31	63	127	255

The trick to solving it

Think recursively. To move a tower of 4 discs from A to C, first move the top 3 out of the way to B, then move the biggest disc to C, then move the 3 from B on top of it. Moving the 3 uses exactly the same idea with 2, and so on.

There's also a simple pattern you can follow without thinking about recursion:

Odd moves: move the smallest disc one peg along, always in the same direction. Go A → C → B → A… if the number of discs is odd, or A → B → C → A… if it's even.
Even moves: make the only legal move that doesn't touch the smallest disc.

Our step-by-step explanation with diagrams is here: Tower of Hanoi Solution Explained.

History and the legend

The French mathematician Édouard Lucas published the puzzle in 1883. He added a legend of priests moving 64 golden discs between three diamond needles, with the world ending when they finished. With 64 discs the minimum is 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves. At one move per second that takes about 585 billion years, far longer than the age of the universe.

Why it's used in classrooms

The Tower of Hanoi is a standard example in maths and computer science for teaching recursion, powers of two and planning ahead. Psychologists have also used versions of it in studies of problem-solving and planning. For more logic practice, try the Logic Puzzle or Minesweeper.