Tower of Hanoi

Tower of Hanoi Pictorial Representation 

Tower of Hanoi is a mathematical puzzle where we have 3 rods and N disks. The objective of the puzzle is to move all disks from the source rod to the destination rod using an auxiliary rod. 

Here we have 3 Disk.

First, move disk 1 from source to destination.

Move disk 2 from source to auxiliary.

Move disk 1 from destination to auxiliary.

Move disk 3 from source to destination.

Move disk 1 from auxiliary to source.

Move disk 2 from auxiliary to destination.

Move disk 1 from source to destination. All disks are correctly transferred from the source to the destination rod, with the largest disk at the bottom and the smallest at the top.

Algorithm 

Step 1: START

Step 2: In starting, we have three rods: source, auxiliary, and destination.

Step 3: All the disks placed on the source rod in ascending order, with the largest disk at the bottom and the smallest at the top.

Step 4: To move N disks from the source to the destination using the auxiliary rod:

• Move N-1 disks from the source to the auxiliary rod using the destination rod as a helper.
   
• Move the largest disk from the source to the destination.
   
• Move the N-1 disks from the auxiliary rod to the destination using the source rod as a helper.

Step 5: Repeat these steps until all disks are on the destination rod.

Step 6: The puzzle is solved when all disks are transferred to the destination rod correctly.

Step 7: END.

Recursive Approach

public class Main {
	public static void main(String[] args) {
    	Solution solution = new Solution();
    	int N = 3; // Change N to the number of disks you want to use
    	long total_moves = solution.toh(N, 1, 3, 2);
    	System.out.println("Total moves: " + total_moves);
	}
}
class Solution{

	public long toh(int disks, int source, int destination, int auxiliary) {
    	if (disks == 1) {
        	System.out.println("move disk 1 from rod " + source + " to rod " + destination);
        	return 1;
    	}

    	long count1 = toh(disks - 1, source, auxiliary, destination);
    	System.out.println("move disk " + disks + " from rod " + source + " to rod " + destination);
    	long count2 = toh(disks - 1, auxiliary, destination, source);

    	return count1 + count2 + 1;
	}
}

#include <iostream>

class Solution {
public:
	long toh(int disks, int source, int destination, int auxiliary) {
    	if (disks == 1) {
        	std::cout << "move disk 1 from rod " << source << " to rod " << destination << std::endl;
        	return 1;
    	}

    	long count1 = toh(disks - 1, source, auxiliary, destination);
    	std::cout << "move disk " << disks << " from rod " << source << " to rod " << destination << std::endl;
    	long count2 = toh(disks - 1, auxiliary, destination, source);

    	return count1 + count2 + 1;
	}
};

int main() {
	Solution solution;
	int N = 3; // Change N to the number of disks you want to use
	long total_moves = solution.toh(N, 1, 3, 2);
	std::cout << "Total moves: " << total_moves << std::endl;
	return 0;
}

class Solution:
	def toh(self, disks, source, destination, auxiliary):
    	if disks == 1:
        	print(f"Move disk 1 from rod {source} to rod {destination}")
        	return 1

    	count1 = self.toh(disks - 1, source, auxiliary, destination)
    	print(f"Move disk {disks} from rod {source} to rod {destination}")
    	count2 = self.toh(disks - 1, auxiliary, destination, source)

    	return count1 + count2 + 1

if __name__ == "__main__":
	solution = Solution()
	N = 3  # Change N to the number of disks you want to use
	total_moves = solution.toh(N, 'A', 'C', 'B')
	print(f"Total moves: {total_moves}")

Output:

Explanation:

The recursive technique is the most common approach to clear up the Tower of Hanoi problem. It's primarily based on the observation that to move n disks from the source rod to the destination rod, you may break it down into three steps:

• Move the top n-1 disks from the source rod to the auxiliary rod, using the destination rod as a temporary memory.
• Move the largest n-th disk from the source rod to the destination rod.
• Move the n-1 disks from the auxiliary rod to the destination rod, using the source rod as a temporary location.

The system maintains recursively till all disks are moved to the destination rod. 

Complexities: 

Time Complexity: O(2^N)

Space Complexity: O(N)

Iterative Approach

import java.util.Stack;

class Hanoi {

	public void tohIterative(int disks, int source, int destination, int auxiliary) {
    	Stack<HanoiState> stack = new Stack<>();
    	stack.push(new HanoiState(disks, source, destination, auxiliary));

    	while (!stack.isEmpty()) {
        	HanoiState currentState = stack.pop();

        	if (currentState.disks == 1) {
            	System.out.println("Move disk 1 from rod " + currentState.source + " to rod " + currentState.destination);
        	} else {
            	stack.push(new HanoiState(currentState.disks - 1, currentState.auxiliary, currentState.destination, currentState.source));
            	stack.push(new HanoiState(1, currentState.source, currentState.destination, currentState.auxiliary));
            	stack.push(new HanoiState(currentState.disks - 1, currentState.source, currentState.auxiliary, currentState.destination));
        	}
    	}
	}

	public static void main(String[] args) {
    	Hanoi hanoi = new Hanoi();
    	int disks = 3;
    	int source = 1;
    	int destination = 3;
    	int auxiliary = 2;

    	hanoi.tohIterative(disks, source, destination, auxiliary);
	}
}

class HanoiState {
	int disks;
	int source;
	int destination;
	int auxiliary;

	HanoiState(int d, int src, int dest, int aux) {
    	this.disks = d;
    	this.source = src;
    	this.destination = dest;
    	this.auxiliary = aux;
	}
}

#include <iostream>
#include <stack>

struct HanoiState {
	int disks;
	int source;
	int destination;
	int auxiliary;

	HanoiState(int d, int src, int dest, int aux)
    	: disks(d), source(src), destination(dest), auxiliary(aux) {}
};

void tohIterative(int disks, int source, int destination, int auxiliary) {
	std::stack<HanoiState> stack;
	stack.push(HanoiState(disks, source, destination, auxiliary));

	while (!stack.empty()) {
    	HanoiState currentState = stack.top();
    	stack.pop();

    	if (currentState.disks == 1) {
        	std::cout << "Move disk 1 from rod " << currentState.source << " to rod " << currentState.destination << std::endl;
    	} else {
        	stack.push(HanoiState(currentState.disks - 1, currentState.auxiliary, currentState.destination, currentState.source));
        	stack.push(HanoiState(1, currentState.source, currentState.destination, currentState.auxiliary));
        	stack.push(HanoiState(currentState.disks - 1, currentState.source, currentState.auxiliary, currentState.destination));
    	}
	}
}

int main() {
	int disks = 3;
	int source = 1;
	int destination = 3;
	int auxiliary = 2;

	tohIterative(disks, source, destination, auxiliary);

	return 0;
}

class Hanoi:

	def tohIterative(self, disks, source, destination, auxiliary):
    	stack = []
    	stack.append((disks, source, destination, auxiliary))

    	while stack:
        	disks, source, destination, auxiliary = stack.pop()

        	if disks == 1:
            	print(f"Move disk 1 from rod {source} to rod {destination}")
        	else:
            	stack.append((disks - 1, auxiliary, destination, source))
            	stack.append((1, source, destination, auxiliary))
            	stack.append((disks - 1, source, auxiliary, destination))

# Usage
hanoi = Hanoi()
disks = 3
source = 1
destination = 3
auxiliary = 2

hanoi.tohIterative(disks, source, destination, auxiliary)

Output:

Explanation:

The iterative approach solves the Tower of Hanoi trouble using a loop and a stack. It simulates the recursive technique using an explicit stack. The idea is to maintain track of each disk (source, destination, auxiliary) and push and pop from the stack till the problem is solved. This technique can be more efficient for big numbers of disks.

Here's an excessive-degree definition of the iterative technique:

• Initialize an empty stack to keep states.
• Push the prior state (n, source, destination, auxiliary) onto the stack.
• While the stack is not empty:
• Pop the top state from the stack.
• If n is 1, flow the disk directly from the source to the destination rod.
• Otherwise, push the states for n-1 disks onto the stack within the proper order.

The iterative approach avoids the overhead of recursive function calls and is frequently desired for overall performance motives.

Complexities: 

Time Complexity: O(2^N)

Space Complexity: O(N)

Dynamic Programming Approach

class Hanoi {
	public long toh(int N) {
    	long[] dp = new long[N + 1];
   	 
    	for (int i = 1; i <= N; ++i) {
        	dp[i] = 2 * dp[i - 1] + 1;
    	}
   	 
    	return dp[N];
	}
}

public class Main {
	public static void main(String[] args) {
    	Hanoi hanoi = new Hanoi();
    	int N = 3; // Number of disks
    	long total_moves = hanoi.toh(N);
    	System.out.println("Total moves: " + total_moves);
	}
}

#include <iostream>
#include <vector>

class Hanoi {
public:
	long toh(int N) {
    	std::vector<long> dp(N + 1, 0);
   	 
    	for (int i = 1; i <= N; ++i) {
        	dp[i] = 2 * dp[i - 1] + 1;
    	}
   	 
    	return dp[N];
	}
};

int main() {
	Hanoi hanoi;
	int N = 3; // Number of disks
	long total_moves = hanoi.toh(N);
	std::cout << "Total moves: " << total_moves << std::endl;
	return 0;
}

class Hanoi:
	def toh(self, N):
    	dp = [0] * (N + 1)
   	 
    	for i in range(1, N + 1):
        	dp[i] = 2 * dp[i - 1] + 1
   	 
    	return dp[N]

# Usage:
N = 3  # Number of disks
hanoi = Hanoi()
total_moves = hanoi.toh(N)
print("Total moves:", total_moves)

Output:

Explanation:

The dynamic programming technique is a more advanced approach to solving the Tower of Hanoi. Its objective is to encounter optimal moves to solve this problem with the fewest possible moves. Dynamic programming entails breaking the problem into smaller subproblems and storing their solutions in an array to avoid redundant calculations.

The Tower of Hanoi can be solved using dynamic programming by calculating the minimum number of moves required to move n disks from the source to the destination. The minimum variety of move for n disks may be expressed as a recursive formula:

Minimum Moves(n) = 2 * Minimum Moves(n - 1) + 1

Here, Minimum Moves(n) represents the minimal number of moves required to move n disks. This formulation may calculate the minimum moves for large numbers of disks without simulating the actual actions.

Complexities: 

Time Complexity: O(2^N)

Space Complexity: O(N)

Using Recursion : 

public class TowerOfHanoi {
    public static void moveDisks(int n, char fromPeg, char toPeg, char auxPeg) {
        if (n == 1) {
            System.out.println("Move disk 1 from peg " + fromPeg + " to peg " + toPeg);
            return;
        }
        moveDisks(n - 1, fromPeg, auxPeg, toPeg);
        System.out.println("Move disk " + n + " from peg " + fromPeg + " to peg " + toPeg);
        moveDisks(n - 1, auxPeg, toPeg, fromPeg);
    }

    public static void main(String[] args) {
        int n = 3; // Number of disks
        moveDisks(n, 'A', 'C', 'B'); // A, B and C are names of pegs
    }
}

#include <iostream>
using namespace std;

void moveDisks(int n, char fromPeg, char toPeg, char auxPeg) {
    if (n == 1) {
        cout << "Move disk 1 from peg " << fromPeg << " to peg " << toPeg << endl;
        return;
    }
    moveDisks(n - 1, fromPeg, auxPeg, toPeg);
    cout << "Move disk " << n << " from peg " << fromPeg << " to peg " << toPeg << endl;
    moveDisks(n - 1, auxPeg, toPeg, fromPeg);
}

int main() {
    int n = 3; // Number of disks
    moveDisks(n, 'A', 'C', 'B'); // A, B and C are names of pegs
    return 0;
}

def moveDisks(n, fromPeg, toPeg, auxPeg):
    if n == 1:
        print(f"Move disk 1 from peg {fromPeg} to peg {toPeg}")
        return
    moveDisks(n - 1, fromPeg, auxPeg, toPeg)
    print(f"Move disk {n} from peg {fromPeg} to peg {toPeg}")
    moveDisks(n - 1, auxPeg, toPeg, fromPeg)

n = 3  # Number of disks
moveDisks(n, 'A', 'C', 'B')  # A, B, and C are names of pegs

It will give you the output(for n=3)

Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg C

Let's discuss this code now : 

1. Base Case: If there's only one disk, move it directly from the source peg to the destination peg.
2. Recursive Case: Move n-1 disks to the auxiliary peg, move the nth disk to the destination peg, then move the n-1disks from the auxiliary peg to the destination peg.

This method breaks the problem down into smaller sub-problems of the same type, that solve the smallest problem directly and combine the solutions.

Complexities : 

• Time Complexity: O(2n)O(2n). Each move requires two calls to move n−1n−1 disks and one additional move, leading to exponential growth in the number of moves.
• Space Complexity: O(n)O(n). This arises from the depth of the recursion tree, as each call adds a frame to the stack.

Frequently Asked Questions

What is the concept of Tower of Hanoi?

The Tower of Hanoi is a classic mathematical puzzle involving three rods and a stack of different-sized disks, where the objective is to transfer the entire stack from one rod to another, following specific rules, using an auxiliary rod. The puzzle illustrates recursion and algorithmic problem-solving.

What is the Tower of Hanoi IQ test?

The Tower of Hanoi is not an IQ test but a mathematical puzzle. It challenges problem-solving skills, spatial reasoning, and patience.

What is the formula for the Tower of Hanoi 4 pegs?

The formula for the Tower of Hanoi with 4 pegs is not as straightforward as the classic 3-peg version and involves complex algorithms for optimal solutions.

Why is the game called Tower of Hanoi?

The game is named "Tower of Hanoi" because it was inspired by a legend of an Indian temple in Hanoi, where priests moved disks between three diamond needles.

What are the rules of the Tower of Hanoi?

The Tower of Hanoi works on three primary rules: First, only one disk may be moved at a time. Second, each move involves taking the uppermost disk from one of the stacks and placing it on top of another stack. Lastly, a larger disk cannot be placed on top of a smaller disk. These rules ensure that the game requires strategic planning and thought.

Conclusion

In this article, we discussed the Tower of Hanoi puzzle and looked into different methods to solve it. We discuss the Recursive Approach, which breaks the problem down into smaller, manageable parts. We also cover the Iterative and Dynamic Programming Approaches and explain how each method works and their respective time and space complexities. At the end, we discussed the final method of solving this puzzle which is the Recursive method Tower. We explained all these approaches with the help of proper code examples to make it easy for you to understand.

To better understand the topic, refer to 

• Data Structures and Algorithms 
• Data Structure Interview Questions and Answers (2023) 
• How to Practice Data Structures & Algorithms?

For more information, refer to our Guided Path on CodeStudio to upskill yourself in Python, Data Structures and Algorithms, Competitive Programming, System Design, and many more! 

Head over to our practice platform, CodeStudio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!
Happy Learning!