Iterative Tower of Hanoi

Soumya Agrawal
Last Updated: May 20, 2022
Difficulty Level :
EASY

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 which 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.

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

Problem Statement

We will be given three rods and ‘n’ 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 in any poles.

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

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 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 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=7.

 

 

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

 

 

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

 

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

 

 

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

 

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

 

 

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

 

 

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

 

 

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

 

 

Please try to solve Tower of Hanoi on CodeStudio 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

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 language.

You can use CodeStudio to practice various DSA questions typically asked in interviews. It will help you in mastering efficient coding techniques.

Keep Coding!!!

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think