Skip to content

Why the Minimum Is 2ⁿ − 1 Moves

Everyone quotes the formula. Here is why it is true — both halves of the proof, in plain steps, with a board that counts every disk's moves as it goes.

On this page
  1. Half one: 2ⁿ − 1 moves is enough
  2. Half two: no solution is shorter
  3. The shortest solution is unique
  4. How the moves divide between the disks
  5. Positions, not just moves
  6. Frequently asked questions
  7. Keep reading

A perfect game of Tower of Hanoi with n disks takes 2ⁿ − 1 moves: 7 for three disks, 1,023 for ten, eighteen quintillion for the sixty-four of the legend. The formula is quoted everywhere. The proof usually is not, which is a shame, because it is short, it needs nothing beyond careful counting, and it says something stronger than the formula does.

Write M(n) for the smallest number of moves that solves the puzzle with n disks — the best possible, over every solution anyone could ever find. The claim is the equation M(n) = 2ⁿ − 1, and it comes in two halves:

  • 2ⁿ − 1 moves is enough. There is a solution that long.
  • Fewer is impossible. Every solution is at least that long.

Half one: 2ⁿ − 1 moves is enough

This is the half everyone knows, because it is just the recursive method. To move n disks, move the n − 1 smaller disks out of the way onto the spare tower, move the largest disk, then move the n − 1 disks back on top of it. If that method takes T(n) moves, then

T(n) = 2 · T(n − 1) + 1, with T(0) = 0

and unrolling the recurrence gives T(n) = 2ⁿ − 1. The algorithm page does the unrolling step by step and checks it by induction. A method that takes 2ⁿ − 1 moves exists, so the best possible can be no worse: M(n) ≤ 2ⁿ − 1.

Half two: no solution is shorter

This is the half that is usually skipped, and the interesting one — it has to rule out every solution, including ones nobody has thought of. The trick is to watch just one disk: the largest.

It has to move. The largest disk starts on tower A and has to end on tower C, so it moves at least once.

Before it can move, every other disk is on one tower. Look at the first time the largest disk moves, from A to some tower. At that moment nothing can be on top of it, and nothing can be on the tower it is moving to — every other disk is smaller, and it cannot land on a smaller disk. So all n − 1 other disks are on the third tower. They started on A, so getting there was a complete transfer of an (n − 1)-disk tower from one tower to another. The largest disk never got in the way — it is bigger than all of them, so for the smaller disks it might as well be the floor — which means that transfer took at least M(n − 1) moves.

After it has finished moving, every other disk is on one tower. Now look at the last time the largest disk moves, onto C. The same reasoning says that at that moment all n − 1 other disks are stacked on the third tower. Afterwards they all have to end up on C, on top of it: another complete transfer, at least M(n − 1) moves more.

Nothing is counted twice. The moves before the largest disk’s first move, the largest disk’s own moves, and the moves after its last move do not overlap. Adding them up,

M(n) ≥ M(n − 1) + 1 + M(n − 1) = 2 · M(n − 1) + 1

and with M(0) = 0, the same arithmetic as before gives M(n) ≥ 2ⁿ − 1. Put the two halves together and the minimum is exactly 2ⁿ − 1.

The sentence the whole proof rests on is “all n − 1 other disks are on the third tower” — and it is true only because there is no fourth tower. Add one and the smaller disks can be split between two spares, the inequality collapses, and the answer changes completely: fifteen disks fall from 32,767 moves to 129. That is the four-peg puzzle, and the proof that its shortest solution is shortest took until 2014.

The shortest solution is unique

Now read the lower-bound argument backwards. Suppose a solution takes exactly 2ⁿ − 1 moves. Then there is no slack anywhere in the inequality, and each part has to take its minimum:

  • The largest disk moves exactly once. A second move would add at least one move the count has no room for. So it goes straight from A to C, and never visits B.
  • Before that one move, the other disks go from A to B in exactly M(n − 1) moves — a shortest (n − 1)-disk solution.
  • After it, they go from B to C in exactly M(n − 1) moves — another.

By the same argument one size down, each of those shortest (n − 1)-disk solutions is unique, and so on to zero disks. So the shortest solution is not just a solution of 2ⁿ − 1 moves: it is the solution, the only one. That is why every correct solver, every textbook and every language on the algorithm pages prints exactly the same list, and why the first move — disk 1 to C for an odd number of disks, to B for an even number — is not a matter of style.

How the moves divide between the disks

The recursion also says how often each disk moves. The largest disk moves once. Each (n − 1)-disk transfer moves disk n − 1 once, and there are two of those, so it moves twice. Each halving of the problem doubles the count, so disk k moves 2ⁿ⁻ᵏ times, and the smallest disk does half of all the work.

Adding the disks up gives the formula a second time: 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1. The board below keeps the tally as it plays.

4 disks on tower A. 15 moves to go.Step 0 of 15

Disk4321
Moves so far0000
In the whole game1248

Each disk’s moves so far against its total of 2ⁿ⁻ᵏ. The lit column is the disk that just moved. Step to the end and every column is full at once — no disk ever moves more than it has to.

Positions, not just moves

Every arrangement of the disks is a position: each disk can sit on any of the three towers, and the rule forces their order on a tower, so n disks have 3ⁿ positions. Draw each position as a point and join two points whenever one legal move turns one into the other, and the picture is a finely nested triangle, the shape known as the Sierpiński triangle, with the three full-tower positions at its corners.

The minimum-moves question is then a question about distance in that picture, and it has a clean answer: no two positions are further apart than two corners. Any legal arrangement of n disks can be turned into any other in at most 2ⁿ − 1 moves, and the start and finish of the classic puzzle are as far apart as two positions can be. From a position part-way through, the shortest route to a full tower is shorter — two thirds of a full game on average for a random position, much less for a game that was going well — and the solver finds it.

Frequently asked questions

Why is the minimum number of moves in Tower of Hanoi 2ⁿ − 1?

Two facts together. The recursive method solves n disks in 2ⁿ − 1 moves, so that many is enough. And no solution can use fewer: before the largest disk first moves, all the other disks must have been moved onto a single other tower, and after its last move they must all be moved onto it again. Each of those takes at least the minimum for n − 1 disks, which gives at least 2 · (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1 moves.

Is there only one shortest solution to the Tower of Hanoi?

Yes. In any solution of exactly 2ⁿ − 1 moves the largest disk must move exactly once, straight from its starting tower to its goal, and the moves before and after it must each be a shortest solution for n − 1 disks. Those are unique by the same argument, all the way down, so the whole sequence of moves is forced.

How many times does each disk move in the shortest solution?

Disk k, counting from the smallest as disk 1, moves 2ⁿ⁻ᵏ times. The largest disk moves once, the next twice, and the smallest disk moves 2ⁿ⁻¹ times — half of all the moves. Adding them up, 1 + 2 + 4 + … + 2ⁿ⁻¹, gives 2ⁿ − 1 again.

What is the minimum number of moves from a partly solved position?

It depends on the position, but it is never more than 2ⁿ − 1. Work from the largest disk down: a disk already on the tower it needs to reach costs nothing, and a disk that is not costs 2ᵏ⁻¹ moves, where k is its size, after which the smaller disks must gather on the third tower instead. The Tower of Hanoi solver on this site computes exactly that.

Keep reading