Tower of Hanoi

How to play

Every disc on the board starts on peg 1, widest at the bottom, narrowest on top. Your job is to rebuild that same stack on peg 3. Two restrictions make it a puzzle rather than a chore: you may only carry one disc at a time, and you may only place a disc on an empty peg or on a disc wider than itself. A wide disc can never rest on a narrow one, which means peg 2 is not a parking space you can fill carelessly — it is a working area you have to keep in a usable state.

The counter marked Minimum shows the shortest route that exists for the number of discs you picked. It is not a target the board invents; it is a proven figure, and no sequence of legal moves can beat it. Your own counter sits beside it, so you always know how far off the ideal line you are. Finishing at all is the first goal. Finishing at exactly the minimum is the real one, and the board tells you plainly when you manage it.

Controls

• Click or tap a peg to lift its top disc. Click a second peg to drop it there. If you change your mind, click the same peg again and the disc goes back.
• Drag the top disc from one peg to another if you prefer a continuous gesture. It works with a mouse and with a finger, and releasing away from any peg simply cancels.
• Keys 1, 2 and 3 choose pegs in the same lift-then-drop rhythm, so the whole puzzle can be solved without pointing at anything. Esc puts a lifted disc back.
• Undo last move returns the last disc to the peg it came from and takes one off the counter, which keeps the number honest.
• Restart rebuilds the starting stack at the current size. The disc buttons from 3 to 8 change the size and start a fresh round.

Each peg carries a spoken description for screen readers that names the peg, how many discs it holds and which disc is on top, and it is rewritten after every move.

The method: solve it by describing it

Most people meet this puzzle and start pushing discs around hoping a pattern appears. It does, but there is a faster route to it, and the trick is to stop thinking about discs and think about stacks.

Suppose you want to move a stack of five discs from peg A to peg C, with peg B free. Forget four of them for a second. The bottom disc, disc 5, can only reach peg C if peg C is empty and nothing sits on disc 5. So before disc 5 can move, the four discs above it must already be somewhere else — and the only somewhere else is peg B, stacked in order. That gives you the whole plan in three lines: move the top four from A to B, move disc 5 from A to C, then move the top four from B to C.

The clever part is that the first and third lines are the same problem again, one disc smaller, with the pegs playing different roles. Moving four discs from A to B means moving three from A to C, putting disc 4 on B, then bringing those three from C to B. Keep unwrapping and you eventually reach a single disc, which needs a single move. That is the recursive solution, and it is why this puzzle turns up in programming courses so often: it is the shortest honest example of a problem that contains smaller copies of itself.

Counting the moves falls out of the same description. If T(n) is the number of moves for n discs, then T(n) = 2 × T(n−1) + 1: two smaller transfers plus the one big disc. With T(1) = 1, the sequence runs 1, 3, 7, 15, 31, 63, 127, 255 — always one less than a power of two, or 2ⁿ − 1. Eight discs therefore need 255 moves, and every extra disc roughly doubles the work.

The practical rule at the board

Recursion explains the solution but is awkward to hold in your head while your hand is moving. There is a mechanical version that produces exactly the same optimal sequence, and it fits in two sentences.

First: alternate. On every odd-numbered move you move the smallest disc, disc 1. On every even-numbered move you do not touch disc 1 — and with disc 1 ruled out, exactly one legal move remains on the board, so you cannot go wrong. Second: disc 1 always travels in the same direction around the three pegs, and which direction depends on parity. With an odd number of discs, disc 1 goes 1 → 3 → 2 → 1 → 3 and so on. With an even number, it goes 1 → 2 → 3 → 1 → 2. Pick the direction on your first move and never reverse it.

That is the whole optimal strategy. Try it with three discs, where the sequence is short enough to check by eye: disc 1 to peg 3, disc 2 to peg 2, disc 1 onto disc 2, disc 3 to peg 3, disc 1 to peg 1, disc 2 onto disc 3, disc 1 home. Seven moves, which is 2³ − 1, and the smallest disc walked 1 → 3 → 2 → 1 → 3 exactly as promised.

Where the puzzle came from

Édouard Lucas, a French mathematician, put this puzzle on sale as a toy in 1883 under the pen name N. Claus de Siam — an anagram of Lucas d'Amiens, after his birthplace. The set came with a story: in a temple at Benares, priests were said to be moving sixty-four golden discs between three diamond needles under the same two rules, and the world would end when the last disc was placed. The legend was part of the packaging, invented to sell the puzzle, and it did its job well enough that the tale is still repeated over a century later.

It is also, accidentally, a good arithmetic lesson. Sixty-four discs would need 2⁶⁴ − 1 moves, a figure twenty digits long: 18,446,744,073,709,551,615. Working steadily at one move a second, never sleeping and never making a mistake, the priests would need roughly 585 billion years — over forty times the current estimated age of the universe. The doubling is gentle at the start and merciless later: the jump from seven discs to eight costs you 128 extra moves, and the jump from sixty-three to sixty-four would cost more moves than every move made in every game of this puzzle ever played.

Questions players ask