The Towers of Hanoi

The Towers of Hanoi problem is said to be based on a legend in which the monks in a monastery near Hanoi, Vietnam came into possession of 64 golden disks mounted on one of three diamond needles. The disks are in order with the smallest on top and the largest on the bottom. The task given to the monks was to try to move all the disks from one needle to another needle using the following rules.

1. Only one disk may be moved at any one time.
2. No disk may be placed on top of a smaller disk.

According to the legend, after all the disks have been moved, the universe will come to an end. If we suppose that the monks began their task 3000 years ago, and that they have been moving disks constantly at a rate of one per second ever since, calculate the approximate number of years from now to the time when the universe will supposedly end. But don’t worry about this too much.

Tracing the Development of a Complex Recursive Solution

Think of the needles as needle 1, needle 2, and needle 3. The disks are numbers 1, 2, 3. . .n where 1 is the smallest and n is the largest. You are trying to move all the disks from needle 1 to needle 3, using needle 2 to help the process. If there is only one disk on needle 1 then the problem is insignificant, simply move that disk to needle 3.

Think of a tower with two disks as a one-disk tower placed on top of a larger disk. The instructions for moving such a tower would be:

1. Move the one-disk tower from needle 1 to needle 2 (1 -> 2)
2. Move the bottom disk from needle 1 to needle 3 (1 -> 3)
3. Move the one-disk tower from needle 2 to needle 3 (2 -> 3)

Similarly, think of a tower with three disks as a two-disk tower placed on top of the largest disk. The instructions for moving such a tower would be:

1. Move the two-disk tower from needle 1 to needle 2 (Just adapt the previous solution in this manner: (1 ->
2. 3) (1 -> 2) (3 -> 2)
3. Move the bottom disk from needle 1 to needle 3 (1 à 3)
4. Move the two-disk tower from needle 2 to needle 3 (Once again, adapt the previous solution in this manner: (2 ->
5. 1) (2 -> 3) (1 -> 3)

The pattern should now be clear. If there are n disks on needle 1, then think of this as a tower of n-1 placed on top of the largest disk. Before you can move disk n to needle 3, you must move disks 1 through n-1 out of the way be moving them to needle 2. Then, after you move disk n to needle 3, you must move disk 1 through n-1 from needle 2 to needle 3.

Break this pattern down into 3 subproblems:

1. Move n-1 disks from needle 1 to needle 2
2. Move n disk from needle 1 to needle 3
3. Move n-1 disks from needle 2 to needle 3.

Subproblem 2 is very simple because only one disk is moving. Subproblems 1 and 3 appear to be very complex but in fact can be divided into further subproblems until you reach a point where you are only moving one disk.

But you will be doing that many times!

Examine this recusive algorithm for solving The Towers of Hanoi problem:

If there is only one disk then

simply move it from the first needle to the last needle

else

move n-1 disks from the first needle to the intermediate needle,

move the bottom disk to the third needle

move the n-1 disks from the intermediate needle to the last needle

Using that algorithm, this is pseudocode for a method called moveTower which has three parameters:

• the height of the tower to be moved;
• the number of the needle on which the tower starts;
• the number of the needle on which the tower finishes.

method moveTower ( height, start, finish : integer )

variable intermediate : integer // represents the intermediate needle number

if height is equal to 1 then

just move it from start to finish // exit from the method

else

determine the location for the intermediate needle by using the fact that the sum of the values of the needle numbers

is always six.intermediate is assigned the value of 6 – ( start + finish )

move all but one disk from start to intermediate using moveTower method

moveTower ( height – 1, start, intermediate )

move the bottom disk

output start , “à”, finish

move the remaining disks from intermediate to finish using moveTower method

moveTower ( height-1, intermediate, finish )

end procedure

Play the Game Trace it through all methods and classes.