The Hanoi Tower is a problem that E. Lucas brought to the western world in 1883. However, the origins of this game may be traced back to ancient Hindu civilization. It is linked with a Hindu temple tale in which someone allegedly employed the puzzle to improve the mental discipline of young priests. So, in this tutorial, you will explore the Tower of Hanoi problem and, ultimately, you will create a solution for it using the C programming language.
Understanding Tower of Hanoi Puzzle
The Tower of Hanoi is a mathematical problem composed of three towers and numerous rings arranged in increasing order of their diameters. The number of towers is constant for this problem, whereas the player can vary the number of rings he wants to use. The image given below depicts the setup of the TOH puzzle.
There are three towers in this diagram. And one of the towers is decked up with many discs, having the greatest diameter disc at the bottom and the smallest diameter disc at the top. This tower is known as the source tower. And the objective of this game is to move all rings present at the source tower to the destination tower without altering their sequence.
Before you get ahead of yourself and deem this problem trivial, there are few crucial aspects to consider. In this problem, you are allowed to move only one disc at a time. Furthermore, you are not enabled to place a larger disc on top of a smaller disc at any instance. That means the approach shown in the image below can never result in an accurate solution.
Moving forward, let’s look at all the rules involved in this TOH puzzle.
Rules of Tower of Hanoi Puzzle
The Tower of Hanoi problem is solved using the set of rules given below:
- Only one disc can be moved at a time.
- Only the top disc of one stack can be transferred to the top of another stack or an empty rod.
- Larger discs cannot be stacked over smaller ones.
The complexity of this problem can be mapped by evaluating the number of possible moves. The least movements needed to solve the Tower of Hanoi problem with n discs are 2n-1.
Logical Approach to Implement Solution For TOH Problem
In this section, you will implement a logical solution to the four-ring TOH problem. The initial problem setup will be as represented in the image below.
In order to solve this problem, you are going to utilize an auxiliary or Helper tower. The first move you will make will be to transfer the orange ring to the helper tower.
Next, you can move the green disc to the destination tower.
After that, you can move the orange disc to the destination tower. You will place this orange disc above the green disc.
Now, the helper tower is empty. So, you will take out the yellow ring from the source tower to the helper tower.
Next, you will move the orange ring to the source tower.
Further, you will move the green ring to the helper tower.
Next, you will move the orange ring to the helper tower. This move will make room for the transfer of the largest disc to the destination tower.
Here, you can bring the largest disc to the destination tower. However, you still need to bring three more discs to our destination tower in order to solve this TOH problem.
Here, you will move the orange ring to the destination tower.
After that, you will move the green ring to the source tower. And you will also transfer the orange ring to the source tower. These two moves will allow you to transfer the second largest disc to the destination tower.
Here, you will place the second ring at the destination tower. Now, you are only left with the arrangement of two more rings.
You will move the orange ring to the helper tower and the green ring to the destination tower.
Finally, you will move the orange disc to the destination tower.
Coding Implementation of TOH Solution
The TOH puzzle can be solved using a recursive programming paradigm. The C program for building a solution to the four-ring TOH problem is given below.
|
#include<stdio.h> #include<conio.h> void TOH(int n, char source, char destination, char helper_t){ if(n==0){ return 0; } TOH(n-1,source, helper_t,destination); printf("\n Move disc %d from tower %c to tower %c",n, source, destination); TOH(n-1, helper_t, destination,source); } int main() { TOH(4, 'A','B','C'); return 0; } |
Output:
The console representing 15 ring movements to reach the final solution.
Conclusion
In this Tower of Hanoi tutorial, you learned what the TOH problem is. After that, you discovered the logical approach to implement a solution for the TOH problem. Finally, you also looked at the programming implementation of the TOH solution using the C programming language.
If you're looking for more in-depth training that goes beyond data structures and covers the foundations of interactive application development, Simplilearn's Software Development Courses will prove ideal for you. The courses in this catalog can help you improve your odds of becoming a software developer by aiding you in mastering the art of software development. So, go ahead and start exploring!
Have any questions about this article on the Tower of Hanoi problem? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!
