Tower of Hanoi Problem
The Tower of Hanoi is one of the best problems on Recursion. It is a Mathematical Puzzle solved by Recursion in the best way. This problem aims to Move n Number of discs from a source rod to a destination rod.
It consists of three rods and N number of Discs stacked in the First rod according to decreasing size,
Rules in Tower of Hanoi Problem
- Only one disc can be moved at a time.
- A bigger disc can't be placed on a smaller one.
- The disc should be stacked at the destination in the same manner as it was at the source position.
- Problem to be solved in the minimum number of steps.
Let us understand the Tower of Hanoi Problem with a Diagram.
The Minimum Number of Moves Required to solve the Tower of Hanoi Problem is 2n-1. where n is the total number of Discs.
Play Tower of Hanoi
I think Now You have understood this problem. Now Lets us proceed to solve the Tower of Hanoi problem in our Code.
Tower of Hanoi Problem can be solved in Two Ways:
- Using Recursion
- Using Stack
Tower of Hanoi Using Recursion
In this approach, we have to just think about how to transfer all discs in the helper rod and the rest of the work will recursion do.
Tower of Hanoi Solution in C++
//Tower of Hanoi
#include<bits/stdc++.h>
using namespace std;
void Hanoi(int n,char src,char dest,char help)
{
if(n==0) return;
Hanoi(n-1,src,help,dest);
cout<<"Ring from "<<src<<" to "<<dest<<"\n";
Hanoi(n-1,help,dest,src);
return;
}
int main()
{
Hanoi(3,'A','C','B');
return 0;
}
Tower of Hanoi Solution in C
//Tower of Hanoi
#include<stdio.h>
void Hanoi(int n,char src,char dest,char help)
{
if(n==0) return;
Hanoi(n-1,src,help,dest);
printf("Disc from %c to %d \n",src,dest);
Hanoi(n-1,help,dest,src);
return;
}
int main()
{
Hanoi(3,'A','C','B');
return 0;
}
Tower of Hanoi Solution in Java
import java.util.*;
public class TowerofHanoi {
public static void main(String[] args) {
Hanoi(3,'A','C','B');
}
static void Hanoi(int n, char src, char dest, char help)
{
if(n==0) return;
Hanoi(n-1,src,help,dest);
System.out.println("Disc From "+ src +" to "+ dest);
Hanoi(n-1,help,dest,src);
return;
}
}
Tower of Hanoi Solution in Python
def Hanoi(int n,char src,char dest,char help) :
if(n==0):
return;
Hanoi(n-1,src,help,dest);
System.out.println("Disc From "+ src +" to "+ dest);
Hanoi(n-1,help,dest,src);
return;
Hanoi(3,'A','C','B');
Time Complexity of Tower of Hanoi Problem
Time Complexity of Tower of Hanoi Problem is O(2^n). and this is the best way to solve Tower of Hanoi Problem. You can try it with the divide and conquer algorithm but then complexity may increase.
-: Some of The Best Problems of Recursion:-
- Tower of Hanoi
- Print Permutation of String
- Print all subsets of a string
- Reverse a String using Recursion
- Factorial of a Large Number
- Print Palindrome of a number
- Shortest path in MATRIX.
- Print all possible words from phone digit
- Total path in a maze
- Implementation of Binary Tree
