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