Word:

Towers of Hanoi

(games)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.
Browse
towel rack
towel rail
towel ring
Toweling
towelling
Tower
Tower bastion
tower block
tower cress
tower mustard
Tower of Babel
Tower of London
tower of strength
Tower Technology Corporation
Towered
Towering
-- Towers of Hanoi --
Towery
towheaded
Towhee
Towilly
towing line
towing path
towing rope
Towline
Town
town clerk
Town cress
town crier
town gas
town hall
town house
town meeting
Definitions Index: # A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

About this site and copyright information - Online Dictionary Home - Privacy Policy