How to solve the Tower of Hanoi

The Tower of Hanoi has a beautiful secret: one simple pattern solves it perfectly, with any number of discs. Once you see it, you can solve 8 discs without a mistake.

The rules

There are three pegs and a tower of discs on the left peg, largest at the bottom. Move the whole tower to the right-hand peg. Only one disc moves at a time, only the top disc of a peg can move, and a disc can never go on top of a smaller one.

The fewest moves

With n discs, the fewest moves possible is 2ⁿ − 1. That’s 7 moves for 3 discs, 15 for 4, 31 for 5, 63 for 6, 127 for 7 and 255 for 8. Each extra disc doubles the work, plus one.

The idea behind it

To move a tower of 4 discs, you have to move the biggest disc at some point. It can only move when the other 3 are all stacked on the third peg. So: move the top 3 out of the way, move the big disc, then move the 3 back on top of it. Moving 3 discs works the same way with 2, and so on down. That’s why the count doubles with every disc.

The pattern you can actually use

1. The smallest disc moves every other turn, always going around the pegs in the same direction.
2. Which direction? With an even number of discs, the smallest disc goes left peg → middle → right → left, and so on. With an odd number, it goes left → right → middle → left.
3. On the turns in between, make the only legal move that doesn’t touch the smallest disc. There’s always exactly one.

Follow these two alternating steps and the tower moves itself, in the fewest moves possible.

The legend

The puzzle was invented by the French mathematician Édouard Lucas in 1883. He sold it with a story about a temple where priests move 64 golden discs, and when they finish, the world will end. At one move per second, 64 discs would take about 585 billion years, so there’s no rush.