Tower Of Hanoi
October 11, 2011
According to legend, there is a temple in Hanoi where are located sixty-four golden rings of graduated sizes and three diamond towers. Each day, the monks of the temple move a ring from one tower to another according to the rule that only one ring may be moved each day, that a single move consists of taking the highest ring from one tower and placing it on another tower, and that no ring may be placed on top of a smaller ring. The rings and towers were placed at the beginning of the world, and the monks have toiled through the ages to move all the rings from the designated starting tower to the designated finishing tower, at each day making the move that minimizes the total number of moves required. The world will end when the monks complete their work.
Actually, there is no legend; the story was concocted as a mathematical puzzle by Edouard Lucas, whom we have met in our work on primality testing. The program that determines the sequence of moves is often used as a demonstration of recursion: to move five rings from the first tower to the second, first move four rings from the first tower to the third, then move the fifth ring from the first tower to the second, then move four rings from the third tower to the second. To move four rings from the first tower to the third, first move three rings from … There is also an iterative solution, but I can never remember it, and the recursive solution is so simple that it’s the one I always use.
Your task is to write the program that calculates the sequence of moves that solved the Tower of Hanoi using the fewest number of moves. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 