# Method To Solve Tower Of Hanoi Problem

# 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:

- Only one disk can be moved at a time.
- Only the topmost disc can be picked up from the stand.
- 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