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.
- Only one disk can be moved at a time.
- 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
