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.
touch screen « tourist « tourist information «
Towers of Hanoi » Tower Technology Corporation »
toy » Toy/Ada