C Program Tower of Hanoi

The Tower of Hanoi problem consists of three poles, left, middle, and right. One of the poles (say, the left) contains n disks of different sizes placed on each other, as shown in Fig. The objective of the problem is to transfer all the disks from the left pole to right pole such that only one disk can be moved at a time (to any pole) and a larger  disk cannot be placed on top of a smaller disk.

This problem can easily solved for small values of n. However, the level of difficulty increases rapidly as the number of disks increases. It is also very difficult to write a program for this problem using loops and other control structures. However, the use of recursion leads to a very simple and elegant solution.

The first step in implementing recursion is to find out how we can reduce the size of the problem under consideration. The problem of moving n disks, can be decomposed into smaller problems of moving n – 1 disks as shown below:

1. Move n – I disks from the source pole to the intermediate pole

2. Move remaining disk from the source pole to the target pole

3. Move n -1 disks from the intermediate pole to the target pole.

The second step is to decide the terminating condition. Note that the problem of moving n – 1 disks in steps l and 3 will actually be solved in terms of the smaller problem of moving n – 2 disks, which in turn will be solved in terms of the still smaller problems involving n – 3 disks and so on for as long as there is at least one disk to be moved. Thus, the terminating condition for this problem is that the number of disks to be moved should be equal to zero.

The complete program that includes a recursive function hanoi is given below. The function accepts four parameters. The parameter n disk of type int specifies the number of disks to be moved. The other three parameters, namely, source, target and other, are of type char and specify a single character identification of the source, target and intermediate poles, respectively.

/* Tower of Hanoi program */
#include<stdio.h>
void hanoi(int ndisk, char left, char right, char mid);
void main() {
 int ndisk;
 clrscr();
 printf("--- Tower of Hanoi ---\n");
 printf("Enter number of disks: ");
 scanf("%d", &ndisk);
 hanoi(ndisk, 'L', 'R', 'M');
 getch();
}
/* Recursive function to move 'ndisk' disks from source' 
 pole to 'target' pole using 'other' as intermediate pole */
void hanoi(int ndisk, char source, char target, char other) {
 if (ndisk > 0) {
   hanoi(ndisk - 1, source, other, target);
   printf("Move disk from %c to %c\n", source, target);
   hanoi(ndisk - 1, other, target, source);
 }
}

The program output is given below