4.2.1 The Towers of Hanoi

A game called the Towers of Hanoi was purportedly played by priests in the Temple of Brahma, who believed that completion of the game's central task would coincide with the end of the world. The task involves three pegs. The version considered here has n disks initially mounted on peg 1 (the priests dealt with 64 disks). The n disks increase in size from top to bottom, the top disk being the smallest. The problem is to relocate the n disks to peg 3 by moving one at a time. Only the top disk on a peg can be moved. Each time a disk is moved it may be placed only on an empty peg or on top of a pile of disks of larger size. The task is to develop an algorithm specifying a solution to this problem, no matter what the value of n.

Consider the case when n = 4, shown in Figure 4.1(a). The following sequence of instructions provides a solution.

1. Move the top disk from peg l to peg 2.

2. Move the top disk from peg 1 to peg 3.

3. Move the top disk from peg 2 to peg 3.

4. Move the top disk from peg 1 to peg 2.

5. Move the top disk from peg 3 to peg 1.

6. Move the top disk from peg 3 to peg 2.

7. Move the top disk from peg 1 to peg 2.

8. Move the top disk from peg 1 to peg 3.

9. Move the top disk from peg 2 to peg 3.

10. Move the top disk from peg 2 to peg 1.

11. Move the top disk from peg 3 to peg 1.

12. Move the top disk from peg 2 to peg 3.

13. Move the top disk from peg 1 to peg 2.

14. Move the top disk from peg 1 to peg 3.

15. Move the top disk from peg 2 to peg 3.

(a) The Initial Problem

(b) After Component 1

(c) After Component 2

(d) After Component 3 ?the Solution!

Figure 4.1 The Towers of Hanoi Problem

It is not difficult to arrive at such a solution for a specific small value of n. Try to find a solution for n = 5. You will find that, even though you succeed after some trial and error, creating a solution for n = 25 is indeed a formidable task. You may even be too old to care by the time you finish. If a particular value of n gives so much trouble, how does one specify a solution for any n, when one does not even know what value n will have?

One answer is to apply the technique of recursion. This means attempting to break down the problem into component problems that can be solved directly or that are identical to the original problem but involve a smaller number of disks. The three component problems below fit the requirements of this framework.

1. Move the top n - 1 disks from peg 1 to peg 2.

2. Move the top disk from peg 1 to peg 3.

3. Move the top n - 1 disks from peg 2 to peg 3.

If these three problems can be solved, and their solutions are applied in sequence to the initial situation, then the result is a solution to the original problem. This can be seen from parts (a)-(d) of Figure 4.1, which show the consecutive situations after each is applied.

We now generalize the original problem:

Move the top n disks from peg i to peg f.

i denotes the initial peg on which the top n disks to be relocated reside, and f denotes the final peg to which they are to be relocated. Let a denote the third available peg. Solving the original problem, which has only n disks, is equivalent to solving the generalized problem with i taken as 1 and f taken as 3. This is because the moves that accomplish its solution will also work for the generalized problem, since any disks below the top n are larger than they are, so their existence doesn't render any of the moves illegal. Solving the first component problem is equivalent to solving the generalized problem with n replaced by n - 1, i by 1, and ?by 2. It is now apparent that the original problem, and the components 1, 2, and 3, have structure identical to the generalized problem, but the components involve fewer disks. They also involve different initial, available, and final pegs. This is why it was necessary to generalize the original problem.

Suppose you have found a solution to the generalization and denote it by towers(n,i,a,f). Then, as just shown, the application of the solutions to components 1, 2, and 3, in sequence, will be a solution to the original problem. A recursive definition for towers(n,i,a,f) can now be expressed as follows. Note that moves in towers(n,i,a,f) are from peg i to peg f?/FONT>that is, from the second parameter to the fourth parameter. The first parameter specifies the number of top disks, on the peg given by the second parameter, that are to be moved.

>Comment

To obtain towers(n,i,a,f):

If n = 1, then

>Comment

move the top disk from peg i to peg f

else

>Comment

apply towers(n - 1,i,f,a)

moves the top disks from peg i to peg f

>Comment

apply towers(n - 1,a,i,f).

This is the recursive algorithm for the Towers of Hanoi problem. Notice that the definition gives an explicit solution for the special case when n = l and an implicit solution for the case of n > 1.

To use the method of recursion we must recognize when it is applicable and find a correct way to generalize the original problem and then to break down the generalization. We have been successful and have found a recursive algorithm. Because no further refinement is needed, the corresponding recursive program can be written directly using functional modularization:

towers(n,i,a,f)

/* Moves the top n disks from peg i to peg f

*/

int n,i,a,f;

{

if(n == 1)

printf("\n %d -> %d\n",i,f);

else

{

towers(n-1,i,f,a);

[1]

printf("\n %d -> %d\n",i,f);

towers(n-1,a,i,f);

[2]

}

}

The labels [1] and [2] are not part of the program but are used later as references when explaining the program. It is essential to see that this function has been written just like any other; whenever a component task is available as a function, we invoke it to carry out that task. The feature that distinguishes it and makes it a recursive function is that the required functions happen to be the function itself. The references within towers to itself are allowed in recursive languages.

Anytime a function calls itself during its execution, a recursive call has been made. The two invocations of towers within towers represent such recursive calls. In general, when a recursive program executes on a computer, or when its execution is simulated, many recursive calls will be made. Simulation of a program or function call means carrying out its instructions by hand and keeping track of the values of all its variables. These are referred to as the first, second, etc., recursive calls. The initial call to the function precedes the first recursive call.