Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Tower of Hanoi?
3.
Tower of Hanoi Pictorial Representation 
4.
Algorithm 
5.
Recursive Approach
5.1.
Java
5.2.
C++
5.3.
Python
5.4.
Explanation:
5.5.
Complexities: 
6.
Iterative Approach
6.1.
Java
6.2.
C++
6.3.
Python
6.4.
Explanation:
6.5.
Complexities: 
7.
Dynamic Programming Approach
7.1.
Java
7.2.
C++
7.3.
Python
7.4.
Explanation:
7.5.
Complexities: 
8.
Frequently Asked Questions
8.1.
What is the concept of Tower of Hanoi?
8.2.
What is the Tower of Hanoi IQ test?
8.3.
What is the formula for the Tower of Hanoi 4 pegs?
8.4.
Why is the game called Tower of Hanoi?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Tower of Hanoi

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

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. 

Tower of hanoi

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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. 

Tower of Hanoi Pictorial Representation

Here we have 3 Disk.

Source Image

First, move disk 1 from source to destination.

Auxiliary Image

Move disk 2 from source to auxiliary.

Destination Image

Move disk 1 from destination to auxiliary.

source to destination

Move disk 3 from source to destination.

auxiliary to source

Move disk 1 from auxiliary to source.

auxiliary to destination

Move disk 2 from auxiliary to destination.

largest disk

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:

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(2N)

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;

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

C++

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

Python

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:

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(2N)

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:

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(2N)

Space Complexity: O(N)

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.

Conclusion

In this article, we learn about  tower of hanoi. We also learn about Recursive Approach, Iterative Approach, Dynamic Programming Approach and their time and space complexity. We concluded the article by coding the tower of hanoi problem.

To better understand the topic, refer to 

 

For more information, refer to our Guided Path on CodeStudio to upskill yourself in PythonData Structures and AlgorithmsCompetitive ProgrammingSystem 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!

Previous article
Tic Tac Toe Game A Complete Tutorial
Next article
6 Basic SDLC Models: Which One is the Best?
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass