The Tower of Hanoi, Explained

After reading this you will be able to solve the Tower of Hanoi by hand, derive the exact minimum of 2^n - 1 moves, and read the recursion that produces it move by move.

What the puzzle is

You start with a stack of discs on one of three pegs. The discs shrink as they go up, so the largest sits on the bottom and the smallest on top. Your task is to move the whole stack to another peg. Two rules bind you: move one disc at a time, and never place a larger disc on a smaller one.

The puzzle looks trivial with two or three discs and turns punishing fast. Three discs need 7 moves. Ten discs need 1023. The legend that ships with the puzzle claims monks in a temple are moving a 64-disc tower, and that the world ends when they finish. At one move per second that finish is about 585 billion years away, roughly 40 times the current age of the universe. The puzzle is a small machine for feeling exponential growth in your hands.

The hook is that the whole thing reduces to one idea repeated at every scale. To move a stack of n discs, you first move the top n-1 out of the way, move the single biggest disc, then move the n-1 back on top. That sentence is both the solution and the proof of its cost.

When it is worth studying

The Tower of Hanoi earns its place in a first course on recursion because the recursive solution is short, correct, and provably optimal, and because you can watch every step. Reach for it when you want to see three things at once: a problem defined in terms of a smaller copy of itself, a recurrence relation, and a closed-form solution that matches the recurrence exactly.

It is a poor model for almost anything physical. It says nothing about heat, populations, or chaos. Do not read the 64-disc legend as a claim about the real world. It is a way to make the number 2^{64} - 1 \approx 1.845 \times 10^{19} concrete, nothing more. If you want dynamics that do model physical spreading or feedback, the Heat equation simulator and the Logistic map bifurcation are the honest choices.

The recurrence and its closed form

Let T(n) be the minimum number of moves to shift n discs from one peg to another. The recursive strategy gives a recurrence directly. Moving the top n-1 discs costs T(n-1). Moving the largest disc costs 1. Moving the n-1 discs back costs T(n-1) again.

Here T(0) = 0 because an empty stack needs no moves. Each larger case doubles the previous count and adds one for the single big-disc move. Unrolling the recurrence gives the closed form.

You can check the algebra by substitution. If T(n-1) = 2^{n-1} - 1, then 2(2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1. The base case holds since 2^0 - 1 = 0, so induction confirms the formula for every n.

The recursion is also a proof of optimality. The biggest disc must move at least once, and before it can move, all n-1 smaller discs must sit on the single spare peg, which itself costs at least T(n-1). After the big disc moves, those n-1 discs must be rebuilt on top, another T(n-1). So no strategy can beat 2\,T(n-1)+1.

Watching the count grow

The numbers double and add one at each step: 1, 3, 7, 15, 31, 63. The table below lists the first several disc counts with the exact minimum and the time at one move per second.

Notice how flat the plot looks until it does not. That is the signature of exponential growth: the curve seems tame for small n and then leaves the page. A log scale straightens it into a line, because \log_2(2^n - 1) \approx n.

A worked example with three discs

Reading the solution as binary

The move sequence has a clean arithmetic shape. If you number the moves from 1 to 2^n - 1, the disc moved on step m is the position of the lowest set bit in the binary form of m. Move 1 is binary 001, lowest bit in position 1, so disc 1 moves. Move 4 is 100, lowest set bit in position 3, so disc 3 moves. Move 6 is 110, lowest set bit in position 2, so disc 2 moves.

Count how often each disc moves and the pattern falls out. Disc 1 moves on every odd number, so it moves 2^{n-1} times, which is 4 of the 7 moves for three discs. Disc 2 moves 2^{n-2} times (2 moves), and the largest disc moves once. The sum is 2^{n-1} + 2^{n-2} + \dots + 1 = 2^n - 1, the same total.

Common mistakes

The most frequent error when solving by hand is moving the smallest disc twice in a row. That never helps: two moves of disc 1 could always be replaced by zero or one, so any optimal solution alternates disc 1 with a forced non-trivial move. If you find yourself shuffling the top disc back and forth, you have left the optimal path.

A second mistake is choosing the wrong destination for the substack. To move n discs from A to C, the n-1 stack must go to B, the peg you are not starting from and not ending on. Send it to the wrong peg and you block the big disc.

Related tools

If the recursion here interests you, the N-Queens visualizer and the Knight's tour show backtracking, a close cousin that also builds a solution by trying and retreating. The Fifteen puzzle shares the sliding-constraint flavour and adds a parity argument for why half of all positions are unreachable.

For the wider theme of simple rules generating structure, try Langton's ant, Conway's Game of Life, and Collatz orbits. The binary reading of the move sequence connects naturally to Pascal's triangle mod n and to Nim and Grundy numbers, where binary digit sums decide the game.

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.