Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

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.

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.

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)

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.