Programming Geek
Rated 4.1/5 based on 446 reviews

Solution of Tower of Hanoi Problem

Problem : There are three pegs start, auxiliary and destination. Start peg contains certain number of disks such that smaller disk is on the bigger disk. The problem is to move all the disks from start peg to destination peg following two conditions:

               1) Only one pile can be moved at a time and only from the top.
               2) A larger disk can not be placed on a smaller disk.

Algorithm :
               1) Move the top n-1 disks from start to auxiliary peg.
               2) Move the top disk from start to destination.
               3) Move the top n-1 disks from auxiliary peg to destination peg.

The movement of four disks is illustrated below:

     


The C program implementing the above algorithm:




     
//C program for solving Tower of Hanoi problem
/**
*
*@author VIKASH VIK VIKASHVVERMA
* 
*/

#include<stdio.h>

void towerofhanoi(int n,char start[], char aux[], char destination[])
{
 //base condition
 if(n==1)
 {
  printf("\n%s-->%s",start,destination);
  return;
 }
 
 //move n-1 disks from start peg to auxiliary peg
 towerofhanoi(n-1,start,destination,aux);
 //move last disks to destination peg
 printf("\n%s-->%s",start,destination);
 //move n-1 disks from auxiliary peg to destination peg
 towerofhanoi(n-1,aux,start,destination);
}

void main()
{
 int n;
 printf("Enter no. of disks:");
 
 //get number of disks
 scanf("%d",&n);
 printf("Movement of disks are : ");
 //solve Tower of Hanoi problem recursively by calling towerofhanoi(-,-,-,-) function
 towerofhanoi(n,"A","B","C");
}