Towers of Hanoi

Towers of Hanoi

(games)
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 ?
To put the insects to the test, Reid and colleagues presented them with a logic puzzle known as the Towers of Hanoi.
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.
In an introductory, undergraduate computer and information science Java programming course, the Towers of Hanoi student monk demonstration was given approximately 2 weeks before the final exam.
The one student who did not complete the survey replied to the assistant that he/she was not in attendance on the day of the Towers of Hanoi demonstration.
These responses certainly indicate an overall perceived effectiveness of the student monk demonstration in terms of helping the students learn of the overhead involved in recursion, and about the solution to the Towers of Hanoi problem (questions 1 and 2).
A form of active learning that uses "student monk" volunteers in a classroom demonstration of the recursive Towers of Hanoi solution is proposed as a way to help instructors teach recursion in an introductory IS or CS programming class, independent of the programming language used.
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.