Tower Of Hanoi

Introduction To Tower Of Hanoi

Mathematics is boring until we have to solve worksheets and homework. But there are more creative ways to improve your mathematical muscles.

Have you ever tried a tic-tac-toe game or more strategic games like sudoku solver and chess? If you have, you will know how fun, entertaining, and sometimes useful they are. Similarly, the Tower Of Hanoi is one of the same kind.

The Tower Of Hanoi is one of the most classic problems of recursion. Through this problem, you can see how recursion works.

History of Tower Of Hanoi

First, let’s talk about the history of the Tower of Hanoi puzzle.

It is said that the Tower Of Hanoi is based on a story about an ancient temple of India, which is located in Kashi-Vishwanath. This temple contains a large room with three towers which is surrounded by 64 golden sticks.

These sticks are continuously moved by some Brahmin priests. These priests have been moving the sticks following the rules framed by Lord Brahma.

According to a prophecy, the day at which the priests will perform the last move of the game, then at that day, the world will end.

About The Game

The game of Tower of Hanoi consists of three pegs or towers along with ‘N’ number of Discs. The game’s objective is to move all the Discs from Tower A to Tower B with the help of Tower C.

The rules which were designed for the puzzle are:

1. Only one Disc can be moved at a time.
2. No larger Disc can be placed over a smaller Disc.

This problem will be solved with the help of recursion. So first, let’s have a look at recursion.

Recursion

Recursion refers to a function calling itself.

Recursion basically solves such types of problems that require repetition in the process. Apart from this, many things should be taken care of in the recursive problem.

1. Base Case – It is the smallest valid case for the problem at which the recursion terminates.
2. Smaller problem – The bigger problem is broken down into smaller problems. And then this problem recursively will build us the entire solution.

You can learn more about recursion from here and can also practice some problems based on recursion.

Algorithm

Now let’s try recursion in solving the problem “Tower Of Hanoi.” 

Let us try to understand it with an example of 2 Discs.

1. Move Disc 1 from tower A to tower C.
2. Move Disc 2 from tower A to tower B.
3. Move Disc 1 from tower C to tower A.

                                            Tower A          Tower B          Tower C

We can see that three moves will be required to shift 2 Discs from tower A to tower B with the help of an intermediary tower C.

Now let’s try to understand it with an example of 3 Discs.

To move all the Discs from tower A to tower B, you have to expose the last Disc in the stack of tower A to shift it from tower A to tower B.

So keeping the above rules in mind, move Disc 1 and Disc 2 from tower A to tower C leaving Disc 3 exposed.

 For the problem with three discs, the following steps should be made:

1. Move disc 1 from tower A to tower B.
2. Move disc 2 from tower A to tower C. 
3. Move disc 1 from tower B to tower C.
4. Move Disc 3 from tower A to tower B.
5. Move Disc 1 from tower C to tower A.
6. Move Disc 2 from tower C to tower B.
7. Move Disc 1 from tower A to tower B. 

                                      Tower A           Tower B             Tower C

We can see that 7 moves will be required to shift 3 Discs from tower A to tower B with the help of an intermediary tower C.

Now let us derive the general solution for the ‘N’ number of discs.

1. Recursively, move top’ N – 1′ discs from tower A to tower C.
2. Move the ‘Nth’ disc from tower A to tower B.
3. Now recursively move ‘N – 1’ discs from tower C to tower B.

Approach For the Recursive Code

After going through the discussion on the Algorithm above, you can try to write the recursive code by following the below-mentioned steps:

1. Create a function, let’s say towerOfHanoi() with integer variable ‘N’ representing the number of discs, three-character variables, say ‘source,’ ‘dest’ and ‘inter’ representing source, destination, and intermediate positions.
2. Design a base Case for the solution as if ‘discs’ = 1, then move it from ‘source’ to ‘dest.’
3. Else recursively call the function’ towerOfHanoi()’ for N – 1 discs to move them from ‘source’ to ‘inter.’
4. Move the Nth disc from ‘source’ to ‘dest.’
5. Now again, recursively call the function’ towerOfHanoi()’ for N – 1 discs to move them from ‘inter’ to ‘dest.’

Below is the code snippet for the same approach for your reference.

void towerOfHanoi(int N, char source, char inter, char dest)
{
    // Base Case.
    if(N == 1)
    {
      cout<< "\t\tMove Disc 1 from " << source << " to " << dest << "\n";
      return;
    }

    else
    {
      // Moving N - 1 discs from tower A to tower C.
       towerofHanoi(N - 1, source, dest, inter);

       // Moving Nth disc from tower A to tower B.
      cout<< "\t\tMove disc " << N << " from " << source <<" to "<< dest <<"\n";

       // Moving N - 1 discs from tower C to tower B.
      towerofHanoi(N - 1, inter, source, dest);
    }
}

You can practice this problem from here.

Mathematical Analysis

Let us now analyze the minimum number of moves required to shift all discs from tower A to tower B.

We can observe the following things from the above discussion:

1. For N = 1, the minimum number of moves required to shift from tower A to tower B is 1.
2. For N = 2, the minimum number of moves required to shift from tower A to tower B is 3.
3. For N = 3, the minimum number of moves required to shift from tower A to tower B is 7.

Can you observe some pattern or series from the above points?

Yes, you guessed it right. The number of moves almost doubles every time you insert another disk in the stack.

Moves₁ = 1

Moves₂ = 3

Moves₃ = 7

So, the expression for the N discs will become,

 MovesN = (2 * MovesN-1) + 1 = 2N - 1.

Now, let’s try to prove this expression.

MovesN = (2 * MovesN-1) + 1
             = (2 * (2 * MovesN-2 + 1) ) + 1
             = 22 * MovesN-2 + 2 + 1
             = 23 * MovesN-3 + 22 + 2 + 1
             = 2N - 1 * MovesN - (N - 1) + 2N - 2 + …… + 22 + 2 + 1
             = 2N - 1.

Frequently Asked Questions For Tower Of Hanoi

Key Takeaways

In this article, we discussed the famous mathematical puzzle Tower of Hanoi and the approach to solving it. We also analyzed the mathematical expression for the minimum moves to shift ‘N’ discs from source to destination.

The approach is based upon the recursion. To read more about recursion, visit this link. You can also try solving problems on CodeStudio. If you think that this blog helped you, then share it with your friends!.

Until then, All the best for your future endeavors, and Keep Coding.