Tower of Hanoi Algorithm: Python, C++ Code

What is the Tower of Hanoi?

The Tower of Hanoi is a mathematical puzzle comprising three rods and numerous disks placed one over the other. It is also known as the Tower of Brahma or the Lucas tower, as the French mathematician Edouard Lucas introduced it back in 1883. This puzzle is based on legends about moving gold disks between three rods.

This puzzle has three rods and a variable number of stacked disks. Those rods are designed as cyclic towers. So, the larger disks in diameter are stacked on the bottom, and the smaller disks are stacked on top.

Initially, we are given three pegs or rods. And one of them (A, shown in the example) has all the disks stacked. We aim to move an entire stack of disks from one rod (A) to another (C) by obeying some specific rules.

Here is the initial setup of the puzzle-

And this is the final goal-

Rules of Tower of Hanoi

Here are some essential rules for the Tower of Hanoi:

• The initial state of this puzzle, all the disks will be stacked in rod one.
• The final state is all those disks from rod one will be stacked upon rod two or rod three.
• We can move an on-disk from one rod to another at any given time.
• We can only move the uppermost disk from the rod.
• A disk can’t be placed over another disk, which is smaller.

The original legend was about moving 64 disks. The priests could move one disk at a time according to the rules. According to the legend, there was a prophecy that the world would end if they could complete the act. In the time complexity section, we will show that a Tower of Hanoi setting of n disks would cost 2^n – 1 move.

So, if the priests could require 1 second to move the disks, the total Time they would need to solve the puzzle would be 2^64 – 1 second or 584,942,417,356 years, 26 days, 7 hours, and 15 seconds.

Algorithm for Tower of Hanoi

One general way to solve the Tower of Hanoi is a recursive algorithm. First, we need to decide on two rods or pegs as the source and destination, and the spare peg would be an auxiliary or helper.

Here are the steps to solve the Tower of Hanoi puzzle:

• Move the top n-1 disks from the source peg to the helper peg.
• Afterward, move the nth disk from the source peg to the destination peg.
• Finally, move the rest n-1 disks from the helper peg to the destination peg.

Note: If we have a single disk, we can directly move it from source to destination.

How to solve Tower of Hanoi Puzzle

Let’s illustrate the algorithm for three disks and consider peg A as the source, peg B as the helper, and peg C as the destination

Step 1) Initially, all the disks will be stacked on peg A.

At this stage:

Source = Peg A
Destination = Peg C
Helper = Peg B

Now, we need to move the top n-1 disks from the source to the helper.

Note: Though we can only move one disk at a time, it breaks our problem from a 3-disk problem to a 2-disk problem, which is a recursive call.

Step 2) As we call a recursive call from peg A and the destination is peg B, we will use peg C as a helper.

Notice that we are at stage one again for the same tower of Hanoi problem for two disks.

Now we need to move n-1 or one disk from source to helper, moving the smallest disk from peg A to peg C.

At this stage:

Source = peg A
Destination = peg B
Helper = peg C

Step 3) Then, according to our algorithm, the nth or 2nd disk needs should be transferred into the destination or peg B.

At this stage:

Source = peg A
Destination = peg B
Helper = peg C

Step 4) Now, we will move the n-1 disks or disk one from helper or peg C to the destination or peg B according to the third stage of our algorithm.

At this stage:

Source = peg A
Destination = peg B
Helper = peg C

Step 5) After completing the recursive call, we will return to our previous setting when the first stage of the algorithm.

Step 6) Now, in the second stage, we will move our source to our destination, which is moving disk 3 to peg C from peg A.

At this stage:

Source = peg A
Destination = peg C
Helper = peg B

Step 7) Now we can see that

d is to move the remaining disks from helper (peg B) to destination (peg C). We will use the initial source or peg A as a helper in this case.

Step 8) As we can’t move two disks simultaneously, we will call a recursive call for disk 1. According to the last step and our algorithm, a destination in this step is peg A.

At this stage:

Source = peg B
Destination = peg A
Helper = peg C

Step 9) Our recursive call is completed now. Then we move disk 2 from its source to its destination.

At this stage:

Source = peg B
Destination = peg C
Helper = peg A

Step 10) Then we move our remaining n-1 or disk 1 from helper to destination.

At this stage:

Source = peg A
Destination = peg C
Helper = peg B

Pseudo Code for Tower of Hanoi

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

Program code in C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

Output

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Program code in Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

Output:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Complexity of Tower of Hanoi

Here are the Time and Space Complexity of the Tower of Hanoi:

1) Time complexity:

If we look back at our algorithm, we can see that we are introducing a recursive call for (n-1) disks twice. Those recursive calls for (n-1) disks can be broken down into other ((n-1)-1) and so on until we get only one disk to move.

For three disks-

• Disk 3 calls a recursive function for disk two twice.
• Disk 2 calls a recursive function for disk one twice.
• Disk 1 can move within constant Time, and Time to solve for three disks.

= 2*(Time to solve for two disks) + constant Time to move disk 3

= 2*(2*time to solve for one disk + constant Time to move disk 2) + constant Time to move disk 3

= (2*2) (constant time to move disk 1) + 2*constant time to move disk 2 + constant time to move disk 3

For n disks, it can be written as –

(2^n-1 * constant time to move disk 1 + 2^n-2 * constant time to move disk 2 + ….

This geometric progression will result in O(2^n-1) or O(2ⁿ), which is exponential.

2) Space complexity

The space complexity of the Tower of Hanoi is 0(n). That’s because we need to store the sequence of the plates. When we are using the recursion, it’s using the stack. And the maximum size of the stack can be “n.” That’s why the space complexity becomes O(n).