Towers of Hanoi

Towers of Hanoi

A classic computer science problem, invented by Edouard Lucas in 1883, often used as an example of recursion.

"In the great temple at Benares, says he, beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish."

The recursive solution is: Solve for n-1 discs recursively, then move the remaining largest disc to the free needle.

Note that there is also a non-recursive solution: On odd-numbered moves, move the smallest sized disk clockwise. On even-numbered moves, make the single other move which is possible.

["Mathematical Recreations and Essays", W W R Ball, p. 304]

The rec.puzzles Archive.
Mentioned in ?
References in periodicals archive ?
SHEN, On the Frame-Stewart conjecture about the Towers of Hanoi, SIAM Journal on Computing 33 (2004), 584-589
FELNER, Recent progress in heuristic search: a case study of the four-peg towers of Hanoi problem, Proceedings of the twentieth international joint conference on artificial intelligence, AAAI Press (2007), 2324-2329
SZEGEDY, In how many steps the k-peg version of the Towers of Hanoi game can be solved?
To put the insects to the test, Reid and colleagues presented them with a logic puzzle known as the Towers of Hanoi.
Towers of Hanoi and London: reliability and validity of two executive function tasks.
Motivated by this research, the authors have used an in-class demonstration for teaching recursion that uses student volunteers to illustrate the recursive solution to a classical computer programming problem involving the Towers of Hanoi puzzle.
The Towers of Hanoi is a classical example of a problem that has a very difficult iterative solution, yet a relatively simple recursive one.
The 3 steps in this pseudocode solution to the Towers of Hanoi can be explained in non-programming terms as: 1) Move N-1 rings from the "Source" peg to the "Temp" peg; 2) Move one ring (the last and largest one) from the "Source" peg to the "Dest" peg; 3) Move the N-1 rings from the "Temp" peg to the "Dest" peg.
A Java applet illustrating the Towers of Hanoi puzzle can be found at www.
One class period before the actual in-class demonstration, the Towers of Hanoi puzzle can be briefly introduced to all the students in the class.
With a few simple tools and a surprisingly small number of parts, mathematics instructors from around the US present ways to make historical instruments and learning devices, producing labyrinths, Napier's Bones, the Towers of Hanoi, Pythagorean and string models, French curves, a panimeter, a cycloid pendulum clock and a brachistocrone.