## Tower Of Honoi Program

##### What is the game of Tower of Hanoi?

Tower of Hanoi consists of three pegs or towers with n disks placed one over the other. The objective of the puzzle is to move the stack to another peg following these simple rules.

1. Only one disk can be moved at a time.
2. No disk can be placed on top of the smaller disk.
##### Tower of Hanoi algorithm explained

Let’s try to solve a puzzle – Tower of Hanoi using recursion. Take an example with 2 disks: Disk 1 on top of Disk 2 at peg A. The target is to move both these disks to peg B. Move Disk 1 from peg A to peg C. Then move disk 2 from peg A to peg B and, finally, move disk 1 from peg C to peg B. This solution takes 3 steps. You can easily move this stack from peg B to any other peg using these 3 steps.

#include
void TofH(int,char,char,char,int*);
int main() {
int n,m=0;
printf("enter the number of disks:\n");
scanf("%d",&n);
TofH(n,'s','t','d',&m);
printf("number of moves=%d\n",m);
return 0;
}
void TofH(int n,char s,char t,char d,int *m) {
if(n==1)
{
printf("move disc %d from peg %c to peg %c\n",n,s,d);
(*m)++;
return;
}
else
{
TofH(n-1,s,d,t,m);
printf("move disc %d from peg %c to peg %c\n",n,s,d);
(*m)++;
TofH(n-1,t,s,d,m);
}
}
##############################################
OUTPUT:
enter the number of disks:
4
move disc 1 from peg s to peg t
move disc 2 from peg s to peg d
move disc 1 from peg t to peg d
move disc 3 from peg s to peg t
move disc 1 from peg d to peg s
move disc 2 from peg d to peg t
move disc 1 from peg s to peg t
move disc 4 from peg s to peg d
move disc 1 from peg t to peg d
move disc 2 from peg t to peg s
move disc 1 from peg d to peg s
move disc 3 from peg t to peg d
move disc 1 from peg s to peg t
move disc 2 from peg s to peg d
move disc 1 from peg t to peg d
number of moves =15
##### Tower of Hanoi maths explained

By now, you might have identified that to move N disks from one peg to another, you need 2𝑁−1. So, the number of steps almost double every time you insert another disk in the stack. Let us prove that the number of steps in 2𝑁−1 For a given 𝑁 number of disks, the way to accomplish the task in a minimum number of steps is: Move the top 𝑁−1 disks to an intermediate peg. Move the bottom disk to the destination peg. Finally, move the 𝑁−1 disks from the intermediate peg to the destination peg. Therefore, the recurrence relation for this puzzle would become: 𝑎1=1,𝑎2=3;𝑎𝑁=2𝑎𝑁−1+1;𝑁≥2