Tower of Hanoi Formula

A tower of n disks can be moved in 2ⁿ − 1 moves, and no fewer. Here is where the number comes from, and why it cannot be beaten.

Minimum moves = 2ⁿ − 1

Where 2ⁿ − 1 comes from

Let T(n) be the fewest moves for n disks. To move the biggest disk you must first get all the others out of the way, onto the third peg: that costs T(n − 1) moves. Then the big disk moves once. Then the smaller disks have to be carried on top of it, which costs T(n − 1) again. So

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

That gives 1, 3, 7, 15, 31, … Each number is one less than a power of two. To see that it always is, add 1 to both sides: T(n) + 1 = 2 · (T(n − 1) + 1). The quantity T(n) + 1 doubles with every disk and starts at 1, so it equals 2ⁿ, and T(n) = 2ⁿ − 1.

Why you cannot do better

Sooner or later the largest disk has to move. At that moment it is alone on top of its peg, the peg it is going to is empty, and so every smaller disk must be sitting on the third peg: a full tower of n − 1 disks has been moved, which took at least T(n − 1) moves. After the largest disk has moved, those n − 1 disks have to be moved again, at least T(n − 1) more moves. So T(n) can never be less than 2 · T(n − 1) + 1, and the method above achieves exactly that.

A formula for any position

The same reasoning gives the fewest moves from any position, which is what the solver uses. Go through the disks from the largest to the smallest, keeping a “goal peg” for the disks you have not looked at yet (at first, the peg you want the tower on):

• If the disk is already on the goal peg, it costs nothing and the goal peg stays the same.
• Otherwise it has to move once, and before that every smaller disk must be gathered on the third peg. The disk costs 2^k moves, where k is the number of disks smaller than it (the k smaller disks are carried across in 2^k − 1 moves, and the disk itself moves once). The goal peg for the smaller disks becomes that third peg.

Add up the costs. Example, four disks with disks 4 and 1 on peg 1, disk 3 on peg 2 and disk 2 on peg 3, goal peg 3:

For three pegs this is exact. We checked it against a brute-force search over every position of up to seven disks.

How long would a big tower take?

The numbers grow very quickly. At one move per second, with no mistakes and no breaks:

The 64-disk row is the one in the old legend of the monks who move a tower of 64 golden disks until the world ends. It takes exactly 18,446,744,073,709,551,615 moves.

More pegs, fewer moves

A fourth peg lets you park disks and saves a great many moves. The usual method, named after Frame and Stewart, splits the tower at the best point k: move the top k disks aside using all the pegs, move the remaining n − k disks with one peg fewer, then bring the k disks back. The 4-peg column in the table above comes from that method. We checked each number from 1 to 10 disks by searching every position, and you can try it on the board: choose 4 pegs.

Where next

Learn how to solve it by hand, or play it now.