Towers Of Hanoi

Suppose there are three pegs labeled A, B and C. Four disks are placed on peg A. The bottom-most disk is largest, and disks go on decreasing in size with the topmost disk being smallest. The objective of the game is to move the disks from peg A to peg C, using peg B as an auxiliary peg. The rules of the game are as follows:

a. Only one disk may be moved at a time, and it must be the top disk on one of the pegs.
b. A larger disk should never be placed on the top of a smaller disk.

Suppose we are to write a program to print out the sequence in which the disks should be moved such that all disks on peg A are finally transferred to peg C. Here it is...

main( )

{

int n = 4 ;

move ( n, 'A', 'B', 'C' ) ;

}

move ( int n, char sp, char ap, char ep )

{

if ( n == 1 )

printf ("\n Move from %c to %c ", sp, ep ) ;

else

{

move ( n - 1, sp, ep, ap ) ;

move ( 1, sp, ' ', ep ) ;

move ( n - 1, ap, sp, ep ) ;

}

}

And here is the output...

Move from A to B

Move from A to C

Move from B to C

Move from A to B

Move from C to A

Move from C to B

Move from A to B

Move from A to C

Move from B to C

Move from B to A

Move from C to A

Move from B to C

Move from A to B

Move from A to C

Move from B to C

This problem is the famous Towers of Hanoi problem, wherein three pegs are to be employed for transferring the disks with the given criteria. Here's how we go about it. We have three pegs: the starting peg, sp, the auxiliary peg ap, and the ending peg, ep, where the disks must finally be. First, using the ending peg as an auxiliary or supporting peg, we transfer all but the last disk to ap. Next the last disk is moved from sp to ep. Now, using sp as the supporting peg, all the disks are moved from ap to ep.

The three pegs are denoted by 'A', 'B' and 'C'. The recursive function move( ) is called with different combinations of these pegs as starting, auxiliary and ending pegs. Going through the following figure would be the best way to sort out how the control flows through the program.

That's recursion for you. Clean, compact and elegant, that is once you master it.