Tower of Hanoi is a very famous game.

In this game there are 3 pegs and N number of disks placed one over the other in decreasing size.

The objective of this game is to move the disks one by one from the first peg to the last peg.

And there is only ONE condition, we can not place a bigger disk on top of a smaller disk.

To solve this game we will follow 3 simple steps recursively.

We will use a general notation:

T(N, Beg, Aux, End)

T denotes our procedure

N denotes the number of disks

Beg is the initial peg

Aux is the auxiliary peg

End is the final peg

```
1. T(N-1, Beg, End, Aux)
2. T(1, Beg, Aux, End)
3. T(N-1, Aux, Beg, End)
Step 1 says: Move top (N-1) disks from Beg to Aux peg.
Step 2 says: Move 1 disk from Beg to End peg.
Step 3 says: Move top (N-1) disks from Aux to End peg.
```

```
/*
N = Number of disks
Beg, Aux, End are the pegs
*/
T(N, Beg, Aux, End)
Begin
if N = 1 then
Print: Beg --> End;
else
Call T(N-1, Beg, End, Aux);
Call T(1, Beg, Aux, End);
Call T(N-1, Aux, Beg, End);
endif
End
```

If there are N disks then we can solve the game in minimum
2^{N} – 1 moves
Example: N = 3
Minimum moves required = 2^{3} – 1 = 7

```
#include <stdio.h>
void t(int n, char beg, char aux, char end);
int main(){
printf("Moves\n");
t(3, 'a', 'b', 'c'); //N = 3 (no. of disks) a, b, c are the three pegs
return 0;
}//main() ends here
void t(int n, char beg, char aux, char end){
if(n == 1){
printf("%c --> %c\n", beg, end);
}else{
t(n-1, beg, end, aux);
t(1, beg, aux, end);
t(n-1, aux, beg, end);
}
}//t() ends here
```

Recently Added

- Bootstrap - Dropdowns Bootstrap
- Bootstrap - Panels Bootstrap
- Bootstrap - List group Bootstrap
- Bootstrap - Media Object Bootstrap
- Bootstrap - Thumbnails Bootstrap
- Upload file to remote server using FTP and SFTP Client - Windows, Mac, Linux Howto Website
- Setting up name servers - Pointing domain name to hosting server Howto Website
- Getting a domain and hosting plan for your website Howto Website
- Getting started with free blog and website Howto Website
- How to Website - Introduction Howto Website