Method To Solve Tower Of Hanoi Problem

Share

Introduction

Tower of Hanoi (TOH) is a math puzzle problem. Where we have three rods i.e. source(A), auxiliary(B) and destination(C) and n disks. The objective of the puzzle is to move all disks from source rod to destination rod by following rules:

  1. Only one disk can be moved at a time.
  2. Only the topmost disc can be picked up from the stand.
  3. No bigger disc will be placed at the top of the smaller disc.

This problem can be solved using recursion. Where recursion is a process in which a function calls itself directly or indirectly and the function itself is called a recursion function.

Several Cases In TOH problem

Case 1:If only one disc is given, then move a disk from A to B directly.

Case 2:If two disks are given, then

  • Move a disk from A to B.
  • Then move a disk from A to C.
  • Finally, move a disk from B to C.

Case 3:If 3 disks are given,

  • Move 2 disks from A to B.
  • Then move a disk from A to C.
  • Finally, Move 2 disks from B to C.

For n disks

  • Move n-1 disks from source to auxiliary, using C.
  • Then move a disk from A to C.
  • Finally, move n-1 disks from B to C using A.

Algorithm

Step 1:Start
Step 2:If n==1;
       move a single disks from source to destination
Step 3:If n>1;
       i)let temp be the other pole than other source and destination.
       ii)Move a tower of n-1 disks from source to auxiliary.
       iii)Move a single disks from source to destination.
        iv)Move a tower of n-1 disks from auxiliary to destination.
Step 4:End

Program code

#include<stdio.h>
void transfer(int n,char src,char trt,char auxi)
{
	if(n==1)
	{
		printf("\n move disk %d from peg %c to peg %c",n,src,trt);
	}
	else
	{
		transfer(n-1,src,auxi,trt);
		printf("\n move disk %d from peg %c to peg %c",n,src,trt);
		transfer(n-1,src,auxi,trt);
	}
}
int main()
{
	int n;
	printf("\nEnter th number of disk in source peg:");
	scanf("%d",&n);
	transfer(n,'s','t','a');
	return 0;
}

Read about: Quick sort, Selection sort

Share
%d bloggers like this: