The Towers of Hanoi is a puzzle consisting of a number of disks placed on three columns. The disks have different diameters and holes in the middle so that they will fit over the columns. All the disks start in column A. The object of the puzzle is to transfer all the disks from column A to column C. Only one disk can be moved at a time, and no disk can be placed on a disk that's smaller than itself.

There's an ancient myth that somewhere in India, in a remote temple, monks labor day and night to transfer 64 golden disks from one of three diamond-studded towers to another. When they are finished, the world will end. However, any alarm you may feel will be dispelled when you see how long it takes to solve the puzzle for far fewer than 64 disks. In this article, we will learn about Tower of Hanoi solution.

What is Tower of Hanoi?

The Tower of Hanoi is a conventional puzzle that includes 3 rods and fixed disks of different sizes. The puzzle begins with the disks stacked in decreasing order of size on one rod, with the biggest disk at the bottom. The goal is to move the entire stack to another rod, following these rules:

Only one disk can be moved at a time.

A disk can handiest be placed on top of a bigger disk or an empty rod.

The intention is to transport all the disks from the source rod to the target rod, using the auxiliary rod as needed.

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

Java

C++

Python

Java

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; } }

C++

#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; }

Python

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

Java

C++

Python

Java

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;

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

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

Java

C++

Python

Java

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); } }

C++

#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; }

Python

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 :

Java

C++

Python

Java

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

C++

#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; }

Python

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 :

Base Case: If there's only one disk, move it directly from the source peg to the destination peg.

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.