Tower of Hanoi

Problem. Move $n$ disks from peg A to peg C using peg B, with two rules: move one disk at a time, and never place a larger disk on a smaller one.

The recursive solution

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);
    printf("move disk %d: %c -> %c\n", n, from, to);
    hanoi(n - 1, via, to, from);
}

Move the top $n - 1$ aside, move the largest, move the $n - 1$ back.

$T (n) = 2 T (n - 1) + 1, T (0) = 0 ⟹ T (n) = 2^{n} - 1,$

and this is optimal — the largest disk must move at least once, and before it can, all $n - 1$ others must be on the spare peg.

The iterative solution

The move sequence has a beautiful closed form:

On move $i$ (1-indexed), move disk $ctz (i)$ — the number of trailing zeros of $i$ .

for (long long i = 1; i <= (1LL << n) - 1; i++) {
    int disk = __builtin_ctzll(i);
    // the disk moves in a fixed cyclic direction depending on parity of n and disk
}

Disk 0 (the smallest) moves on every odd step; disk 1 on every 4th; disk $k$ on every $2^{k + 1}$ -th. The smallest disk always cycles in one direction ( $A \to C \to B \to A$ if $n$ is odd, the other way if even), and on the other moves there is only ever one legal move not involving it.

This is exactly a Gray code: the bit that changes from $i$ to $i + 1$ is $ctz (i + 1)$ , and each disk’s position corresponds to a bit.

The state graph

The $3^{n}$ legal configurations form a graph whose structure is the Sierpiński triangle. The optimal solution is a path along one edge of it, and the graph’s diameter is $2^{n} - 1$ .

Consequences:

The shortest path between any two configurations is computable in $O (n)$ by a greedy recursion.
Moving from an arbitrary configuration to another is not always $2^{n} - 1$ — that is only the corner-to-corner distance.

Variants

Variant	Result
$n$ disks, 3 pegs	$2^{n} - 1$ moves
4 pegs (Reve’s puzzle)	Frame-Stewart: $min_{k} (2 T_{4} (n - k) + 2^{k} - 1)$ ; proven optimal in 2014
$p$ pegs	Frame-Stewart generalises; optimality open for $p \geq 5$
Cyclic Hanoi (moves only $A \to B \to C \to A$ )	$3^{n} - 1$ moves
Bicolour / two-stack variants	different recurrences
Arbitrary start and end configuration	$O (n)$ greedy
Count moves of a specific disk $k$	$2^{n - 1 - k}$
Which peg is disk $k$ on after $m$ moves?	read the bits of $m$

Frame-Stewart for 4 pegs: move $n - k$ disks to a spare peg (using all 4), move the remaining $k$ using 3 pegs ( $2^{k} - 1$ moves), then move the $n - k$ back. Choosing the optimal $k$ gives a DP.

Why it is worth knowing

The problem is the canonical illustration of three ideas:

Recursion with a self-similar structure — the classic first example of “solve two smaller copies”.
A $2^{n}$ lower bound proved by necessity, not by exhaustion.
The recursive and iterative forms of the same sequence — one derived from the recursion, the other from the binary representation. Seeing that they agree is a good exercise in the connection between recursion and bit patterns.

The ctz fact generalises: whenever a recursive process splits as $T (n) = 2 T (n - 1) + O (1)$ and produces a sequence, that sequence usually has a description in terms of the binary expansion of the step index.

The legend

The Tower of Brahma has 64 golden disks. At one move per second, $2^{64} - 1$ moves take about 585 billion years — around 42 times the current age of the universe.

See also: Gray Code · Divide and Conquer · Classical Problems

whoashish's cp notes

Directory