Tower of Hanoi is a mathematical puzzle. In this puzzle, we are required to shift all the disks from rod/pole A to rode/pole B using rod/pole C. The disks should be arranged in ascending order i.e the smallest one on top. The transfer of disks from one pole to another works under two conditions –
- The transfer of multiple disks is not allowed. In other words, only one disk is allowed to move at a time.
- A larger disk can not be placed above the smaller one in any of the poles.
For Instance –
In the tower of Hanoi problem, we have given the number of disks representing disks of size from 1 to n. Print all the steps to move the disks from the starting pole to the destination pole.
Table of Contents
Example
3
Move the disk 1 from A to B Move the disk 2 from A to C Move the disk 1 from B to C Move the disk 3 from A to B Move the disk 1 from C to A Move the disk 2 from C to B Move the disk 1 from A to B
1
Move the disk 1 from A to B
Algorithm
Move to the algorithm part for the Tower of Hanoi problem.
- Initialize an integer n representing a number of disks.
- Create 3 stacks for source, destination, and auxiliary. Similarly, Create 3 variables s as ‘A’, d as ‘B’, a as ‘C’.
- Check if the number of disks mod 2 is 0, store d in a temporary variable. After that, update d as a and a as temporary variable.
- Firstly, create a variable for the total number of moves and update it as (n*n) -1.
- Traverse from n to 1 and push the current value in source stack.
- Traverse from 1 to total moves and check if current index mod 3 is 1, pop the top from source and destination stack. If the popped top of source stack is equal to INT_MIN, push the popped top of destination to source.
- Else If the popped top of destination stack is equal to INT_MIN, push the popped top of source stack to destination stack.
- Else If the popped top of source stack is greater than the popped top of destination stack, push both the tops in source stack, else push both in destination stack. After that, print the traversal.
- Similarly, check if current index mod 3 is 2, pop the top from source, and auxiliary stack. If the popped top of source stack is equal to INT_MIN, push the popped top of the auxiliary stack to source stack.
- Else If the popped top of the auxiliary stack is equal to INT_MIN, push the popped top of source stack to auxiliary stack.
- Else If the popped top of source stack is greater than the popped top of the auxiliary stack, push both the tops in source stack, else push both in the auxiliary stack. After that, print the traversal.
- Similarly, check if current index mod 3 is 0, pop the top from auxiliary and destination stack. If the popped top of the auxiliary stack is equal to INT_MIN, push the popped top of destination stack to auxiliary stack.
- Else If the popped top of destination stack is equal to INT_MIN, push the popped top of the auxiliary stack to destination stack.
- Else If the popped top of the auxiliary stack is greater than the popped top of destination stack, push both the tops in the auxiliary stack, else push both in destination stack. After that, print the traversal.
C++ Program for Iterative Tower of Hanoi
#include <bits/stdc++.h>
using namespace std;
struct Stack{
unsigned capacity;
int top;
int *array;
};
struct Stack* createStack(unsigned capacity){
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack -> capacity = capacity;
stack -> top = -1;
stack -> array = (int*) malloc(stack -> capacity * sizeof(int));
return stack;
}
int isFull(struct Stack* stack){
return (stack->top == stack->capacity - 1);
}
int isEmpty(struct Stack* stack){
return (stack->top == -1);
}
void push(struct Stack *stack, int item){
if(isFull(stack)){
return;
}
stack -> array[++stack -> top] = item;
}
int pop(struct Stack* stack){
if(isEmpty(stack)){
return INT_MIN;
}
return stack -> array[stack -> top--];
}
void moveDisk(char fromPeg, char toPeg, int disk){
cout<<"Move the disk "<<disk<<" from "<<fromPeg<<" to "<<toPeg<<endl;
}
void moveDisksBetweenTwoPoles(struct Stack *src, struct Stack *dest, char s, char d)
{
int pole1TopDisk = pop(src);
int pole2TopDisk = pop(dest);
if (pole1TopDisk == INT_MIN){
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
else if(pole2TopDisk == INT_MIN){
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
else if(pole1TopDisk > pole2TopDisk){
push(src, pole1TopDisk);
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
else{
push(dest, pole2TopDisk);
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
}
void TowerOfHanoi(int num_of_disks, struct Stack *src, struct Stack *aux, struct Stack *dest){
int i, total_num_of_moves;
char s = 'A', d = 'B', a = 'C';
if(num_of_disks % 2 == 0){
char temp = d;
d = a;
a = temp;
}
total_num_of_moves = pow(2, num_of_disks) - 1;
for(i = num_of_disks; i >= 1; i--){
push(src, i);
}
for(i = 1; i <= total_num_of_moves; i++){
if(i % 3 == 1){
moveDisksBetweenTwoPoles(src, dest, s, d);
}
else if(i % 3 == 2){
moveDisksBetweenTwoPoles(src, aux, s, a);
}
else if(i % 3 == 0){
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
}
int main(){
unsigned n = 3;
struct Stack *source, *destination, *auxiliary;
source = createStack(n);
auxiliary = createStack(n);
destination = createStack(n);
TowerOfHanoi(n, source, auxiliary, destination);
return 0;
}Move the disk 1 from A to B Move the disk 2 from A to C Move the disk 1 from B to C Move the disk 3 from A to B Move the disk 1 from C to A Move the disk 2 from C to B Move the disk 1 from A to B
Java Program for Iterative Tower of Hanoi
class Iterative_TOH{
class Stack{
int capacity;
int top;
int array[];
}
Stack createStack(int capacity){
Stack stack=new Stack();
stack.capacity = capacity;
stack.top = -1;
stack.array = new int[capacity];
return stack;
}
boolean isFull(Stack stack){
return (stack.top == stack.capacity - 1);
}
boolean isEmpty(Stack stack){
return (stack.top == -1);
}
void push(Stack stack,int item){
if(isFull(stack)){
return;
}
stack.array[++stack.top] = item;
}
int pop(Stack stack){
if(isEmpty(stack)) {
return Integer.MIN_VALUE;
}
return stack.array[stack.top--];
}
void moveDisksBetweenTwoPoles(Stack src, Stack dest, char s, char d){
int pole1TopDisk = pop(src);
int pole2TopDisk = pop(dest);
if (pole1TopDisk == Integer.MIN_VALUE){
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
else if (pole2TopDisk == Integer.MIN_VALUE){
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
else if (pole1TopDisk > pole2TopDisk){
push(src, pole1TopDisk);
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
else{
push(dest, pole2TopDisk);
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
}
void moveDisk(char fromPeg, char toPeg, int disk){
System.out.println("Move the disk "+disk + " from "+fromPeg+" to "+toPeg);
}
void TowerOfHanoi(int num_of_disks, Stack src, Stack aux, Stack dest){
int i, total_num_of_moves;
char s = 'A', d = 'B', a = 'C';
if(num_of_disks % 2 == 0){
char temp = d;
d = a;
a = temp;
}
total_num_of_moves = (int) (Math.pow(2, num_of_disks) - 1);
for(i = num_of_disks; i >= 1; i--){
push(src, i);
}
for(i = 1; i <= total_num_of_moves; i++){
if (i % 3 == 1){
moveDisksBetweenTwoPoles(src, dest, s, d);
}
else if(i % 3 == 2){
moveDisksBetweenTwoPoles(src, aux, s, a);
}
else if(i % 3 == 0){
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
}
public static void main(String[] args){
int n = 3;
Iterative_TOH ob = new Iterative_TOH();
Stack source, destination, auxiliary;
source = ob.createStack(n);
destination = ob.createStack(n);
auxiliary = ob.createStack(n);
ob.TowerOfHanoi(n, source, auxiliary, destination);
}
}Move the disk 1 from A to B Move the disk 2 from A to C Move the disk 1 from B to C Move the disk 3 from A to B Move the disk 1 from C to A Move the disk 2 from C to B Move the disk 1 from A to B
Complexity Analysis for Iterative Tower of Hanoi
Time Complexity: O(2n) where n is the number of disks in the tower of Hanoi problem.
Auxiliary Space: O(n) because we used stack space.
References for the iterative method for implement tower of Hanoi.