Tower of Hanoi

Move the stack across. Never put a bigger disc on a smaller one.

The maths Recursion, and why 2ⁿ − 1 grows so fast

Discs

No moves yet. The best possible is 7.

Moves 0 Fewest 7

Nothing lifted

How to play

Move the whole stack from the left peg to the right peg. Only one disc moves at a time, and a disc may never rest on a smaller one.

Click a peg to lift its top disc, then click another peg to put it down — or drag the disc straight across. Clicking the peg you took it from puts it back and costs you nothing. A drop that would break the rule is refused and the status line says why.

The goal peg flies a flag. Each disc that lands in its final place there gets a gold ring: in a perfect game the biggest disc lands exactly halfway through, and everything after that is the same puzzle again, one disc smaller.

Keyboard: left and right arrows move between the pegs, Home and End jump to the outer pegs, Enter or Space lifts and drops, Escape puts a lifted disc back.

Show me one move gives the best move from the position you are actually in. If you have wandered off the shortest route it says so rather than pretending you are still on it. Use it as often as you like; the Perfect ribbon is kept for a shortest solve you find on your own.

The starting position never changes, so Reset and New puzzle do the same thing here. Use the Discs control to change the size of the problem: 3 discs need 7 moves, 4 need 15, and 6 need 63. Each extra disc roughly doubles the work.

Why this is mathematics

To move n discs you first move n − 1 out of the way, move the big one, then move the n − 1 back. That self-reference is recursion, and it gives the exact answer: 2ⁿ − 1 moves. Ten discs need 1,023. Sixty-four discs need more moves than there have been seconds since the Big Bang.

More puzzles

Just for fun. Nothing here is timed, scored or saved to your account.

← All games