Tower of Hanoi recursion game algorithm explained

Tower of Hanoi game is a puzzle invented by French mathematician Édouard Lucas in 1883.

History of Tower of Hanoi

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.

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.

1. Only one disk can be moved at a time.
2. No disk can be placed on top of the smaller disk.

Before we proceed, let’s understand Recursion –

What is 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\left(\right)$, 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 $X$ 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

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.

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?

• Recursively solve the problem of moving disk 1,2, and 3 from peg A to peg C
• Move disk 4 from A to C
• Recursively solve the problem of moving disk 1,2 and 3 from peg C to peg B

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

 

• Create a function Tower with int ‘a’ – for number of disks, char ‘from’ – for from peg, char ‘aux’ – for a secondary peg, char ‘to’ – for destination peg
• Put ‘if’ loop
• If (a=1) i.e. if number of disk = 1, move it from ‘initial peg’ to the ‘destination peg’
• Else, call function tower for ‘a-1’ i.e. the number of disk -1, recall function tower for n-1 disk and move it ‘from’ to ‘to’
• Recall function again using recursion until an or number of the disk is 1.

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();
}

Tower of Hanoi maths explained

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:

1. Move the top \(N-1\) disks to an intermediate peg.
2. Move the bottom disk to the destination peg.
3. Finally, move the \(N-1\) disks from the intermediate peg to the destination peg.

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-

 

But what about the prophecy for the tower of Hanoi where the priests are using 64 disks?

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.

Tower of Hanoi dynamic programming problem

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 recursion sample problem in C++

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.