Iterative Tower of Hanoi

Last Updated on November 24, 2023 by Ankit Kochar

The Tower of Hanoi puzzle has fascinated mathematicians and puzzle enthusiasts alike for centuries with its elegant simplicity and complex nature. Originally formulated by the French mathematician Édouard Lucas in 1883, this classic problem involves moving a stack of disks from one peg to another, adhering to specific rules. While the traditional Tower of Hanoi puzzle employs a recursive algorithm, the concept of an iterative solution has emerged as an intriguing alternative.

What is the Tower of Hanoi?

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.

Conclusion
The Tower of Hanoi puzzle continues to captivate minds with its blend of simplicity and complexity. The iterative approach offers an alternative methodology to solve this problem, emphasizing efficiency, scalability, and clearer control flow. By diverging from the recursive path, the iterative solution showcases a different perspective on algorithmic problem-solving, shedding light on the diverse strategies available to tackle intricate challenges.

FAQ (Frequently Asked Questions) About Iterative Tower of Hanoi:

Here are some FAQs related to the iterative Tower of Hanoi.

1. How does the iterative Tower of Hanoi differ from the recursive method?
The iterative approach employs loops and explicit stack-based methods to solve the Tower of Hanoi puzzle, whereas the recursive method relies on function calls and dividing the problem into smaller subproblems.

2. Is the iterative solution faster than the recursive one?
In some cases, the iterative solution may offer faster execution due to the elimination of function call overhead. However, the actual performance can vary based on the implementation and problem size.

3. Can the iterative approach handle larger Tower of Hanoi configurations?
The iterative method’s optimized iterations and stepwise movement strategies can potentially handle larger configurations more efficiently than recursive approaches, but it also depends on the specific implementation and constraints.

4. What are the advantages of understanding the iterative Tower of Hanoi solution?
Exploring the iterative solution enhances one’s understanding of algorithm design, control flow structures, and alternative problem-solving strategies, providing valuable insights beyond traditional recursive paradigms.