Recursion – The Towers of Hanoi (i)

When one talks about recursion, invariably, the topic eventually turns towards the Towers of Hanoi (ToH). It is one of the most ubiquitous problems solved in a recursive manner – and it’s not one of the best (but more on that later). First, let’s look at a brief history of the Towers of Hanoi.

The Tower of Hanoi (note Tower, not Towers) is a classical mathematical puzzle, invented by French mathematician François Édouard Anatole Lucas (1842-1891) in 1883. Lucas is more commonly known for his study of the Fibonacci sequence. He marketed the game, which he called La Tour D’Hanoï, under the pseudonym N. Claus de Siam, a Mandarin of the College Li-Sou-Stian. It was Henri de Parville, French science writer who revealed “N. Claus de Siam” was an anagrammatic pseudonym for “Lucas d’Amiens”, and that the college of “Li-Sou-Stian” was really Lycée “Saint-Louis”, a school in Paris (where Lucas taught).

The front of the box from the original game

The Tower of Hanoi is loosely based on the legend of the Tower of Brahma, because no one has ever proven such a tower ever existed. The legend was likely created to create an air of mystique around the game itself. The instruction sheet that came with the game briefly outlined the legend:

“According to an old Indian legend, the Brahmins have been following each other for a very long time on the steps of the alter in the Temple of Bernares, carrying out the moving of the Sacred Tower of Brahma with sixty-four levels in fine gold, trimmed with diamonds from Golconde. When all is finished, the Tower and the Brahmins will fall, and that will be the end of the world!”

Translated into English from the instruction sheet provided with the game.
N. Claus (Edouard Lucas), La Tour d’Hanoï, Veritable Casse-tête Annamite (1883)

It was de Parville who elaborated on the legend, producing a much more embellished backstory.

It is said that, in the great temple at Benares, beneath the dome which marks the centre of the world, one may see fixed in a brass-plate three diamond needles, one cubit high and as thick round as the body of a bee. On one of these needles God at the creation placed sixty-four discs of pure gold, the largest disc resting on the brass slab, and the others placed in increasingly smaller diameters atop one another. This is the Tower of Brahma. Night and day the priests are continuously occupied, transferring the discs from the first diamond needle to the third, without deviating from the fixed and immutable laws imposed by Bramah. The priest can only move one disc at a time; he can place this disc on an unoccupied needle, or above a larger disc. When following these rules the 64 discs have been transferred from the needle upon which they placed to the third needle, the tower, and the Brahmins will crumble to dust, and it will signify the end of the world. 

Translated into English from Henri, de Parville, la tour d’Hanoï, Compte rendu de l’éditeur, Journal des Débats Politiques et Littéraires, 27 December 1883, revue des sciences, p.1-2 

It is not clear whether Lucas invented this legend or was inspired by it. The legend however, were it to be true, would take roughly 600 billion years to fulfill. This assumes the disks would be moved with 264-1 moves, which at the rate of one move per second, gives 1.84×10¹⁹ seconds (or 5.845×10¹¹ years). To put this into perspective, it is estimated that the age of the universe is 13.8×10⁹ years.

The Towers of Hanoi is similar, except the diamond needles are replaced by wooden dowels, and the golden disks replaced by wooden disks. Lucas published his work in the 3rd volume of Récreations Mathématiques [1]. The puzzle was translated to English from the works by Gaston Tissandier in 1890 [2]. In the original puzzle, Lucas used 8 discs. The figure shown below [3] illustrates the beginning of the game, II the process of transposition, with the disks moved with sticks A, B, and C, III the tower rebuilt at B. 

hanoiG
The Towers of Hanoi illustrated in La Nature

The game has made a number of appearances in popular culture. In the 1959 science fiction movie “Now Inhale“, the Terran focus of the novel is allowed to play one game from his home planet before he is executed for espionage. He chooses to play Towers of Hanoi, presumably with a good number of disks. In season 3 of Doctor Who (1966), in an episode titled “The Celestial Toymaker“, the First Doctor, and the Celestial Toymaker played The Trilogic Game, which is basically a variant of the Towers of Hanoi in the shape of a tetrahedron with 10 layers. The Celestial Toymaker gave the Doctor only 1023 moves to finish the game, or he would be trapped in the Celestial Toyroom forever.

The Trilogic Game

[1] Lucas, É, “La Tour d’Hanoi”, in Récréations Mathématiques (III), Gauthier-Villars et Fils, Imprimeurs-Libraires, Paris, pp.55-59 (1893)
[2] Tissandier G., (translated by Frith, H.), Half Hours of Scientific Amusement, Ward, Lock & Co., London, pp.106-111 (1890)
[3] Henri de Parville, “La tour d’Hanoï et la question du Tonkin”, La Nature, 12(548), pp.285-286 (Dec.1884)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.