2026-10-22
Tower of Hanoi looks like a children's toy — a few disks, three pegs, one rule about never stacking a big disk on a small one. Underneath sits one of the cleanest results in recreational maths, and once you see it, the puzzle stops being trial-and-error and becomes a system you can run on autopilot.
To move a stack of n disks you first have to free the bottom disk — which means moving the n−1 above it onto a spare peg — then shift the big disk, then rebuild the n−1 stack on top. So the move count doubles every time you add a disk, plus one: M(n) = 2·M(n−1) + 1, which works out to exactly 2ⁿ − 1. Three disks take 7 moves, four take 15, ten take 1,023 — and a perfect player cannot do better. If your solve took more than the minimum, you made detours.
Here's the part most players never notice: in optimal play you don't really make decisions. Disk 1 (the smallest) moves on every other move — 1, 3, 5, 7… Disk 2 moves every 4th move. Disk 3 every 8th. Each disk moves exactly half as often as the one below it, cycling in the same repeating direction. Pick the correct starting direction for the smallest disk and the entire game is determined from move one.
Write the move number in binary and the puzzle reads it back to you: the disk that moves on move m is the position of the lowest 1-bit. Move 1 (binary 1) → disk 1. Move 4 (binary 100) → disk 3. Move 6 (binary 110) → disk 2. That's why a Hanoi board is secretly a counting machine — each disk behaves like a bit flipping on its own schedule, and the whole optimal solution is just counting from 1 to 2ⁿ − 1 in disguise.
The puzzle shipped with a story: monks moving a 64-disk golden tower, and when they finish, the world ends. Comfortingly, 2⁶⁴ − 1 moves at one per second takes about 585 billion years — roughly forty times the age of the universe. It's the best intuition pump there is for exponential growth: every disk you add doubles the work. On the site's much smaller boards, the practical takeaway is planning — trace the big disk's journey first and let the smaller ones fill in mechanically.
Try it on Tower of Hanoi — watch the rhythm of the small disk, then carry the same "halve the problem" instinct into 15-Puzzle. Or take today's board in the Daily Set.