Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Iterative Approach
3.1.
Implementation in Java
3.2.
Implementation in C++
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
How many approaches are there to solve the Tower of Hanoi problem?
4.2.
What do you mean by Stack Data Structure?
4.3.
What is the difference between iterative and recursive algorithms?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Iterative Tower of Hanoi

Author Soumya Agrawal
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Tower of Hanoi is a famous game or puzzle consisting of three rods with some disks of various sizes in which we have to shift the disks from one rod to another to get arranged in ascending order. There will be some conditions that we need to follow to place the disks in a particular order.

The Tower of Hanoi problem can be solved using the Recursive method, which is better than the iterative one. We will discuss the conditions and the code to solve the iterative solution of the Tower of Hanoi. (Also see Data Structures)

Without any further delays, let’s move on to the problem statement.

Problem Statement

We will be given three rods and ‘n’ a number of disks piled on top of each other. Disks are arranged to end up in ascending order, i.e., the disk having the smallest diameter on the top. 

Objective: The objective of this puzzle is to move all the disks from one pole(source pole) to another pole(destination pole) with the help of the third pole in between, known as the auxiliary pole. This will be achieved by using two rules.

  1. Only one disk can be moved at a time.
  2. A disk with a larger diameter can’t be placed above the smaller ones on any poles.
     

To solve this problem, we will see the simple iterative approach with the help of an example and code.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Iterative Approach

We will follow three simple steps to solve the problem.

  1. Calculate the total number of moves required 2n-1, where n is the number of disks.
  2. Suppose the number of disks is even, then interchange the destination and pole and the auxiliary pole. This rule will be clear with the help of an example.
  3. For i = 1 to the total number of moves(Number of moves is calculated with the help of the above formula.)
  •  If i%3==1, Then there will be movement of the top disk from source to destination pole or vice versa.
  •  If i%3==2, Then there will be movement of the top disk from the source to an auxiliary pole or vice versa.
  •  If i%3==0, Then there will be movement of the top disk from auxiliary to destination pole or vice versa.

 

Let’s understand the example with the pictorial representation of it.

Suppose n=3, then the total number of moves will be 23-1=8-1=7.

 

Illustration

 

Now, when i=1,(1%3==1) so there will be movement of the disk between the source(S) and destination(D) pole.

 

step 1

 

Now, when i=2,(2%3==2) so there will be movement of the disk between the source(S) and auxiliary(A) pole.

step 2

 

Now, when i=3,(3%3==0) so there will be movement of the disk between auxiliary(A) and destination(D) pole.

 

step 3

 

Now, when i=4,(4%3==1) so there will be movement of the disk between Source(s) and destination(D) pole.

step 4

 

Now, when i=5,(5%3==2) so there will be movement of the disk between the source(S) and auxiliary(A) pole.

 

step 5

 

Now, when i=6,(6%3==0) so there will be movement of the disk between auxiliary(A) and destination(D) pole.

 

step 6

 

Now, when i=7,(7%3==1) so there will be movement of the disk between source(S) and destination(D) pole.

 

step 7

 

Note: All these 3 disks are of different sizes. Disk named ‘3’ is the largest and ‘1’ is the smallest.

 

example animation

 

Please try to solve Tower of Hanoi on Coding Ninjas Studio before stepping into the solution

Implementation in Java

To write the iterative approach, we will use Stack Data Structure. The stack will store and remove the disks in LIFO(Last In First Order) principle. 

import java.util.*;
import java.lang.*;
import java.io.*;

// Tower of Hanoi
class Solution {

    //Stack
    class Stack {
        int capacity;
        int top;
        int arr[];
    }

    // Create Stack
    Stack create(int capacity) {

        Stack stack = new Stack();
        stack.capacity = capacity;
        stack.top = -1;
        stack.arr = new int[capacity];

        return stack;
    }

    //Stack is full when the top is equal
    // to the last index
    boolean isFull(Stack stack) {
        return (stack.top == stack.capacity - 1);
    }

    // To check Stack is empty or not
    boolean isEmpty(Stack stack) {
        return (stack.top == -1);
    }

    //Function to add an item in Stack
    void push(Stack stack, int item) {
        if (isFull(stack))
            return;

        stack.arr[++stack.top] = item;
    }

    //Function to remove an item from Stack
    int pop(Stack stack) {

        if (isEmpty(stack))
            return Integer.MIN_VALUE;

        return stack.arr[stack.top--];
    }

    // Function to move disks between the poles
    void moveDisks(Stack src, Stack dest, char s, char d) {

        int pole1 = pop(src);
        int pole2 = pop(dest);

        // When pole 1 is empty
        if (pole1 == Integer.MIN_VALUE) {

            push(src, pole2);
            move(d, s, pole2);
        }

        // When pole2 pole is empty
        else if (pole2 == Integer.MIN_VALUE) {

            push(dest, pole1);
            move(s, d, pole1);
        }

        // When top disk of pole1 > top disk of pole2
        else if (pole1 > pole2) {

            push(src, pole1);
            push(src, pole2);
            move(d, s, pole2);
        }
        // When top disk of pole1 < top disk of pole2
        else {

            push(dest, pole2);
            push(dest, pole1);
            move(s, d, pole1);
        }
    }

    //Function to show the movement of disks
    void move(char fromPeg, char toPeg, int disk) {

        System.out.println("Move the disk " + disk + " from " + fromPeg + " to " + toPeg);
    }

    // Implementation
    void Iterative(int num, Stack src, Stack aux, Stack dest) {

        int i, total_num_of_moves;
        char s = 'S', d = 'D', a = 'A';

        // Rules in algorithm will be followed
        if (num % 2 == 0) {

            char temp = d;
            d = a;
            a = temp;
        }
        total_num_of_moves = (int)(Math.pow(2, num) - 1);

        // disks with large diameter are pushed first
        for (i = num; i >= 1; i--)
            push(src, i);

        for (i = 1; i <= total_num_of_moves; i++) {

            if (i % 3 == 1)
                moveDisks(src, dest, s, d);

            else if (i % 3 == 2)
                moveDisks(src, aux, s, a);

            else if (i % 3 == 0)
                moveDisks(aux, dest, a, d);
        }
    }

    // Main Function
    public static void main(String[] args) {

        // number of disks
        int num = 3;

        Solution ob = new Solution();
        Stack src, dest, aux;

        src = ob.create(num);
        dest = ob.create(num);
        aux = ob.create(num);

        ob.Iterative(num, src, aux, dest);
    }
}

 

Output:

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

Must Read Stack Operations

Implementation in C++

#include <bits/stdc++.h>

using namespace std;
// Tower of Hanoi

class Stack {
    public:
        int capacity;
    int top;
    int arr[1000001];

    Stack(int capacity) {
        this -> capacity = capacity;
        this -> top = -1;
    }

    //Stack is full when the top is equal
    // to the last index
    bool isFull(Stack * stack) {
        return (stack -> top == stack -> capacity - 1);
    }

    // To check Stack is empty or not
    bool isEmpty(Stack * stack) {
        return (stack -> top == -1);
    }

    //Function to add an item in Stack
    void push(Stack * stack, int item) {
        if (isFull(stack))
            return;
        stack -> arr[++stack -> top] = item;
    }

    //Function to remove an item from Stack
    int pop(Stack * stack) {
        if (isEmpty(stack))
            return INT_MIN;
        return stack -> arr[stack -> top--];
    }

    void moveDisks(Stack * src, Stack * dest, char s, char d) {

        int pole1 = pop(src);
        int pole2 = pop(dest);

        // When pole 1 is empty
        if (pole1 == INT_MIN) {
            push(src, pole2);
            move(d, s, pole2);
        }
        // When pole2 pole is empty
        else if (pole2 == INT_MIN) {
            push(dest, pole1);
            move(s, d, pole1);
        }
        // When top disk of pole1 > top disk of pole2
        else if (pole1 > pole2) {
            push(src, pole1);
            push(src, pole2);
            move(d, s, pole2);
        }
        // When top disk of pole1 < top disk of pole2
        else {

            push(dest, pole2);
            push(dest, pole1);
            move(s, d, pole1);
        }
    }

    //Function to show the movement of disks
    void move(char fromPeg, char toPeg, int disk) {
        cout << "Move the disk " << disk << " from " << fromPeg << " to " << toPeg << '\n';
    }

    // Implementation
    void Iterative(int num, Stack * src, Stack * aux, Stack * dest) {

        int i, total_num_of_moves;
        char s = 'S', d = 'D', a = 'A';

        // Rules in algorithm will be followed
        if (num % 2 == 0) {
            char temp = d;
            d = a;
            a = temp;
        }
        total_num_of_moves = (int)(pow(2, num) - 1);

        // disks with large diameter are pushed first
        for (i = num; i >= 1; i--)
            push(src, i);

        for (i = 1; i <= total_num_of_moves; i++) {
            if (i % 3 == 1)
                moveDisks(src, dest, s, d);
            else if (i % 3 == 2)
                moveDisks(src, aux, s, a);
            else if (i % 3 == 0)
                moveDisks(aux, dest, a, d);
        }
    }
};

int main() {
    // your code goes here
    // number of disks
    int num = 3;
    Stack * src, * dest, * aux;

    //stacks created for src , dest, aux
    src = new Stack(num);
    dest = new Stack(num);
    aux = new Stack(num);

    // solution 
    Stack * sol = new Stack(0);
    sol -> Iterative(num, src, aux, dest);
    return 0;
}

 

Output

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

Implementation in Python

#Tower of Hanoi
INT_MIN = -2147483648

class Stack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.top = -1
        self.arr = []

    # Stack is full when the top is equal
    # to the last index
    def isFull(self, stack):
        return stack.top == stack.capacity - 1

    # To check Stack is empty or not
    def isEmpty(self, stack):
        return stack.top == -1

    # Function to add an item in Stack
    def push(self, stack, item):
        if self.isFull(stack):
            return
        stack.top+=1
        stack.arr.append(item)

    # Function to remove an item from Stack
    def pop(self, stack):
        if self.isEmpty(stack):
            return INT_MIN
        stack.top-=1        
        return stack.arr.pop()
    
    def moveDisks(self, src, dest, s, d):

        pole1 = self.pop(src);
        pole2 = self.pop(dest);

        # When pole 1 is empty
        if(pole1 == INT_MIN):
            self.push(src, pole2)
            self.move(d, s, pole2)
            
        # When pole2 pole is empty
        elif (pole2 == INT_MIN):
            self.push(dest, pole1)
            self.move(s, d, pole1)
            
        # When top disk of pole1 > top disk of pole2
        elif (pole1 > pole2):
            self.push(src, pole1)
            self.push(src, pole2)
            self.move(d, s, pole2)
        # When top disk of pole1 < top disk of pole2
        else:
            self.push(dest, pole2)
            self.push(dest, pole1)
            self.move(s, d, pole1)

    # Function to show the movement of disks
    def move(self, fromPeg, toPeg, disk):
        print("Move the disk "+str(disk)+" from "+fromPeg+" to " + toPeg)

    # Implementation
    def Iterative(self, num, src, aux, dest):

        s, d, a = 'S', 'D', 'A'

        # Rules in algorithm will be followed
        if num % 2 == 0:
            temp = d
            d = a
            a = temp

        total_num_of_moves = int(pow(2, num) - 1)

        # disks with large diameter are pushed first
        i = num
        while(i>=1):
            self.push(src, i)
            i-=1
        
        i = 1
        while(i <= total_num_of_moves):
            if (i % 3 == 1):
                self.moveDisks(src, dest, s, d)
            
            elif (i % 3 == 2):
                self.moveDisks(src, aux, s, a)
            
            elif (i % 3 == 0):
                self.moveDisks(aux, dest, a, d)
            
            i+=1
      
# 	number of disks
num = 3
# stacks created for src , dest, aux
src  = Stack(num)
dest = Stack(num) 
aux = Stack(num) 
# solution 
sol = Stack(0)
sol.Iterative(num, src, aux, dest)

 

Output

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

Complexity Analysis

Time Complexity: The time complexity of this algorithm is O(2n), n=number of disks.

Space Complexity: The space complexity will be O(n) as we are using Stack.

 

After understanding the above approach, you should check out this video to know the logic behind this problem.

Frequently Asked Questions

How many approaches are there to solve the Tower of Hanoi problem?

There are two approaches to solve this problem:

  • Iterative solution.
  • Recursive solution.

What do you mean by Stack Data Structure?

It is a linear data structure that stores and removes elements based on LIFO(Last In First Order) principle. There are some common operations that are implemented on stack like Push(), Peek(), Pop(), IsEmpty() etc.

What is the difference between iterative and recursive algorithms?

Iterative:

  • It uses loop statements such as for loop or while loop to repeat the steps.
  • It is faster than the recursive algorithm because of overheads.
  • More efficient in terms of time and space.

Recursive:

  • The Function calls itself again and again till the given base condition is satisfied.
  • Less efficient in terms of time and space.

Conclusion

In this blog, we discussed the Tower of Hanoi problem and how we can build an approach for it:

There are two approaches for this approach; we have discussed the iterative solution in which we have used the Stack to store and remove the disks and arrange them in ascending order. We have written code in Java, C++, and Python language.

Recommended Readings:

Check out some of the Top Recursion and Backtracking Interview Problems to get a proper handle on the concepts.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Keep Coding!!!

Previous article
Two stacks in an array
Next article
Design a Minimum Stack
Live masterclass