Iterative Tower of Hanoi

Problem statement

In the Tower of Hanoi problem you are given three rods (“Source”, “Destination”, “Auxiliary”) and n disks. Initially, all the disks are stacked on the source rod in decreasing order of disk’s size making a conical shape. Your task is to move all the stacked disks to the destination rod by obeying the following rules:

  1. You can move only one disk in one step.
  2. The topmost disk can be removed from any rod and placed on the top of the other rod.
  3. A disk can not be placed on another disk that is smaller in size than it.

Test cases:
Input:
2

Output:
Move Disk 1 from “S” to “A”
Move Disk 2 from “S” to “D”
Move Disk 1 from “A” to “D”

Explanation:

Iterative Approach

Algorithm

  1. Find the total number of moves required to solve the problem.
  2. If the number of disks is n, then the total moves required is 2n – 1.
  3. If n % 2 == 0, i.e, n is even then exchange the position of destination rod and auxiliary rod.
  4. Iterate i in 1 to moves
    a. if i % 3 == 1:
    a.1. Move the topmost disk of the source pole and place it on the top of the destination pole.
    b. If i%3 == 2:
    b.1. Move the topmost disk of the source pole and place it on the top of the auxiliary pole.
    c. If i%3 == 0:
    c.1. Move the topmost disk of the auxiliary pole and place it on the top of the destination pole.

Code Implementation:


import java.util.*;
import java.lang.*;
import java.io.*;
public class TowerOfHanoi{
	
// Stack Class
class Stack
{
	int capacity;
	int top;
	int array[];
}

// This function will create a new stack of the given capacity
Stack initStack(int capacity)
{
	Stack st = new Stack();
	st.capacity = capacity;
	st.top = -1;
	st.array = new int[capacity];
	return st;
}

// This function checks whether the stack is full or not
boolean isFull(Stack st)
{
	return (st.top == st.capacity - 1);
}

// This function checks whether the stack is empty or not
boolean isEmpty(Stack st)
{
	return (st.top == -1);
}

// This function adds this item to the stack.
void push(Stack st, int item)
{
	if (isFull(st)) {
		return;
	}
		
	st.array[++st.top] = item;
}

// This function removes the top of the stack.
int pop(Stack st)
{
	if (isEmpty(st))
		return Integer.MIN_VALUE;
		
	return st.array[st.top--];
}

// This function carries out the movement of the disk between two poles.
void move(Stack src, Stack dest,
							char s, char d)
{
	int disk1 = pop(src);
	int disk2 = pop(dest);

	// Is rod 1 is empty
	if (disk1 == Integer.MIN_VALUE)
	{
		push(src, disk2);
		printMove(d, s, disk2);
	}
	
	// if rod 2  is empty
	else if (disk2 == Integer.MIN_VALUE)
	{
		push(dest, disk1);
		printMove(s, d, disk1);
	}
	
	// If Disk 1 > Disk 2
	else if (disk1 > disk2)
	{
		push(src, disk1);
		push(src, disk2);
		printMove(d, s, disk2);
	}
	// If Disk 1 < Disk 2
	else
	{
		push(dest, disk2);
		push(dest, disk1);
		printMove(s, d, disk1);
	}
}

// This function will print the movement of disks
void printMove(char from, char to, int disk)
{
	System.out.println("Move the disk " + disk +
							" from " + from +
							" to " + to);
}

// Function to implement the algorithm
void iterativeTowerOfHanoi(int n, Stack
				src, Stack aux, Stack dest)
{
	int i, moves;
	char s = 'S', d = 'D', a = 'A';

    // If n is even then exchange the position of destination rod and auxiliary rod.
	if (n % 2 == 0)
	{
		char temp = d;
		d = a;
		a = temp;
	}
	moves = (int)(Math.pow(
						2, n) - 1);

	for(i = n; i >= 1; i--)
		push(src, i);

	for(i = 1; i <= moves; i++)
	{
		if (i % 3 == 1)
		move(src, dest, s, d);

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

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

    // Main function
    public static void main(String[] args)
    {
	
	int n = 3;
	
	TowerOfHanoi ob = new TowerOfHanoi();

	// Create three stacks (Source, destination, Auxiliary)
	Stack source = ob.initStack(n);
	Stack destination = ob.initStack(n);
      Stack auxiliary = ob.initStack(n);
	
	ob.iterativeTowerOfHanoi(n, source, auxiliary, destination);
    }
}

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

Dry Run:

Time complexity: O(2^n). The minimum number of moves required is 2n.

Space Complexity: O(n). We have to store at most n disks.

This article tried to discuss the iterative way to solve the Tower of Hanoi problem. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *