Tower of Hanoi game is a puzzle invented by French mathematician Édouard Lucas in 1883.
There is a story about an ancient temple in India (Some say it’s in Vietnam – hence the name Hanoi) has a large room with three towers surrounded by 64 golden disks.
These disks are continuously moved by priests in the temple. According to a prophecy, when the last move of the puzzle is completed the world will end.
These priests acting on the prophecy, follow the immutable rule by Lord Brahma of moving these disk one at a time.
Hence this puzzle is often called Tower of Brahma puzzle.
Tower of Hanoi is one of the classic problems to look at if you want to learn recursion.
It is good to understand how recursive solutions are arrived at and how parameters for this recursion are implemented.
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.
Before we proceed, let’s understand Recursion –
When a function calls itself, it’s called Recursion.
It will be easier for those who have seen the movie Inception.
Leonardo had a dream, in that dream he had another dream, in that dream he had yet another dream, and that goes on.
So it’s like there is a function called dream()dream(), and we are just calling it in itself.
function dream() print "Dreaming" dream()
Recursion is useful in solving problems which can be broken down into smaller problems of the same kind.
But when it comes to solving problems using Recursion there are several things to be taken care of.
Let’s take a simple example and try to understand those.
Following is the pseudo code of finding the factorial of a given number XX using recursion.
function factorial(x) if x is 0 // base case return 1 return x*factorial(x-1) // break into smaller problem(s)
Detailed explanation to Recursion can be found – Here
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.
Looks simple, Right!
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.
But what if we have 3 disks – 1,2, and 3 stacked in peg A.
To move the stack to peg B you would have to expose disk 3 and to do that disk 1 and 2 have to be moved to peg C.
So by ensuring that you do not break the rules, using the above subsets of 3 steps in the previous case, you would move disk 1 and 2 to peg C, leaving disk 3 exposed with no disk above it.
Now to solve the problem, recursively move disk 3 from peg A to peg B.
Then disk 1 from peg C to peg A. After which disk 2 can be moved above disk 3 at peg B.
The puzzle is finally completed by moving disk 1 from peg A over disk 2 and 3 at peg B.
Would you like to get updates once a month on our latest articles? We won’t spam, we promise. Subscribe now to The HackerEarth Blog!
What if you have 4 disks?
Eventually, you figure out that there is some pattern to the puzzle and with each increment in disks, the pattern could be followed recursively.
While the 3-disk puzzle required 7 steps. 4-disk requires 7+1+7 = 15 steps to be solved.
Check the GIF here for 4 disks
void tower(int a,char from,char aux,char to){ if(a==1){ cout<<"\t\tMove disc 1 from "<<from<<" to "<<to<<"\n"; return; } else{ tower(a-1,from,to,aux); cout<<"\t\tMove disc "<<a<<" from "<<from<<" to "<<to<<"\n"; tower(a-1,aux,from,to); } }
Call the function ‘tower’ in the main program
void main(){ clrscr(); int n; cout<<"\n\t\t*****Tower of Hanoi*****\n"; cout<<"\t\tEnter number of discs : "; cin>>n; cout<<"\n\n"; tower(n,'A','B','C'); getch(); }
By now, you might have identified that to move N disks from one peg to another, you need \(2^{N}-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^{N}-1\)
The question is what is the minimum number of moves\((a_N)\) required to move all the \(N-\)disks to another peg.
Let’s look at a recursive solution
One can already see that \(a_1=1, a_2=3, a_3)=7 \) and so on.
For a given \(N\) number of disks, the way to accomplish the task in a minimum number of steps is:
Therefore, the recurrence relation for this puzzle would become:
\(\displaystyle a_1=1, a_2=3; a_N=2a_{N-1}+1; N\geq2 \)
Now one can solve this relation in an iteration as follows-
Suppose that these priests are highly powerful and can move these massive disks at a speed of 1 per second per hour every day.
At this speed, they would need 2^64 -1 move to complete the task.
That is, 18,446,744,073,709,551,615 moves to complete, which would take about 580 billion years.
Considering our Milky Way is about 13.21 billion years old and our planet is only 5 billion years old, that is a lot of time for the prophecy to be true.
Now that you have understood the algorithm and reasoning behind the Tower of Hanoi problem, it’s time to take up a small assessment to test your understanding of the Tower of Hanoi
Tower of Hanoi is a common dynamic programming problem used in various competitive programming challenges.
Here is one such question from HackerEarth Challenge
Q. Bob and Alice like to play the game Tower of Hanoi. One day Alice challenges Bob to build the tallest tower from a set of disks of different height and radius. The Tower of Hanoi can be built by stacking disks on top of each other. To put disk A on top of disk B, the radius and height of A must be strictly smaller than those of B. Help Bob win the challenge.
Here is the Tower of Hanoi program using C++
#include <bits/stdc++.h> #define lli long long using namespace std; lli dp[202]; int main() { int t,n; lli x,y; cin >> t; assert(t<=10); while ( t-- ) { cin >> n; assert(n<=200); vector < pair<lli,lli> > v; for ( int i = 0; i < n; i++ ) { cin >> x >> y; assert(x<=1000000000); assert(y<=1000000000); v.push_back(make_pair(x,y)); } sort(v.begin(),v.end()); dp[0] = v[0].second; lli ans = v[0].second; for ( int i = 1; i < n; i++ ) { dp[i] = v[i].second; for ( int j = 0; j < i; j++ ) { if ( v[i].second > v[j].second && v[i].first > v[j].first ) dp[i] = max(dp[i], dp[j]+v[i].second); } ans = max(ans, dp[i]); } cout << ans << endl; } return 0; }
Time to end the world on a doomsday or by Tower of Hanoi all can be calculated by mathematics.
Mathematics holds the solution for most of the complex problems, from football betting to banking.
Practice and learn more such algorithms and on CodeMonk and participate in HackerEarth challenges.
Subscribe now for more such article on Algorithms.
Introduction In today's dynamic workplaces, a strong HR department is no longer a luxury –…
Job task analysis is a crucial process for understanding the specific duties and skills required…
In today's competitive talent landscape, attracting top candidates requires going beyond traditional job board postings.…
Finding the perfect fit for your team can feel like searching for a unicorn. But…
Recruitment forms a strong foundation to build an effective team. However, do you know if…
Introduction Performance appraisal has seen a tremendous change over the years. It is no longer…