Last Updated on October 10, 2022 by Gokul Kannan
Problem statement
In the Tower of Hanoi problem you are given three rods (“Source”, “Destination”, “Auxiliary”) and n disks. Initially, all the disks are stacked on the source rod in decreasing order of the disk’s size making a conical shape. Your task is to move all the stacked disks to the destination rod by obeying the following rules:
- You can move only one disk in one step.
- The topmost disk can be removed from any rod and placed on top of the other rod.
- A disk can not be placed on another disk that is smaller in size than it.
Test cases:
Input:
2
Output:
Move Disk 1 from “S” to “A”
Move Disk 2 from “S” to “D”
Move Disk 1 from “A” to “D”
Explanation:
Recursive Approach:
Algorithm:
We will use the auxiliary rod to reach the destination using recursion. The recurrence formula follows:
- Move ‘n-1’ disks from the source rod to the Auxillary rod using the destination rod.
- Move the nth disk from the source rod to the destination rod.
- Move ‘n-1’ disks from the auxiliary rod to the destination rod using the source rod.
Dry Run:
Implementation:
public class Prepbytes
{
public static void main(String[] args) {
towerofhanoi(3, "S", "D", "A");
}
public static void towerofhanoi(int disks, String src, String dst, String temp){
if (disks == 1){
System.out.println("Move disk " + disks + " from "+ src + " to " + dst);
}
else {
towerofhanoi(disks - 1, src, temp, dst);
System.out.println("Move disk " + disks + " from "+ src + " to " + dst);
towerofhanoi(disks - 1, temp, dst, src);
}
}
}
Output:
Move disk 1 from S to D
Move disk 2 from S to A
Move disk 1 from D to A
Move disk 3 from S to D
Move disk 1 from A to S
Move disk 2 from A to D
Move disk 1 from S to D
Time complexity: O(2n). The minimum number of moves required is 2n.
Space Complexity: O(n). We have to store at most n disks in the recursive stack..
Iterative Approach
Algorithm
- Find the total number of moves required to solve the problem. If the number of disks is n, then the total moves required is 2n – 1.
- If n % 2 == 0, i.e, n is even then exchange the position of the destination rod and auxiliary rod.
- Iterate i in 1 to moves
a. if i % 3 == 1:
i. Move the topmost disk of the source pole and place it on the top of the destination pole.
b. If i%3 == 2:
i. Move the topmost disk of the source pole and place it on the top of the auxiliary pole.
c. If i%3 == 0:
i. Move the topmost disk of the auxiliary pole and place it on the top of the destination pole.
Code Implementation:
public class TowerOfHanoi{
// Stack Class
class Stack
{
int capacity;
int top;
int array[];
}
// This function will create a new stack of the given capacity
Stack initStack(int capacity)
{
Stack st = new Stack();
st.capacity = capacity;
st.top = -1;
st.array = new int[capacity];
return st;
}
// This function checks whether the stack is full or not
boolean isFull(Stack st)
{
return (st.top == st.capacity - 1);
}
// This function checks whether the stack is empty or not
boolean isEmpty(Stack st)
{
return (st.top == -1);
}
// This function adds this item to the stack.
void push(Stack st, int item)
{
if (isFull(st)) {
return;
}
st.array[++st.top] = item;
}
// This function removes the top of the stack.
int pop(Stack st)
{
if (isEmpty(st))
return Integer.MIN_VALUE;
return st.array[st.top--];
}
// This function carries out the movement of the disk between two poles.
void move(Stack src, Stack dest,
char s, char d)
{
int disk1 = pop(src);
int disk2 = pop(dest);
// Is rod 1 is empty
if (disk1 == Integer.MIN_VALUE)
{
push(src, disk2);
printMove(d, s, disk2);
}
// if rod 2 is empty
else if (disk2 == Integer.MIN_VALUE)
{
push(dest, disk1);
printMove(s, d, disk1);
}
// If Disk 1 > Disk 2
else if (disk1 > disk2)
{
push(src, disk1);
push(src, disk2);
printMove(d, s, disk2);
}
// If Disk 1 < Disk 2
else
{
push(dest, disk2);
push(dest, disk1);
printMove(s, d, disk1);
}
}
// This function will print the movement of disks
void printMove(char from, char to, int disk)
{
System.out.println("Move the disk " + disk +
" from " + from +
" to " + to);
}
// Function to implement the algorithm
void iterativeTowerOfHanoi(int n, Stack
src, Stack aux, Stack dest)
{
int i, moves;
char s = 'S', d = 'D', a = 'A';
// If n is even then exchange the position of destination rod and auxiliary rod.
if (n % 2 == 0)
{
char temp = d;
d = a;
a = temp;
}
moves = (int)(Math.pow(
2, n) - 1);
for(i = n; i >= 1; i--)
push(src, i);
for(i = 1; i <= moves; i++)
{
if (i % 3 == 1)
move(src, dest, s, d);
else if (i % 3 == 2)
move(src, aux, s, a);
else if (i % 3 == 0)
move(aux, dest, a, d);
}
}
// Main function
public static void main(String[] args)
{
int n = 3;
TowerOfHanoi ob = new TowerOfHanoi();
// Create three stacks (Source, destination, Auxiliary)
Stack source = ob.initStack(n);
Stack destination = ob.initStack(n);
Stack auxiliary = ob.initStack(n);
ob.iterativeTowerOfHanoi(n, source, auxiliary, destination);
}
}
Output:
Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D
Time complexity: O(2n). The minimum number of moves required is 2n.
Space Complexity: O(n). We have to store at most n disks.
We tried to discuss the Program for the Tower of Hanoi. We hope this article gives you a better understanding of the Program for Tower of Hanoi. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.