Home / Brain Teasers / Tower of Hanoi

Tower of Hanoi

The Tower of Hanoi is a mathematical puzzle invented by French mathematician Édouard Lucas in 1883. You win by moving a pyramid of disks from one of three pegs to another, one disk at a time, never putting a larger disk on a smaller one.

Brain Teasers Medium 1 Player

Tower of Hanoi rules

All disks start stacked on one peg in order, largest at the bottom and smallest on top. There are three pegs, and the goal is to rebuild the same stack on a different peg.

You move one disk per turn, and only the top disk of a peg. A disk can go on an empty peg or on top of a larger disk, but never on top of a smaller one.

The puzzle is solved when the whole tower sits on the target peg in the correct size order. The minimum number of moves for n disks is exactly 2ⁿ − 1.

Tower of Hanoi strategy and tips

Recurse on the top n−1 disks

To move n disks, first move the top n−1 to the spare peg, move the largest disk to the goal, then move the n−1 stack on top of it. Every solution is this pattern nested inside itself.

Watch the smallest disk's rhythm

The smallest disk moves every other turn and always travels in the same direction around the three pegs. Keep it cycling, and fill the turns in between with the only other legal move.

There's only ever one good non-small move

On turns when you don't move the smallest disk, exactly one legal move exists between the other two pegs. Make it. There's never any guessing.

Pick the right starting direction

With an even number of disks, move the smallest disk to the spare peg first. With an odd number, move it straight to the target peg. The right first direction guarantees the minimum-move solution.

Frequently asked questions

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

For n disks the minimum is 2ⁿ − 1 moves. Three disks take 7 moves, four take 15, and ten disks take 1,023.

How long would 64 disks take?

At one move per second, 2⁶⁴ − 1 moves would take about 585 billion years. That's the number behind the legend of the priests of Brahma moving a 64-disk tower.

Can you solve Tower of Hanoi with more than three pegs?

Yes. The four-peg version is called the Reve's puzzle. It uses the Frame–Stewart algorithm and needs far fewer moves than the three-peg version.

Is there a pattern to solving it without recursion?

Yes. Move the smallest disk in one consistent direction every other turn, and make the single other legal move in between. That produces the optimal solution.