Iterative Tower of Hanoi

Iterative Approach

We will follow three simple steps to solve the problem.

1. Calculate the total number of moves required 2ⁿ-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 2³-1=8-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 ‘3’ is the largest and ‘1’ is the smallest.

 

 

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:

• Trapping Rainwater
• Delete Middle Element Of The Stack
• Diagonal Traverse ii
• Largest rectangle in histogram
• Distance from Next Greater element
• Online Stock Span
• Daily Temperatures
• Create Maximum Number
• Introduction to Recursion
   

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!!!