Tower of Hanoi: A Recursive Puzzle With a Provably Optimal Solution

The rules and the recursive insight

Three pegs, N disks of distinct sizes stacked smallest-on-top on the first peg. Move every disk to the third peg, one at a time, and never place a larger disk on a smaller one. Édouard Lucas invented the puzzle in 1883, wrapped in a legend about Vietnamese monks moving 64 golden disks. What makes it a favourite teaching example is that the optimal solution falls directly out of a recursive way of thinking about the problem rather than any clever search.

To move N disks from peg A to peg C using peg B as a spare, notice that the bottom disk cannot move anywhere until every disk above it is out of the way, and the only place N-1 smaller disks can go while leaving the bottom disk free is entirely onto the spare peg. That observation is the whole algorithm:

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);   // move top n-1 disks out of the way
  moveDisk(from, to);            // move the (now exposed) largest disk
  hanoi(n - 1, via, to, from);   // move the n-1 disks onto the largest
}
hanoi(N, 'A', 'C', 'B');

Why the move count is exactly 2^N - 1

Let M(n) be the minimum number of moves to relocate n disks. The recursion above moves n-1 disks twice (once out of the way, once onto the final peg) plus one single move of the largest disk, giving the recurrence M(n) = 2·M(n-1) + 1, with M(0)=0. Unrolling it: M(n) = 2·(2·M(n-2)+1)+1 = 4·M(n-2)+3 = ... = 2ⁿ·M(0) + (2ⁿ-1) = 2ⁿ-1. This can also be proven optimal, not just achievable, by a simple exchange argument: the largest disk must move at least once, and before it can move every other disk must already be off it and off the destination peg, which by induction takes at least M(n-1) moves - so M(n) ≥ 2·M(n-1)+1 as a lower bound too, matching the recursive construction exactly.

For N=64 golden disks, as in Lucas's legend, that is 2⁶⁴-1 ≈ 1.8×10¹⁹ moves. At one move per second, finishing would take longer than the current estimated age of the universe - the puzzle is a standard way to make exponential growth viscerally concrete, since adding just one more disk always exactly doubles the remaining work plus one move.

The move sequence has a beautiful bit pattern

Number the moves 1, 2, 3, ... up to 2ⁿ-1. Which disk moves on move k turns out to be determined purely by the binary representation of k: the disk that moves on move k is the position of the lowest set bit of k (counting from 1), i.e. one more than the number of trailing zero bits in k's binary form. Move 1 (binary 1) moves disk 1; move 2 (binary 10) moves disk 2; move 4 (binary 100) moves disk 3; move 6 (binary 110) moves disk 2 again. This gives an entirely non-recursive way to generate the same optimal solution - iterate k from 1 to 2ⁿ-1, extract the lowest set bit, move that disk in the only legal direction available to it (each disk's direction alternates cyclically among the three pegs, and for N even vs odd the smallest disk cycles A→C→B→A or A→B→C→A respectively) - and it is a nice illustration of how a purely recursive definition and a purely combinatorial bit-trick can compute exactly the same object.

Generalising: four pegs and the Frame-Stewart conjecture

Adding a fourth peg should make the puzzle strictly easier, and it does - but the optimal move count for the 4-peg version, known as Frame-Stewart numbers, was only proven correct in 2014 (by Bousch), decades after Frame and Stewart independently proposed the same recursive strategy in 1941. The idea is to move an optimally-chosen prefix of the smallest disks to a spare peg using all four pegs, move the remaining larger disks to the destination using the classical 3-peg algorithm (since one peg is now occupied by the prefix), then move the prefix back onto the finished stack using all four pegs again. Finding the optimal split point requires trying every possible prefix size and taking the minimum, but for a long time nobody could prove no smarter, non-prefix-based strategy could ever do better - a rare case of a simple children's puzzle having an open research question attached to it for over 70 years.

Frequently asked questions

Try it live

Everything above runs in your browser — open Tower of Hanoi and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.