N-ary Puzzle Calculator
How the Tower of Hanoi count works
Three pegs, and a stack of disks of decreasing size. Only one disk moves at a time, and a larger disk may never sit on a smaller one. The picture above shows your stack on the left peg, which is where every Hanoi puzzle starts, with the other two empty.
Each disk you add doubles the work and adds one move. To shift a stack of n, you
first move the top n-1 disks out of the way, move the big disk once, then move those n-1 back on
top. So the count is 2 x (previous) + 1. Run that from one disk upward and you get 1, 3, 7, 15, 31,
and in general 2^n - 1.
That doubling is why the legend about 64 golden disks works. The number is not large because the puzzle is fiddly, it is large because it doubles 64 times.
What counts as an n-ary puzzle
An n-ary puzzle has a number of stages, and each stage rests in n different positions. Solving it means counting the mechanism through those states in order, which is why the move counts grow so fast. The oldest example is the Chinese rings, where each ring is effectively one binary digit and the solution traces a Gray code.
The classification runs well past binary. Goetz Schwandtner's compendium of n-ary puzzles is the reference work, cataloguing ternary designs like Crazy Elephant Dance, quaternary ones such as the Ziggu series, Hanayama's senary Cast Infinity, and at the far end a 15-ary puzzle called Generation Lock.
The formulas, and how they were checked
| Puzzle | Minimum moves | Verified by |
|---|---|---|
| Tower of Hanoi, n disks | 2^n - 1 |
Recursive simulation |
| Chinese rings, n rings |
(2^(n+1) - 2) / 3 when n is even(2^(n+1) - 1) / 3 when n is odd |
Breadth-first search of the full state space to n = 12 |
| n-ary, base k, m stages | (k - 1) x rings(m) |
Brute forced for every base 2 to 6, stages 1 to 7 |
That last relationship is the useful one. A ternary puzzle takes exactly twice the moves of the binary puzzle with the same number of stages, and a quaternary one exactly three times.
Hanoi is kept separate on purpose. It is ternary in the sense that each disk sits on one of three pegs, but its optimal path visits only 2^n of those 3^n states, so it does not follow the counting rule the other two share.
Where to see them
The Tower of Hanoi guide covers the method and the history, and Chinese rings explains the Gray code connection. The wider range is in mechanical puzzles.