Discrete

One tour through every position of the Tower of Hanoi

Draw every position of the Tower of Hanoi as a point and every legal move as a line, and the picture is a Sierpiński triangle. The famous shortest solution runs straight down one side of it, spelling the binary Gray code as it goes. The slowest honest solution threads through every position once and spells the ternary one. And unlike the cube the binary Gray code walks, which has 1,344 closed tours at four dimensions, the triangle has exactly one at every size.

Worth reading first: A walk that changes one thing at a time · The symmetric graphs no tour can close.

A walk that changes one thing at a time found the reflected binary Gray code: an order through all sixteen four-digit binary words in which each step changes exactly one digit, which is the same thing as a closed tour through every corner of a four-dimensional cube. That essay counted such tours by exhaustive search and found many — six on the ordinary cube, 1,344 on the four-dimensional one. The Gray code is one of them, chosen for its convenient recursive shape, and nothing about the cube singles it out.

There is a puzzle in which the Gray code is not a choice. Édouard Lucas sold it in 1883 as the Tower of Hanoi: a stack of discs, largest at the bottom, sits on one of three pegs, and the stack is to be moved to another peg one disc at a time, never putting a disc on top of a smaller one. The shortest solution for nn discs takes 2n−12^n - 1 moves, and the sequence of discs it moves is exactly the sequence of digits the binary Gray code changes. This essay draws the puzzle’s positions as a graph, finds that the graph is a Sierpiński triangle, and asks the tour question of it. The answer is the opposite of the cube’s: the graph of positions has exactly one closed tour through every position, at every size, and exactly one path through every position from the start to the goal — which is the solution of a harder puzzle and spells the ternary Gray code.

A position is a list of pegs

Nine positions of two discs, and the moves between them. Two-disc Hanoi: 9 states, 12 moves; shortest solution 3 moves.
Fig. 1 The nine positions of the puzzle with 2 discs, each drawn as three pegs, joined by a line when one legal move connects them. The three-move solution from both on A to both on C runs along the bottom.

Turning a puzzle into a graph is the move the seven bridges of Königsberg taught: keep only what can be reached from what, and throw the rest away. The rule that a disc never sits on a smaller one has a convenient consequence: a position is determined entirely by saying which peg each disc is on. Given the pegs, the discs on any one peg can only be stacked in one order, largest at the bottom. So with nn discs and three pegs there are exactly 3n3^n positions, one for each word of length nn in the letters A, B and C, and every such word is a legal position — nothing in the rule forbids any assignment of discs to pegs, it only forbids the moves that would produce an illegal stack.

The moves are just as easy to list. The smallest disc is always on top of whatever peg it is on, so it can always move, to either of the other two pegs. Any other move must move the top disc of one of the two pegs the smallest disc is not on, and onto the other of those two; of the two top discs there, the smaller is the only one that can go onto the larger. So from every position there are exactly three moves, unless all the discs are on one peg, when there are two. The figure draws this for two discs. The thin lines are moves of the small disc, which make three little triangles, one for each place the large disc can be. The thick lines are moves of the large disc, which can only happen when the small disc is out of the way on the third peg, and there are exactly three of them.

That is already the whole structure in miniature. A position with nn discs consists of a choice of peg for the largest disc and a position of the remaining n−1n-1 discs. Within one choice for the largest disc the smaller discs move exactly as in the (n−1)(n-1)-disc puzzle, so the positions split into three copies of the smaller graph. And the largest disc can move between two copies only when every smaller disc is on the third peg — a single position in each copy, so the three copies are joined by exactly three single moves, one between each pair. Three copies, joined pairwise at their corners by single lines: that is the recursive description of a Sierpiński triangle, as the triangle that Pascal’s numbers draw modulo two described it and as eight rules and a triangle grew it from a one-line automaton, and it is what the next figure draws.

The shortest solution runs down one side

The shortest solution runs along one side (3 discs). Hanoi graph with 3 discs: 27 states; route classic of 8 states.
Fig. 2 All 27 positions of the 3-disc puzzle, laid out as a Sierpiński triangle. The shortest route from all on A to all on C, found by breadth-first search, runs straight along the bottom side in 7 moves.

With three discs there are twenty-seven positions and thirty-nine moves. The layout puts the nine positions with the largest disc on A in the lower-left third, those with it on B at the top, and those with it on C in the lower-right; inside each third the same rule is applied to the middle disc, with the other two pegs exchanged so that the corners which need to meet do meet. Every move then has the same length on the page, and the result is the triangle drawn above: the positions with every disc on one peg are its three corners.

Solving the puzzle is finding a route from the lower-left corner to the lower-right, and the shortest one is visible at a glance. It runs straight along the bottom side, through eight of the twenty-seven positions. Breadth-first search confirms that no route is shorter and that this one is the only one of its length. The recursive reason is the classical proof: to move the largest disc from A to C, all the smaller discs must first be on B, so the solution must cross the single line between the A-third and the C-third, and to get there it must solve the (n−1)(n-1)-disc puzzle from A to B, then make the one big move, then solve it again from B to C. If TnT_n moves are needed for nn discs, then Tn=2Tn−1+1T_n = 2T_{n-1} + 1, and with T1=1T_1 = 1 that gives Tn=2n−1T_n = 2^n - 1.

Two corners of the triangle are therefore 2n−12^n - 1 moves apart, and the search adds the fact that no two positions are further apart than that: the diameter of the graph is the length of a side. The shortest solution visits 2n2^n positions, which at three discs is eight of twenty-seven and at ten discs is 1,024 of 59,049 — a vanishing share. It is the most economical route there is, and almost all of the puzzle’s positions lie off it. The triangle’s own dimension, log⁡3/log⁡2≈1.585\log 3/\log 2 \approx 1.585 as a dimension that is not a whole number measured it, is this ratio read the other way: doubling the side triples the number of positions.

The disc it moves is the digit the Gray code changes

The 4-disc solution is the Gray code on 4 bits. Hanoi 4 discs: discs moved 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1; equal to Gray code flips.
Fig. 3 The 15 moves of the shortest 4-disc solution against the reflected binary Gray code on 4 bits. At every step the disc moved is the bit the Gray code changes, marked in red.

Write down which disc each move of the shortest solution moves, numbering the discs from 1 for the smallest. For four discs the sequence is 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. It is the ruler sequence: the disc moved at step kk is one more than the number of times 2 divides kk, so disc 1 moves on every odd step, disc 2 on every step that is twice an odd number, and the largest disc exactly once, in the middle. The recursion explains it, since each half of the solution is the smaller solution and the big move sits between them.

The reflected binary Gray code has the same recursion. Its list of nn-bit words is the list of (n−1)(n-1)-bit words with a 0 in front, followed by the same list reversed with a 1 in front, so the step at the join changes the leading bit and every other step changes what the smaller list changed. The figure sets the two side by side and the computation checks every step: the digit the Gray code changes at step kk is the disc the puzzle moves at step kk. The same reflection organised every place changes back, where each digit of the binary words is changed back as often as it is changed, and the puzzle makes that balance physical: every disc that leaves a peg in the first half of the solution is retraced in mirror image in the second. The connection is the reason the Gray code is sometimes taught through the puzzle, and the converse is a practical solving method — count in Gray code and move the disc whose digit changed.

Which way to move it is decided too. The figure’s last two rows show that the smallest disc always moves the same way round the three pegs — A to C to B to A for an odd number of discs, the other way for an even number — and that every other move is the only legal move not involving the smallest disc. So the solution can be played with no memory at all: alternately move the smallest disc one step round its circle, and make the one other move available. This is exactly the behaviour of a walk on the cube that the reflected order of the binary words produces, transplanted onto pegs, and it is why the puzzle and the cube are often described as one object. They are not. The cube has 2n2^n corners and the puzzle has 3n3^n positions; the Gray code walks all of the cube and only a sliver of the puzzle. The next figure asks what walks all of the puzzle.

Forbid one pair of pegs, and the route takes in everything

The adjacent-peg solution visits every position (3 discs). Hanoi graph with 3 discs: 27 states; route linear of 27 states.
Fig. 4 The same 27 positions with moves directly between A and C forbidden. The only route left from all on A to all on C passes through all 27 positions, in 26 moves.

A variant of the puzzle, studied at least since the 1940s, puts the three pegs in a row and allows a disc to move only to a neighbouring peg: A to B, B to A, B to C, C to B, never directly between the ends. Every move of this restricted puzzle is a move of the ordinary one, so its graph is the ordinary graph with the A–C moves deleted. Breadth-first search on that graph finds the shortest solution from all on A to all on C, and it is long: 3n−13^n - 1 moves, 26 for three discs and 80 for four. Since the graph has only 3n3^n positions, a route of 3n−13^n - 1 moves that never repeats a position has visited every position. The restricted puzzle’s best solution is a path through the whole of the ordinary puzzle’s graph.

In fact the restricted graph is nothing but that path. Counting the moves available in each restricted position shows that two positions — the starting stack and the goal — have one move each and every other position has exactly two, at every size checked up to five discs; a connected graph like that is a single line. The restricted puzzle has no choices at all: from every position there is one way forward and one way back.

Read as words in the letters 0, 1 and 2, with the largest disc’s peg written first, the positions along this path are 000, 001, 002, 012, 011, 010, 020, 021, 022, 122, … — each word differing from the last in one digit, by one. That is the reflected ternary Gray code: the ternary words of length nn, listed so that consecutive words differ in one place by one, built by the same reflection as the binary one, with three blocks instead of two and the middle block reversed. The computation compares the two lists word for word and they agree. So the two Gray codes are the two extreme solutions of one puzzle — the shortest walks the binary code along one edge of the triangle, the restricted walks the ternary code through all of it.

Why there is only one tour

The one closed tour of every position (3 discs). Hanoi graph with 3 discs: 27 states; route cycle of 27 states, closed.
Fig. 5 The only closed route through all 27 positions that visits each exactly once, found by exhaustive search. Each shaded third is entered once and left once, along the single moves that join the thirds.

A Hamiltonian cycle of the positions — a closed route through every position exactly once — would be a way to play the puzzle that visits every arrangement of the discs and returns to the start. The exhaustive search finds one for three discs, drawn above, and no other. The reason is visible in the shading.

The three thirds of the graph are joined to one another by single moves, one line between each pair. A closed route that visits all three thirds must enter each third and leave it, and since a route can use each line once and each third has only two lines to the outside, the route must use all three joining lines, entering each third along one and leaving along the other. That fixes everything outside the thirds. Inside each third, the route must run from one of its corners to another, visiting every position of the third on the way: a path through every position of the smaller puzzle between two of its corners.

How many such paths does the smaller puzzle have? The same argument applies one level down. A path from corner A to corner C of the nn-disc graph, through every position, must visit the three thirds; it starts in the A-third and ends in the C-third, so the B-third lies in the middle, and since the A-third and the C-third are joined to the B-third by one line each, the order is forced — all of the A-third, then all of the B-third, then all of the C-third. Inside each third it is again a corner-to-corner path through everything. Writing pnp_n for the number of such paths, this says pn=pn−13p_n = p_{n-1}^3, and one disc gives p1=1p_1 = 1, since the only path through the three positions of a single disc from A to C goes by way of B. So pn=1p_n = 1 for every nn, and the closed tour, which is three such paths joined by the three joining lines, is unique too.

One tour against 1,344

One tour of the positions, and many of the cube. n=1: 1 tours, 1 paths; n=2: 1 tours, 1 paths; n=3: 1 tours, 1 paths; n=4: 1 tours, 1 paths; cubes 2:1, 3:6, 4:1344
Fig. 6 Every closed tour of the positions and every path from all on A to all on C through each position once, counted by exhaustive search for 1 to 4 discs, against the closed tours of the cubes the binary Gray code walks.

Most graphs that have one tour have many. Half the neighbours forces a tour found tours guaranteed by density, the boards a knight can tour found them in their millions on a chessboard, and the tour arrives with the last second neighbour found that a random graph which has one tour typically has a great many sharing most of their edges. The induction proves uniqueness for every size; the search confirms it independently for one to four discs, where the graph has 81 positions and the search must rule out every alternative explicitly. It also confirms that the single corner-to-corner path is the restricted puzzle’s solution, position for position. The figure sets these counts beside the closed tours of the cubes: 1 on the square, 6 on the 3-cube, 1,344 on the 4-cube, and the count on the 5-cube is in the hundreds of millions.

The contrast is the point of the essay, and it is worth stating plainly because the two objects are so often run together. The cube is generous with tours and the triangle is miserly, and the difference is how they are joined. The nn-cube is two copies of the (n−1)(n-1)-cube joined by 2n−12^{n-1} lines, one at every corner, so a tour can cross between the halves at any of a great many places and the choices multiply at every level. The Hanoi graph is three copies joined by three lines, one per pair, so there is no choice at all about where a tour crosses, and none multiplies. The graph is what the symmetric graphs no tour can close would call barely Hamiltonian: remove any one joining line and no tour survives, because the third it served could then be entered and left by only one route.

Graphs with exactly one Hamiltonian cycle are a studied curiosity, and a famous conjecture concerns them: Sheehan conjectured that no graph in which every point has exactly four neighbours has a unique tour, and for three neighbours a theorem of Smith, written up by Tutte in 1946, says that every line of such a graph lies on an even number of tours, so a tour is never unique there. The Hanoi graph slips between these: its corners have only two neighbours, and that pair of degree-two corners in every third is exactly what forces the route.

How far apart two positions are

How far apart two positions are. n=1: 0.6667 / 0.6667; n=2: 0.5926 / 0.6667; n=3: 0.5561 / 0.6667; n=4: 0.5402 / 0.6667; n=5: 0.5330 / 0.6667; n=6: 0.5297 / 0.6667; n=7: 0.5281 / 0.6667; n=8: 0.5273 / 0.6667
Fig. 7 For 1 to 8 discs, the mean distance between two positions and the mean distance from a position with every disc on one peg, each as a share of the longest distance, measured by breadth-first search over every pair.

The tour is unique; the distances are not so rigid, and they have a surprise of their own. From a position with every disc on one peg, the average number of moves needed to reach a random position turns out to be exactly two thirds of the longest distance, 23(2n−1)\tfrac23(2^n - 1), at every size the search reaches. That follows from the recursion too: the third containing the start is reached at a cost of the smaller puzzle’s average, and each of the other two costs a full 2n−12^{n-1} moves to enter plus the smaller average from its corner, and the arithmetic closes on two thirds.

Between two random positions the average is smaller, and it drifts. The search measures it over all 43 million pairs at eight discs and gets 0.5273 of the longest distance, falling slowly with each disc added. Andreas Hinz and Andreas Schief showed in 1990 that in the limit the share is 466/885=0.52655…466/885 = 0.52655\ldots, a fraction nobody would guess, which they obtained by computing the average distance between two random points of the Sierpiński triangle itself. That is the precise sense in which the puzzle with many discs is the fractal: the graph’s distances, scaled by the side, converge to the fractal’s.

A random position is therefore just over half a full solution away from another random position, and two thirds of one from a tidy stack. The shortest solution is the longest of all shortest routes, as an edge of a triangle should be.

What the drawings do not settle

The figures are exact. Every count of tours and paths comes from a search that rules out every alternative, every distance from breadth-first search over every pair, and the agreement of the solution with the two Gray codes is checked digit by digit rather than read off the picture. But exhaustion stops at four discs for tours and eight for distances, and the statements for every nn rest on the inductions in the text, which a drawing of three discs can illustrate and not prove.

The layout also hides something. Drawn as a triangle, the graph looks as though its three corners are special and its interior is not, and the uniqueness argument leans on exactly that impression. But the shape is a choice of drawing; the graph’s symmetry is only the six permutations of the pegs, and it is the joining structure — three single lines between three copies — that does the work. The same structure drawn as a tangle would have the same one tour. And the limit 466/885466/885 is quoted, not derived: the figure shows the shares heading towards it from above, slowly, which is consistent with the theorem and could not establish it.

Still open: four pegs and more

With a fourth peg the puzzle changes character. J. S. Frame and B. M. Stewart each proposed in 1941 a strategy for moving nn discs with four pegs — move some number of the smallest discs aside using all four pegs, move the rest with the three pegs left, and bring the first group back, choosing the split optimally — and conjectured that it is the best possible. For four pegs that conjecture stood for seventy-three years, until Thierry Bousch proved it in 2014 by an intricate argument about the graph of positions. For five or more pegs it is still open, although computer searches have confirmed it for every case small enough to search.

The state graphs of the many-peg puzzles are no longer Sierpiński triangles, and they are full of shortcuts: with four pegs there are many shortest solutions, and the distances behave very differently. Whether those graphs are still sparing with tours, or as generous as the cube, has been asked and is not answered in general. It is the kind of question the walk through the middle levels needed decades to settle for one family of cube-like graphs, and the many-peg graphs have had far less attention.

A triangle with one road round it

The positions of the Tower of Hanoi form a Sierpiński triangle: three copies of the smaller puzzle, joined pairwise by single moves. The shortest solution runs straight along one side in 2n−12^n - 1 moves and spells the binary Gray code; forbid moves between the end pegs and the only solution left threads through all 3n3^n positions in 3n−13^n - 1 moves and spells the ternary Gray code. Because each third can be entered and left only through its two joining lines, a closed route through every position is forced at every level, and there is exactly one — confirmed by exhaustive search for one to four discs, against 1,344 tours on the four-dimensional cube whose corners the binary Gray code walks. The tour that the cube offers in profusion, the puzzle offers once.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

Exhaustive searchGraphGray codeHamiltonian cycleHypercubeRecursionSelf-similaritySierpiński triangle