Tower of Hanoi Solver

In 1883 a new puzzle appeared under the name of Professor N. Claus of Siam, mandarin of the college of Li-Sou-Stian. No such professor existed.

Rearrange the letters of N. Claus de Siam and they spell Lucas d’Amiens. Edouard Lucas, born in Amiens in 1842, was a French mathematician best known for his work in number theory: he studied the Fibonacci numbers and devised the test for Mersenne primes that is still used today. He also invented mathematical recreations, and one of them outlived everything else on the page. It is the Tower of Hanoi, and it repays a second look, because under the disguise it carries three serious things: a proof, a counter, and an admission of how much was still unknown.

A mandarin who never was

Lucas wrote the game up himself, in a volume of his mathematical recreations that was published in 1893, two years after his death. He tells it as a story about a friend. The friend’s game is a tower of eight wooden pieces, pierced in the middle and threaded on one of three nails fixed to a small board. Lucas calls it a true Annamite brain-teaser, and adds that the mandarin did not bring it back from Tonkin, whatever the prospectus says.

Then comes the legend. The mandarin reports that in the great temple at Benares, under the dome that marks the centre of the world, three diamond needles stand in a slab of brass. On one of them, at the beginning of time, were threaded 64 disks of pure gold, the largest at the bottom. Night and day the priests carry the tower from the first needle to the third, one disk at a time. When they finish, the tower and the Brahmins will fall, and the worlds will end.

Lucas ends the joke with a wink. Foreign makers, he says, have lately taken up his friend’s game and its legend, but the whole thing was imagined some time ago at number 56, rue Monge, in Paris. A dictionary of algorithms kept by the United States standards agency gives the legend a different author, De Parville, and the date 1884. Either way, nobody found it in a temple. The legend is no older than the toy.

Why the count doubles

The rules fit in a breath. There are three pegs and a stack of disks, all of different sizes, resting on one peg with the largest at the bottom. Move one disk at a time, always the top disk of a stack, and never set a disk on a smaller one. The task is to rebuild the tower on another peg.

Lucas gives the argument in a few lines. Suppose you can move a tower of eight. Then you can move nine: carry the top eight to the spare peg, move the ninth disk across, and carry the eight back on top of it. So each extra disk doubles the number of moves and adds one. Two disks need 3 moves, three need 7, then 15, 31, 63, 127 and 255. In general a tower of n disks needs 2 to the power n, less one.

That it cannot be done faster takes one more observation. At some point the largest disk has to leave its peg. It can do so only when every smaller disk stands on the third peg, out of the way. No solution, however clever, escapes building the smaller tower once before that move and once after it. The solution of that length is also the only one.

This is what programmers call recursion: a method that, in order to do a task, calls on itself with a part of the task. It needs a case simple enough to do directly, here a tower of one disk, and a rule that cuts every other case down. The whole solution is three lines. Move n minus 1 disks from the start peg to the spare. Move disk n to the goal. Move n minus 1 disks from the spare to the goal.

Now the legend can be checked. For 64 disks Lucas printed the number of moves in full: 18,446,744,073,709,551,615. At one move a second, he wrote, that would take more than five billion centuries.

The arithmetic bears him out. A year of 365.25 days holds 31,557,600 seconds, and dividing gives about 585 billion years, roughly 42 times the estimated age of the universe. Eight disks, by the same reckoning, take 255 seconds, a little over four minutes.

The counter hidden in the disks

Lucas added a remark that is easy to read past: the game, he says, shows how numbers are formed in the binary system. Number the moves 1, 2, 3 and so on, and ask how many times each number can be halved. Odd numbers cannot be halved at all, and on every odd move the smallest disk moves. A number that halves once moves disk 2, one that halves twice moves disk 3. The disks moved run 1, 2, 1, 3, 1, 2, 1, 4, the same pattern as the marks on a ruler.

Here is a case to reproduce. Take five disks on three pegs, a solution of 31 moves. After 11 moves, disks 1 and 2 are on peg A with disk 5, disk 3 is on peg C and disk 4 on peg B. Move 12 is 01100 in binary. Its lowest 1 is the third digit from the right, so disk 3 moves, from C to B, and 20 moves remain. The tool on this page opens on exactly that position. Press the button for the best move and watch the counter turn to 01100 as disk 3 lands.

There is a second way to count that makes the link plainer still. A Gray code lists the binary numbers in an order where only one bit changes from each entry to the next, which is why it is used in mechanical position sensors: a small slip can never upset more than one bit. Count the moves in Gray code and the single bit that changes is the disk to move. Move 11 is 01110 and move 12 is 01010. Only the third bit differs.

None of this needs to be written down while playing. Lucas credits his nephew, Raoul Olive, a pupil at the Lycee Charlemagne, with noticing that the smallest disk always travels the same way round the pegs, on every other move. Between two of its moves only one other move is legal. Follow those two rules and the tower crosses in the fewest moves, with no thought at all.

A disk can be on any of three pegs, so n disks have 3 to the power n positions. Three disks have 27, joined by 39 possible moves, and the picture of positions and moves grows into the pattern known as the Sierpinski triangle. From every one of those positions there is exactly one shortest way to gather all the disks on a chosen peg. Between two arbitrary positions matters are subtler: the largest disk moves once or sometimes twice, and deciding which took a paper to settle efficiently.

A fourth peg and an honest gap

Lucas remarked in passing that more pegs, with the rules slightly changed, would picture other number systems. Keep his rules, add a fourth peg, and the puzzle becomes much shorter. An obvious method suggests itself. Park some of the smallest disks on a spare peg, using all four pegs. Move the rest to the goal with the three pegs left. Then bring the parked disks back. Choosing how many to park so the total is least gives the Frame-Stewart numbers, named for a problem posed by B. M. Stewart in 1939 and answered with J. S. Frame in 1941.

The saving is large. On four pegs the counts run 1, 3, 5, 9, 13, 17, 25, 33, and twelve disks need 81 moves instead of 4,095. What nobody could show for more than seventy years was that no cleverer method does better. Many rediscovered the method and believed they had proved it best. The proof for four pegs came only in 2014, from Thierry Bousch.

For five pegs or more it is still a conjecture. Twelve disks take 47 moves on five pegs and 37 on six by this method, and the method is presumed best, but a paper as recent as 2020 could prove only weaker versions of the claim. A page that prints those figures as the minimum says more than anyone knows.

A computer can settle small cases by brute force, visiting every position and measuring its distance from the goal. The tool here does that when the positions number at most about 16.8 million, which covers four pegs up to twelve disks, five pegs up to ten and six pegs up to nine. In each of those cases the search agrees with the method. Beyond them it cannot check, and it says so: a count for twelve disks on six pegs is labelled conjectured, and a hint given far from the standard line is labelled as a legal route that may not be the shortest.

Change the rules instead of the pegs and the numbers move the other way. If a disk may step only to a neighbouring peg, a tower of n disks needs 3 to the power n, less one, moves to go from one end to the other, passing through every position there is. If disks may travel only clockwise round three pegs, three disks need 15 moves to reach the next peg and 21 to reach the one after.

Why psychologists keep one on the shelf

The puzzle left the toy shop long ago. It has been widely used in neuropsychology to study executive function and deficits in planning. The standard version there has three disks, which makes it a path through just 27 positions, and a solver is usually scored by the number of moves made and the time taken. What makes it a good test is where people stumble. The shortest path sometimes requires a move that seems to lead away from the goal, and researchers who simulate human problem solving point to exactly those counterintuitive moves as the hard ones. People do not see the recursion. They see a disk going the wrong way.

The form of the puzzle matters too. One study measured activity in the prefrontal cortex of twenty adults while they solved it in two forms, a physical set moved by hand and a version on a computer worked with a mouse. The measured change was significantly higher with the real disks. A screen version, this one included, is a way to see the mathematics, not a test of anyone’s mind.

So the toy with the false name has earned its place honestly. It shows a beginner why a method may call on itself, it hides a binary counter in plain sight, and with one more peg it marks the line between what has been proved and what has only never failed.