The History of the Tower of Hanoi
A French mathematician, a toy sold under an anagram, and a legend about the end of the world that appeared in print a year later.
On this page
The Tower of Hanoi is younger than it pretends to be. It arrived in Paris in 1883 dressed as an ancient puzzle from the Far East, with an invented professor on the box and, within a year, a legend about the end of the world. Behind all three was one of the most capable number theorists of the nineteenth century.
Édouard Lucas
François Édouard Anatole Lucas was born in Amiens in 1842. He worked at the Paris Observatory as a young man, served as an artillery officer in the Franco-Prussian War, and spent most of his career teaching mathematics at secondary schools in Paris, including the Lycée Saint-Louis.
His serious mathematics was about numbers. The sequences named after him generalise the Fibonacci numbers, and the method he developed for testing whether huge numbers are prime is, in refined form, the Lucas–Lehmer test that still finds record-breaking primes today. In 1876 he used it to prove that 2¹²⁷ − 1, a number thirty-nine digits long, is prime. It remained the largest known prime until 1951.
He also loved puzzles, and wrote about them seriously: four volumes of Récréations mathématiques, the last two published after his death. That death was absurdly sudden. At a banquet in 1891, a waiter dropped a plate and a shard cut Lucas’s cheek; the wound became infected, and he died a few days later, aged 49.
1883: a puzzle from nowhere
The puzzle went on sale in 1883 under a title that was a joke in every word:
La Tour d’Hanoï, véritable casse-tête annamite. Jeu rapporté du Tonkin par le professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian.
The Tower of Hanoi, a genuine Annamese puzzle. A game brought back from Tonkin by Professor N. Claus (of Siam), mandarin of the college of Li-Sou-Stian.
There was no Professor Claus. “N. Claus de Siam” is an anagram of “Lucas d’Amiens”, and “Li-Sou-Stian” is an anagram of “Saint Louis”, the lycée where Lucas taught. The puzzle itself was eight wooden disks, each pierced through the middle, stacked on one of three pegs fixed to a board. That is the board below — the original, played out in its 255 moves.
8 disks on tower A. 255 moves to go.Step 0 of 255
Eight disks, as in the 1883 box. A perfect game takes 2⁸ − 1 = 255 moves; the eight-disk solution lists every one.
The legend of the sixty-four disks
On 29 March 1884 the French science writer Henri de Parville presented the new puzzle in the magazine La Nature, in an article titled “La tour d’Hanoï et la question du Tonkin”. He revealed that N. Claus was Lucas — and he told a story.
In the great temple at Benares, beneath the dome that marks the centre of the world, three diamond needles stand in a brass plate. At the creation, God placed sixty-four disks of pure gold on one of them, the largest at the bottom. Day and night the priests move the disks from needle to needle, one at a time and never a larger disk on a smaller one. When all sixty-four have been moved to another needle, the tower, the temple and the priests will crumble into dust, and the world will end.
No older source for the story is known, and it has been retold with endless variations since — the temple moves to Hanoi, the priests become monks, the tower becomes the Tower of Brahma. What makes it work is the arithmetic, which is exactly right. Sixty-four disks take 2⁶⁴ − 1 moves: eighteen quintillion, which at one move a second is about 585 billion years. The priests are in no danger of finishing, and the 64-disk page shows where they would be if they had started the year the puzzle was published.
Why Hanoi?
In 1883 France was at war to take control of Tonkin, the northern region of what is now Vietnam, around the city of Hanoi. The name was topical, and de Parville’s title — “the Tower of Hanoi and the Tonkin question” — makes the connection explicit. The Siamese professor, the Annamese puzzle and the Brahmin temple are all part of the same fashionable exoticism.
None of it seems to have been true. No version of the puzzle older than Lucas’s is known, from Vietnam or anywhere else. What Lucas really brought back from the edge of the known world was a piece of mathematics.
What the puzzle became
A teaching example. Tower of Hanoi became the standard first example of recursion in programming courses, because its solution is a recursive function and almost nothing else: move the smaller disks aside, move the largest, move the smaller disks back. The algorithm and recursion explained pages take it apart.
A problem in mathematics. Its move counts are the Mersenne numbers Lucas spent his career on, and its solution turned out to be a binary counter in disguise — see Tower of Hanoi, binary and Gray code.
A harder puzzle with more pegs. Henry Dudeney’s The Canterbury Puzzles (1907) posed a four-stool version with cheeses, “The Reve’s Puzzle”. The general problem with any number of pegs was set in the American Mathematical Monthly in 1939, and in 1941 J. S. Frame and B. M. Stewart each published a method for it. Whether their method is the best possible stayed open for decades: Thierry Bousch proved it optimal for four pegs in 2014, and for five or more pegs the question is still unanswered.
A test of planning. Psychologists and neuropsychologists use the puzzle to study how people plan ahead. In 1982 Tim Shallice designed the Tower of London, a variant with coloured balls on pegs of different heights, to measure planning in patients with frontal-lobe damage.
A plot device. In The Celestial Toymaker, a 1966 Doctor Who serial, the Doctor must win the Trilogic Game: a ten-piece Tower of Hanoi to be finished in exactly 1,023 moves, which is precisely the ten-disk minimum.
Timeline
| Year | What happened |
|---|---|
| 1842 | Édouard Lucas is born in Amiens. |
| 1876 | Lucas proves 2¹²⁷ − 1 prime, the largest prime known until 1951. |
| 1883 | The Tower of Hanoi goes on sale, credited to “Professor N. Claus de Siam”. |
| 1884 | Henri de Parville reveals the inventor and publishes the temple legend in La Nature. |
| 1891 | Lucas dies in Paris, aged 49. |
| 1907 | Dudeney’s “The Reve’s Puzzle” poses a four-peg version. |
| 1941 | Frame and Stewart publish methods for any number of pegs. |
| 1966 | Doctor Who’s Trilogic Game demands a perfect ten-disk solution. |
| 1982 | Tim Shallice introduces the Tower of London test of planning. |
| 2014 | Thierry Bousch proves the Frame–Stewart method optimal for four pegs. |
The puzzle is still the one in the 1883 box: three pegs, a stack of disks, one rule. You can play it here, with anywhere from three disks to fifteen.
Frequently asked questions
Who invented the Tower of Hanoi?
The French mathematician Édouard Lucas. He published it in 1883 under the name "N. Claus de Siam", an anagram of "Lucas d'Amiens" — Lucas was born in Amiens — and the disguise was seen through the following year.
When was the Tower of Hanoi invented?
It went on sale in France in 1883. The legend of the temple and its sixty-four golden disks was published the next year, in an article by the science writer Henri de Parville in the magazine La Nature on 29 March 1884.
Is the Tower of Hanoi legend true?
There is no evidence for it. The story of priests moving sixty-four golden disks in a temple first appears in print in 1884, in an article presenting Lucas's new puzzle, and no older source for it is known. It is best read as part of the puzzle's presentation — and at one move a second, the world it threatens has about 585 billion years to spare.
Why is it called the Tower of Hanoi?
The 1883 puzzle was sold as "a genuine Annamese puzzle" brought back from Tonkin, the region around Hanoi in what is now northern Vietnam. France was fighting to take control of Tonkin that year, so the name was topical; de Parville's 1884 article was titled "La tour d'Hanoï et la question du Tonkin". No version of the puzzle older than Lucas's is known.
Keep reading
- Why the Minimum Is 2ⁿ − 1 MovesThe full proof that 2ⁿ − 1 moves is both achievable and unbeatable, why the shortest solution is unique, and how the moves divide between the disks.
- Tower of Hanoi, Binary and Gray CodeWhich disk moves on any move, read straight off the binary digits of the move number — and the Gray code that changes exactly the same bit.
- The Iterative Tower of Hanoi SolutionSolving the puzzle with a loop and two rules, and why those rules reproduce the recursive solution move for move.
- Recursion, Explained with the Tower of HanoiBase cases, the leap of faith and the call stack, taught on the one puzzle that recursion makes easy.
- The Tower of Hanoi algorithmThe recursive solution running line by line, its proof, and its complexity — in pseudocode and six languages.