TOWERS OF HANOI

INTRODUCTION

In this tutorial, we are going to learn about the towers of Hanoi problem. The towers of Hanoi is a logical mathematical riddle that can be solved by recursion. In this, we have three rods (1,2, and 3) and n number of disks. The main objective of this towers of Hanoi is to move the entire stack of the disks from one rod to another rod without any changes in their position i.e. the initial positions.

Let’s look at some of the basic rules to be followed when implementing the towers of Hanoi problem.

• The n number of disks should be placed in increasing order i.e. the smallest disk should be always on the top.
• Only one disk can be moved at once. The movement of two disks at a time should not be done.
• If you want to place two disks in one rod, the disk which is in the bottom should be greater than the disk at the top.
• If there are multiple disks on a rod, then the disk which is on the top is only movable I.e. a disk can only be moved if it is the uppermost disk of the stack of disks

Let’s understand the idea behind the Towers of Hanoi with an example.

Suppose, we have placed three discs in rod A, and we have to move all the discs to rod C following all the properties of the Towers of Hanoi, the movement of discs would be taken as follows.

MOVE DISC FROM 1 TO 3
MOVE DISC FROM 1 TO 2
MOVE DISC FROM 3 TO 2
MOVE DISC FROM 1 TO 3
MOVE DISC FROM 2 TO 1
MOVE DISC FROM 2 TO 3
MOVE DISC FROM 1 TO 3

This would be the possible movement of the discs if we are supposed to move all the discs from A to C, following the properties of the Towers of Hanoi. Let’s look at the pictorial representation of the Towers of Hanoi

Let’s look at the hierarchy tree of the towers of Hanoi

C++ Code:

#include <iostream>
using namespace std;

void TOH(int n, int A,int B,int C){
  if(n>0){
    TOH(n-1,A,C,B);
    cout<<"MOVE DISC FROM : "<<A<<" TO "<<C<<endl;
    TOH(n-1,B,A,C);
  }
}

int main() {
    int n;
    cin>>n;
    int A=1,B=2,C=3;
    TOH(n,A,B,C);
}

Python code:

def TOH(n,A,B,C):
  if n>0:
    TOH(n-1,A,C,B)
    print("MOVE DISC FROM :",A,"TO",C)
    TOH(n-1,B,A,C)

n = int(input())
A=1
B=2
C=3
(TOH(n,A,B,C))

JAVA code:

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int n = s.nextInt();
      int A=1,B=2,C=3;
      Towers t = new Towers();
      t.TOH(n,A,B,C);
  }
}
class Towers {
  void TOH(int n, int A,int B, int C){
    if(n>0){
    TOH(n-1,A,C,B);
    System.out.println("MOVE DISC FROM : "+A+" TO "+C);
    TOH(n-1,B,A,C);
    }
  }
}

Input: 3

Output:

MOVE DISC FROM : 1 TO 3
MOVE DISC FROM : 1 TO 2
MOVE DISC FROM : 3 TO 2
MOVE DISC FROM : 1 TO 3
MOVE DISC FROM : 2 TO 1
MOVE DISC FROM : 2 TO 3
MOVE DISC FROM : 1 TO 3

The time complexity of the code is O(2ⁿ), as there are two possibilities for every disc.

The space complexity of the code is O(N) as we use a call stack to store the recursive call functions.

CONCLUSION

That’s it from this tutorial. Hope you guys found It interesting. We have learned about the basic definition of the Towers of Hanoi, the properties of the Towers of Hanoi, the idea behind the Towers of Hanoi, the tree hierarchy of the towers of Hanoi and solved the Towers of Hanoi problem in different programming languages. Happy coding!