Tower of Hanoi game

A game starts with every disc stacked on peg A, the largest at the bottom. It ends when the whole tower stands on the peg at the far right, marked goal. Three rules govern each move. Only one disc moves at a time, only a top disc can be lifted, and a larger disc may never sit on a smaller one. The middle peg serves as the spare that makes this possible.

British English calls the pieces discs: Oxford Learner's Dictionaries give disc as the British spelling and keep disk for computers, though many puzzle pages write disks. The pegs are also called rods. Disc 1 is the smallest disc, and the option "Show numbers on the discs", on at the start, writes each disc's number on it.

A tap or click on a peg lifts its top disc, and a tap on another peg puts it down there; dragging the disc works too. A move the rules forbid is refused, and the board gives a short shake unless the device asks for reduced motion. The status line gives the reason, as in "Disc 2 cannot go on disc 1: a larger disc never sits on a smaller one."

The board also works from a keyboard. With a peg reached by Tab, a number or the peg's letter lifts the top disc of that peg, and the number or letter of another peg puts it down. Escape puts a lifted disc back, and the arrow keys move from peg to peg.

Three counters run beside the game. Moves counts the moves on the board, and Undo takes one back as often as needed, each counted as a move taken back. Fewest possible shows the minimum for the tower being played, and Time starts with the first move and stops when the tower is complete.

The finished tower brings a result: the moves against the fewest possible, the time to a tenth of a second, the hints used and the moves taken back. Copy result copies a line with the link, Play again starts over, and a further button adds one more disc.

It takes at least 7 moves with three discs, 31 with five and 1,023 with ten. The minimum number of moves for n discs is 2^n - 1, and no sequence of moves does better. Lucas put the rule into words in Récréations mathématiques, where each extra disc doubles the number of moves and adds one.

At a steady move a second, eight discs, the size of Lucas's original wooden set, take 4 minutes and 15 seconds, and ten discs take 17 minutes and 3 seconds. A first game here has four discs, so 15 moves at best. For a classic three-peg tower the counter of the fewest possible uses the same formula, and the reference cases check it against Lucas's table, Dudeney's puzzle and the OEIS.

Five discs take 31 moves, and the smallest disc makes every odd-numbered one. With an odd number of discs it goes round A, C, B, A, so its first move is from A to C. With an even number it turns the other way, A, B, C, A. Peg B is the auxiliary peg, the spare that holds discs on their way.

Between two moves of the smallest disc, only one legal move leaves it alone. On the other two pegs, the smaller top disc goes onto the larger one or onto an empty peg. Repeating those two steps is the iterative solution, and it needs no planning ahead. Lucas credits the rule for disc 1 to his nephew Raoul Olive, a pupil of the lycée Charlemagne.

In the 31 moves, disc 1 moves 16 times and disc 2 moves 8 times. Discs 3 and 4 move 4 and 2 times, and disc 5 at the bottom moves once. In general disc k of n moves 2^(n-k) times, so every disc moves twice as often as the next larger one.

Seven discs, the other count most often looked up, take 127 moves, and disc 1 turns the same way as with five. The game lists any tower's moves under "The solution move by move", numbering each one as "Disc 1: A to C". It highlights the next move while the play follows the list, and "Print the move list" prints only the list. Used that way, this Tower of Hanoi solver also serves a wooden set on the table.

The minimum is 2^n - 1 because the biggest disc cannot move until every smaller disc sits on the spare peg. Those discs then have to be stacked back on top of it. Moving the n - 1 smaller discs away takes at least 2^(n-1) - 1 moves, the bottom disc moves once, and bringing the others back costs the same again.

That gives the recurrence relation T(n) = 2T(n - 1) + 1, with T(1) = 1 for a single disc. Mathematical induction completes the proof: if T(n - 1) = 2^(n-1) - 1, then T(n) = 2^n - 2 + 1 = 2^n - 1. Plus magazine, from the University of Cambridge, sets out the same argument, and the On-Line Encyclopedia of Integer Sequences holds 1, 3, 7, 15, 31 and onwards as sequence A000225.

Doubling at every disc is exponential growth. Ten discs already need 1,023 moves, and twenty would need 1,048,575.

The moves also follow binary counting. The disc moved at step m is one more than the number of zeros at the end of m written in binary. That gives the ruler sequence 1, 2, 1, 3, 1, 2, 1, 4 for the first eight steps of any tower of four or more discs. Andreas M. Hinz notes it in a comment on the OEIS entry A001511, and it is why disc 1 moves on every odd-numbered step.

NRICH, the University of Cambridge's mathematics enrichment site, sets the puzzle for ages 11 to 14 among its problems on patterns and sequences.

The recursive algorithm solves a tower of n discs by solving a tower of n - 1 twice. The puzzle is a common example of recursion, as in Robert Sedgewick and Kevin Wayne's recursion chapter for Princeton University. Recursive techniques are part of AQA's A-level Computer Science specification (7517, section 4.1.1.16), which names no particular puzzle.

1. Move the n - 1 smaller discs from the start peg to the spare peg, with the goal peg as their spare.
2. Move the largest disc to the goal peg.
3. Move the n - 1 discs from the spare peg onto the largest disc, with the start peg as their spare.

The base case is a single disc, which moves straight to its peg, and the first and last steps are the same problem with one disc fewer. The game builds its move list for a tower on three pegs this way. From a mixed position, the hint and the solver work out a shortest way to the goal instead.

A random position puts every disc on any peg, with all arrangements equally likely, except that the largest disc never starts on the goal peg and so has to move. Such a start needs at least 2^(n-1) moves and never more than a whole tower. With four discs that is between 8 and 15, and 12.7 on average over every start the game can deal.

This site's own count of all positions, with the bottom disc anywhere, gives an average of two thirds of a whole tower's moves. That is 10 moves for four discs, so leaving out the starts where the bottom disc is already home raises the average.

Three pegs give n discs 3^n possible positions: 243 for five discs and 59,049 for ten. Drawn as a graph, with a point for each position and a line for each move, they look more and more like the Sierpiński triangle as discs are added. Plus magazine describes the likeness, and the book by Hinz, Klavžar and Petr works it out in detail.

A random start is dealt only after a tap on "Deal a random position". Its position goes into the page's link, so a shared link gives a friend the same start, and the counter then reads "Fewest from start".

Hint highlights both pegs of the next move of a shortest way to the goal from wherever the discs are, and each hint is counted. The status line spells the move out, as in "Hint: move disc 2 from A to C."

Solve lets the solver finish from the current position, with Pause, Resume, One move and Take over to carry on by hand. A game that started from a tower and still follows the printed list is simply continued along it. The solver waits 0.9 seconds between moves at slow speed, 0.45 at normal, 0.16 at fast and about 0.045 at very fast. A game in which the solver, a hint or an undo played a part is not kept as a best result.

A fourth peg cuts the moves sharply: eight discs need 33 moves instead of 255. Henry Dudeney set this as the Reve's puzzle in The Canterbury Puzzles of 1907, with eight cheeses moved across four stools in 33 moves and ten cheeses in 49.

B. M. Stewart posed the general four-peg question as problem 3918 in the American Mathematical Monthly in 1939, and Frame and Stewart each answered it in 1941. Their method, the Frame-Stewart algorithm, moves some small discs aside using all four pegs, moves the rest with three, then brings the small ones back on top.

Whether anything shorter exists stayed open until Thierry Bousch proved in 2014 that it does not, and the OEIS lists the numbers as A007664. For five or more pegs the question is still open, according to the publisher's page for the book by Hinz, Klavžar and Petr.

The game takes 3 to 8 discs on four pegs, because its four-peg hints search every one of the 4^n positions, 65,536 of them for eight discs. Its move list there shows the Frame-Stewart solution, and other solutions of the same length exist.

Édouard Lucas brought out the puzzle in 1883 as "la Tour d'Hanoï, véritable casse-tête annamite", under the name "professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian". R. E. Allardice and A. Y. Fraser quote that wording from the Journal des Débats of 27 December 1883 in the Proceedings of the Edinburgh Mathematical Society.

MacTutor, the history of mathematics archive of the University of St Andrews, explains the names: N. Claus de Siam is an anagram of Lucas d'Amiens, and Li-Sou-Stian of Saint Louis, the lycée where Lucas taught. His set had eight wooden discs with a hole in the centre, threaded on one of three pegs, as volume 3 of Récréations mathématiques (1893) describes it.

The legend came with the puzzle on its 1883 sheet. In the great temple of Benares, in India, priests called Brahmins move the sacred tower of Brahma: 64 discs of pure gold on three diamond needles. They move one disc at a time and never a larger on a smaller. When they finish, the tower and the Brahmins fall and the world ends.

The story is Lucas's own invention, and the puzzle does not come from Vietnam either. Lucas wrote that the game was not brought back from Tonkin, whatever the leaflet says, and that game and legend were made up at 56 rue Monge in Paris. Henri de Parville retold the story in La Nature the following year, and W. W. Rouse Ball cites that account in Mathematical Recreations and Essays.

In the same year Lucas also put a pencil and paper game into print, "le jeu de l'École Polytechnique", now known in Britain as dots and boxes. He brought it out as a boxed game, La Pipopipette, in 1889.

Psychologists use tower puzzles to study planning and problem solving. An article in Plus magazine sums up the appeal of Lucas's tower for that work: "you can watch people think".

Tim Shallice described a planning task in the Philosophical Transactions of the Royal Society in 1982. A study from Erasmus University Rotterdam calls the Tower of London, a related task, a widely used instrument for planning ability. Jeremy Sullivan, Cynthia Riccio and Candace Castillo reviewed tower tasks as measures of executive function in a meta-analysis of 2009.

University of Dundee Museums hold a Tower of Hanoi made at Queen's College, Dundee, around the 1960s, catalogued as "used in psychology to test problem solving skills".

This page is a puzzle, not an assessment. Its counters keep no score with any clinical meaning, and a result here says nothing about intelligence, attention or any condition. The Stroop test on this site turns another classic task from psychology into a game, with no norms either.