Have you heard about this tower of Hanoi problem? you can find this in the syllabus of data structure. If you are not aware of this problem then do not panic I will explain to you what is the problem with the tower of Hanoi and How to solve the Tower of Hanoi Problem.
Within this blog post(How to solve the Tower of Hanoi Problem), we are going to share How long it takes to solve the Tower of Hanoi. How many moves does it take to solve the Tower of Hanoi for 3 disks? How many moves does it take to solve the Tower of Hanoi for 4 disks? Tower of Hanoi solution, Tower of Hanoi recursive solution.
What exactly the Tower of Hanoi problem is?
The tower of Hanoi problem is the problem of shifting a few disks from one peg to another by using a few more pegs in between for help. Peg is noting but a pole where we insert the disk. This process will have some conditions like:
- Only the top disk may be moved at a time.
- Only smaller disks placed on a larger disk
If you still could not get this tower of Hanoi problem then I make it more simple so that you can understand it in a better way.
See, the above image here we have three pegs A, B, and C, and five disks inserted into peg A in decreasing order. This means that the largest disk is at the bottom and the smallest is at the top.
Now the tower of Hanoi problem or main objective is that we need to move the disk from peg A to peg C using peg B temporarily by following the given below rule.
We can move only the top disk at a time. Another one is that we can place only a smaller disk on a larger disk. That means we can not put a larger disk over smaller ones at any move of a disk. A disk may be moved from any peg to any other peg.
How to solve the Tower of Hanoi problem? A solution to the tower of Hanoi problem for n=3 disk?
So, now you would have understood the problem of the tower of Hanoi. Now I show you how to solve this problem for three disks or n=3. See the below image for the same.
You can see all the moves to get the final solution of the tower of Hanoi in the above-given image.
In the first image, we have all three disks in pole A in decreasing order, and then our objective is to shift all these disks to tower C in the same order…
… of placement now means the biggest disk at the bottom and the smallest disk at the top. We can take the temporary help of pole B in solving this problem.
Now we start moving the disk and first we move the top Ist disk from A and keep it at pole C. After this, we move the second disk from A and keep it at pole B.
Now we move the Ist disk from pole C and put it at pole B. After this, we moved the third disk from A and put it at pole C. We move the Ist disk from B to pole A.
Now we move the second disk from B to pole C. After this, we move the first disk from A to C. And our object as per the tower of Hanoi problem has been achieved.
So this was the overall solution of the tower of Hanoi with the use of three disks.
How to write the Tower of Hanoi Algorithm? / Tower of Hanoi algorithm in C?
An algorithm is nothing but a set of instructions or statements to complete a program. See the Tower of Hanoi Algorithm below.
1. Given n disk on peg A.
2. Repeat step 3 until no disk is left.
3. Move one disk at a time, such that no larger disk can be placed over a smaller disk.
4. Exit
Write a C program for the Tower of Hanoi. / Tower of Hanoi algorithm in C?
See the c program for a tower of Hanoi below.
#include<stdio.h>
void hanoi(int n, char initial, char final, char temp)
{
if(n==1)
{
printf("move disk 1 from peg % c to % c\n",initial, final);
return;
}
hanoi(n-1, initial, temp, final);
printf("move disk%d from peg %c to %c\n",n, initial, final);
hanoi(n-1, temp, final, initial);
}
void main()
{
int n;
printf("Enter the number of disk to be moved");
scanf("%d", &n);
hanoi(n, 'A', 'C', 'B');
}
You can also go through a few more amazing blog links below related to Data Structure:
What is a strongly connected graph? / How do you know if a graph is strongly connected…
Graph: Types of the graph in data structure…
AVL Tree In Data Structure…
What is a tree in the data structure…
What is compaction in memory management…
What is garbage collection and how does it work…
Dynamic Memory Management…
Josephus problem & Circular linked list…
What is a circular linked list…
What are the linked lists in the data structure and their types…
What is the priority queue with an example…
the difference between stack and queue…
What is meant by backtracking in the data structure…
You can also check out the difference between Stack vs Queue.
What are the stack and its operations…
How to solve the Tower of Hanoi Problem…
What is recursion with an example…
The complexity of an algorithm…
What are the data structure and its types…
What is the data structure…
What is a queue in a data structure…
Conclusion:
The tower of Hanoi problem is the problem of pole disks and their displacement or movement as per the rule. The Tower of Hanoi has three pegs or poles and there could be n number of the disk. In the initial few disks are kept in either pole in descending order and then we need to move all these disks to another peg in the same descending order with the help of the third pole and following some sets of rules like We can move only the top disk at a time and smaller disk always is above of larger disk.| How to solve the Tower of Hanoi Problem|
Using this blog post(How to solve the Tower of Hanoi Problem) we have gone through How long does it take to solve the Tower of Hanoi? How many moves does it take to solve the Tower of Hanoi for 3 disks? How many moves does it take to solve the Tower of Hanoi for 4 disks? Tower of Hanoi solution, Tower of Hanoi recursive solution.
In the case of any queries, you can write to us at a5theorys@gmail.com we will get back to you ASAP.
Hope! you would have enjoyed this post(How to solve the Tower of Hanoi Problem).
Please feel free to give your important feedback in the comment section below.
Have a great time! Sayonara!
