Tower of Hanoi: Solution, Formula (2^n - 1) and the Maths Behind It

By Dawid Siedlarz · · 9 min read

Play Tower of Hanoi free →

Short answer: the Tower of Hanoi with n discs and three pegs needs at least 2n − 1 moves: 7 for 3 discs, 15 for 4, 31 for 5, 127 for 7. To solve it, move the top n − 1 discs to the spare peg, move the largest disc to the target, then move the n − 1 discs on top of it, which is the same puzzle again, only smaller. The quick rule: move the smallest disc every second turn, always round the pegs in the same direction, and in between make the only other legal move. The puzzle was invented by Edouard Lucas in 1883.

The Tower of Hanoi looks like a toy: three pegs and a stack of discs that get smaller towards the top. The goal is to move the whole stack to another peg, one disc at a time, never putting a bigger disc on a smaller one. With 3 discs it takes a minute. With 7 it takes concentration. With 64 it would outlast the Sun. Behind this simple puzzle sits one of the cleanest examples of recursion in mathematics, a hidden binary counter and a fractal. This guide shows the solution first, then the maths.

The rules

  1. There are three pegs. All discs start on one peg, the largest at the bottom.
  2. You move one disc at a time: the top disc of any peg goes onto another peg.
  3. A disc may never be placed on a smaller disc.
  4. The puzzle is solved when the whole tower stands on the target peg in the same order.

In our Tower of Hanoi the tower starts on the left peg and must end on the right one. Easy has 3 discs, Medium 5 and Hard 7, there is no time limit, and the game shows the fewest possible moves next to your count.

The 3-disc solution, move by move

Call the pegs A (start, left), B (middle) and C (target, right), and the discs 1 (small), 2 (medium) and 3 (large). The shortest solution is 7 moves:

MoveDiscFrom → toAfter the move (A | B | C)
11A → C3 2 | – | 1
22A → B3 | 2 | 1
31C → B3 | 2 1 | –
43A → C– | 2 1 | 3
51B → A1 | 2 | 3
62B → C1 | – | 3 2
71A → C– | – | 3 2 1

Look at the shape of it. Moves 1 to 3 move a tower of two discs from A to B. Move 4 moves the big disc. Moves 5 to 7 move the two-disc tower from B onto it. That structure is the whole secret.

Two ways to solve any tower

1. The recursive method (think in towers)

To move a tower of n discs from the start peg to the target peg:

  1. Move the top n − 1 discs from the start to the spare peg (using the target as the helper).
  2. Move the largest disc from the start to the target.
  3. Move the n − 1 discs from the spare peg onto the target (using the start as the helper).

Steps 1 and 3 are the same puzzle with one disc fewer, so you apply the same three steps to them, and so on down to a single disc, which you simply move. This is why the Tower of Hanoi is the standard first example of recursion in programming courses: a function that solves a problem by calling itself on a smaller version of it. It is also the best way to understand a position: ask which is the largest disc not yet on its target, and everything above it must go to the third peg.

2. The iterative method (no planning needed)

  1. On every odd move (1st, 3rd, 5th...), move the smallest disc one step round the pegs, always in the same direction. With an odd number of discs the direction is A → C → B → A (start, target, middle); with an even number it is A → B → C → A.
  2. On every even move, make the only legal move that does not touch the smallest disc. There is always exactly one.

Follow these two rules and you will finish in the minimum number of moves without thinking ahead. It is how most people solve 7 discs. The recursive method is the one that teaches you why it works.

Why the minimum is 2n − 1

Let T(n) be the fewest moves for n discs. The largest disc has to move at least once. At the moment it moves, it must be alone on its peg and the target peg must be empty, so all the other n − 1 discs must be stacked on the third peg: that took at least T(n − 1) moves. After it moves, those discs still have to get on top of it: at least T(n − 1) moves again. So

T(n) = 2 × T(n − 1) + 1, with T(1) = 1.

That gives 1, 3, 7, 15, 31, 63, 127... and each number is one less than a power of two: T(n) = 2n − 1. The recursive method achieves exactly this number, so it is optimal, and in fact the shortest solution is unique: there is only one way to do it in 2n − 1 moves.

How fast it grows

DiscsFewest movesAt one move per second
377 seconds
41515 seconds
531about half a minute
663about 1 minute
7127about 2 minutes
8255about 4 minutes
101,023about 17 minutes
201,048,575about 12 days
324,294,967,295about 136 years
6418,446,744,073,709,551,615about 585 billion years

Each added disc doubles the work. This is what exponential growth looks like, and it is why the puzzle is used to teach it.

Hidden patterns

Which disc moves when: a binary counter

In the shortest solution, disc k (counting from the smallest) moves exactly 2n−k times. The smallest disc makes half of all the moves (rounded up), the largest moves once, exactly in the middle: after 3 moves with 3 discs, after 15 with 5, after 63 with 7.

There is an even neater rule. Write the move number in binary and count the zeros at the end: move 1 is 1 (no zeros, disc 1), move 2 is 10 (one zero, disc 2), move 3 is 11 (disc 1), move 4 is 100 (two zeros, disc 3). The disc that moves is always one more than the number of trailing zeros. So the solution is literally a binary counter counting from 0 to 2n − 1, and you can tell from the move number alone which disc to move. The same sequence of discs (1, 2, 1, 3, 1, 2, 1...) is the order in which bits change in a Gray code, a way of counting in binary where only one bit changes at each step.

A fractal: the Sierpiński triangle

Every disc can be on any of the three pegs, and the order on each peg is forced (largest at the bottom), so there are exactly 3n legal positions: 27 for 3 discs, 2,187 for 7. Draw each position as a dot and connect two dots when one legal move leads from one to the other. The picture you get is a triangle made of three smaller triangles, each made of three smaller ones: a version of the Sierpiński triangle. The three corners are the positions with the whole tower on one peg, and the shortest solution runs straight along one side.

Our three levels are prime numbers

Numbers of the form 2n − 1 are called Mersenne numbers. Some are prime, and the minimum move counts of our three levels all are: 7, 31 and 127. The last one has a link to the puzzle's inventor: in 1876 Edouard Lucas proved that 2127 − 1, a 39-digit number, is prime. It remained the largest known prime for 75 years, until 1951, and the Lucas-Lehmer test built on his method is still used to find record primes today.

Four pegs: a much harder problem

With a fourth peg the tower can be moved much faster, because there are more places to park discs. The puzzle with four pegs was published by Henry Dudeney in The Canterbury Puzzles (1907) as "The Reve's Puzzle". In 1941 J. S. Frame and B. M. Stewart independently gave a method: move some top discs to one spare peg using all four pegs, move the rest with the three remaining pegs, then move the first group back on top. Choosing the best split gives these move counts:

Discs3 pegs4 pegs (Frame-Stewart)
375
4159
53113
66317
712725
825533
101,02349

For more than 70 years nobody could prove that this method was the best possible for four pegs. Thierry Bousch finally proved it in 2014. For five or more pegs it is still an open question, which is remarkable for a puzzle sold as a toy in 1883.

History: Lucas, a pen name and a legend

The puzzle appeared in Paris in 1883, credited to "Professor N. Claus de Siam" of the "College of Li-Sou-Stian". Both are anagrams: N. Claus de Siam is Lucas d'Amiens, and Li-Sou-Stian is Saint Louis, the Lycée Saint-Louis where Edouard Lucas taught mathematics. Lucas (1842–1891) is also known for the Lucas numbers, a cousin of the Fibonacci sequence, and for a four-volume collection of mathematical recreations.

The puzzle came with a legend: in a great temple, priests move a tower of 64 golden discs between three diamond needles, following the same two rules, and when they finish the world will end. As the table above shows, even at one move per second, with no mistakes, they would need about 585 billion years, more than 40 times the age of the universe. The legend was part of Lucas's exotic packaging, like the name Hanoi, not an ancient tradition.

Where the Tower of Hanoi is used today

  • Teaching programming. It is the classic exercise for recursion; the three-step method above translates into a function a few lines long.
  • Teaching maths. Recurrence relations, proof by induction, exponential growth and binary numbers all appear in one puzzle.
  • Psychology. Tower tasks are used to study planning and problem solving: how far ahead a person thinks before moving. A variant called the Tower of London, introduced by Tim Shallice in 1982, is used in neuropsychological testing.
  • Backups. A "Tower of Hanoi" rotation scheme for backup tapes uses the same 1, 2, 1, 3, 1, 2, 1 pattern to decide which tape to overwrite, so the backups cover recent days densely and older periods more sparsely.

Tips for solving it in our game

  • Start on Easy and solve 3 discs with the iterative rule until it feels automatic, then switch to the recursive method on 5 discs.
  • With an odd number of discs (all our levels: 3, 5, 7), the first move is the smallest disc to the right-hand peg.
  • Check the halfway point: when the largest disc moves, every other disc must be stacked on the middle peg.
  • Never move the smallest disc twice in a row; that is always a wasted move.
  • The score is 1,000 × best moves ÷ your moves, times 1, 2 or 4 by level, so a perfect 7-disc solve scores 4,000. Taking a move back counts as a move.

If you like puzzles where planning several steps ahead pays off, try Box Pusher (see how to solve Sokoban) and the Sliding Puzzle.

Frequently asked questions

What is the minimum number of moves for the Tower of Hanoi?

With n discs and three pegs the minimum is 2 to the power of n, minus 1: 7 moves for 3 discs, 15 for 4, 31 for 5, 63 for 6 and 127 for 7. Each extra disc doubles the number of moves and adds one.

How do you solve the Tower of Hanoi with 3 discs?

With pegs A (start), B (middle) and C (target): move the small disc A to C, the middle disc A to B, the small disc C to B, the large disc A to C, the small disc B to A, the middle disc B to C, and the small disc A to C. That is 7 moves, the minimum.

What is the trick to solving the Tower of Hanoi?

Move the smallest disc on every odd turn, always round the pegs in the same direction (towards the target peg first if the number of discs is odd, towards the middle peg if it is even). On every even turn make the only legal move that does not involve the smallest disc.

How long would 64 discs take?

2 to the power of 64, minus 1, which is 18,446,744,073,709,551,615 moves. At one move per second without a single mistake that is about 585 billion years, roughly 40 times the current age of the universe.

Who invented the Tower of Hanoi?

The French mathematician Edouard Lucas, who sold it in 1883 under the pen name N. Claus de Siam, an anagram of Lucas d'Amiens. He packaged it with the legend of priests moving 64 golden discs, after which the world would end.