Tower Of Hanoi – Algorithm And Implementation

Algorithms

Tower Of Hanoi or TOH in short, is a game containing three pegs A, B, C and A contains disks of different diameters in such a way that larger disk is always below a smaller disk. The objective is to move the disks from peg A to peg B, using peg C as auxiliary following following rules :-

Only one disk can be moved among the towers at any given time.
Only the “top” disk can be removed.
No large disk can sit over a small disk.

Following GIF image represents the solving of Tower Of Hanoi with three disks.

Tower of Hanoi puzzle with n disks can be solved in minimum 2ⁿ−1 steps. This presentation shows that a puzzle with 3 disks has taken 2³ – 1 = 7 steps.

Algorithm Of Tower Of Hanoi Puzzle

A = source peg, B = destination peg, C = auxiliary peg

If n = 1, move the single disk from A to B and stop.
Move the top n-1 disks from A to C(auxiliary peg).
Move the remaining nth disk from A to B.
Move the n-1 disk from C to B using A as auxiliary.

Pseudo code of Tower Of Hanoi


START
Procedure Hanoi(disk, source, dest, aux)
   IF disk == 1, THEN
      move disk from source to dest          // Step 1   
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 2
      move disk from source to dest          // Step 3
      Hanoi(disk - 1, aux, dest, source)     // Step 4
   END IF
END Procedure
STOP

C function to solve Tower Of Hanoi Puzzle


// C function to solve tower of hanoi puzzle recursively
void towerOfHanoi(int n, char from, char to, char aux) 
{ 
    if (n == 1) 
    { 
        printf("\n Move disk 1 from rod %c to rod %c", from, to); 
        return; 
    } 
    towerOfHanoi(n-1, from, aux, to); 
    printf("\n Move disk %d from rod %c to rod %c", n, from, to); 
    towerOfHanoi(n-1, aux, to, from); 
}