Implement tower of hanoi using stack
The Tower of Hanoi is a classic puzzle game that involves three poles and a number of disks of different sizes. The goal of the game is to move all the disks from one pole to another pole while following the rules:
- Only one disk can be moved at a time.
- A larger disk cannot be placed on top of a smaller disk.
The problem of moving the entire tower from one pole to another pole is solved recursively. However, in this implementation, we will use an iterative approach and a stack data structure to simulate the recursive steps.
Problem Statement
Given the number of disks in the Tower of Hanoi game, we need to implement an iterative solution using a stack to print the sequence of movements required to solve the puzzle.
Explanation with Suitable Example
Let's consider the Tower of Hanoi problem with four disks (denoted as 1, 2, 3, and 4). The initial configuration is as follows:
Tower 1 (source pole): 4 → 3 → 2 → 1
Tower 2 (auxiliary pole): empty
Tower 3 (destination pole): empty
The goal is to move all the disks from Tower 1 to Tower 3 while following the rules mentioned above.
Idea to Solve the Problem
The iterative approach to solve the Tower of Hanoi problem using a stack involves simulating the recursive steps without using actual recursive function calls. We will maintain a custom stack to store the state of each disk movement. The stack will contain information about the disk being moved, its source, auxiliary, and destination poles.
Pseudocode
The following pseudocode outlines the steps to solve the Tower of Hanoi problem iteratively using a stack:
function towerOfHanoi(total_disk)
if total_disk <= 0, return
create an empty custom stack
initialize disk to total_disk
initialize source, auxiliary, and destination poles (1, 2, and 3 respectively)
while disk > 0 or the stack is not empty
if disk > 0
create a new stack node with current disk and pole information
push the node onto the stack
swap auxiliary and destination poles
decrement disk
else
peek the top node from the stack
print the movement of the disk using node's information
update source, destination, disk, and auxiliary poles based on node's information
pop the node from the stack
Algorithm Explanation
- Check if the total number of disks is non-positive (total_disk <= 0), if so, return as there is nothing to move.
- Create an empty custom stack to store the disk movement information.
- Initialize the current disk size (disk) to the total number of disks.
- Initialize the source, auxiliary, and destination poles to 1, 2, and 3, respectively.
- Use a loop to simulate the recursive steps:
- If the current disk size is greater than 0:
- Create a new stack node with the current disk size and pole information.
- Push the node onto the stack.
- Swap the auxiliary and destination poles (since we are moving in the opposite direction in the iterative approach).
- Decrement the current disk size.
- Else:
- Peek the top node from the stack (without removing it).
- Print the movement of the disk using the node's information (source pole to destination pole).
- Update the source, destination, auxiliary, and disk size based on the node's information.
- Pop the node from the stack.
- If the current disk size is greater than 0:
Code Solution
Here given code implementation process.
// C program
// Implement tower of hanoi using stack
#include <stdio.h>
#include <stdlib.h>
// Define stack node
struct StackNode
{
int disk;
int source;
int auxiliary;
int destination;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
//Create a new node of stack
struct StackNode *newNode(int disk, int source, int destination, int auxiliary)
{
//Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->disk = disk;
node->source = source;
node->destination = destination;
node->auxiliary = auxiliary;
}
return node;
}
// add node at the top of stack
void push(struct MyStack *stack, struct StackNode *node)
{
node->next = stack->top;
stack->top = node;
stack->size++;
}
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// return top element of stack
struct StackNode *peek(struct MyStack *stack)
{
return stack->top;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Display the movement of current disk
void printResult(struct StackNode *node)
{
printf(" Move disk %d from tower [%d] to [%d]\n", node->disk, node->source, node->destination);
}
// Iterative tower of hanoi implementation
void towerOfHanoi(int total_disk)
{
if (total_disk > 0)
{
// Display total disk
printf("\n Total Disk %d \n", total_disk);
int disk = total_disk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
// Create a stack which is hold information of execute steps
struct MyStack *stack = newStack();
struct StackNode *node = NULL;
int temp = 0;
while (disk > 0 || isEmpty(stack) == 0)
{
if (disk > 0)
{
node = newNode(disk, source, destination, auxiliary);
// Add stack node
push(stack, node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
// Reduce disk size
disk--;
}
else
{
// Get top element of stack
node = peek(stack);
// Display movement of disk
printResult(node);
// Get new execution info
source = node->auxiliary;
destination = node->destination;
disk = node->disk - 1;
auxiliary = node->source;
// Remove stack elemnt
pop(stack);
}
}
}
}
int main()
{
// Test case
towerOfHanoi(4);
towerOfHanoi(3);
return 0;
}Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]/*
Java Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
public int disk;
public int source;
public int auxiliary;
public int destination;
public StackNode next;
public StackNode(int disk,int source,int destination,int auxiliary)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
public void printResult()
{
System.out.print(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(StackNode node)
{
node.next = this.top;
this.top = node;
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public StackNode peek()
{
return this.top;
}
}
public class TowerOfHanoi
{
public MyStack stack;
public TowerOfHanoi()
{
this.stack = new MyStack();
}
// Iterative tower of hanoi implementation
public void towerOfHanoi(int total_disk)
{
if (total_disk > 0)
{
// Display total disk
System.out.print("\n Total Disk " + total_disk + " \n");
int disk = total_disk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
StackNode node = null;
int temp = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
// Reduce disk size
disk--;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
public static void main(String[] args)
{
TowerOfHanoi process = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
}Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
public: int disk;
int source;
int auxiliary;
int destination;
StackNode *next;
StackNode(int disk, int source, int destination, int auxiliary)
{
this->disk = disk;
this->source = source;
this->destination = destination;
this->auxiliary = auxiliary;
}
// Display the movement of current disk
void printResult()
{
cout << " Move disk " << this->disk << " from tower [" << this->source << "] to [" << this->destination << "]\n";
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(StackNode *node)
{
node->next = this->top;
this->top = node;
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
// return top element of stack
StackNode *peek()
{
return this->top;
}
};
class TowerOfHanoi
{
public: MyStack *stack;
TowerOfHanoi()
{
this->stack = new MyStack();
}
// Iterative tower of hanoi implementation
void towerOfHanoi(int totalDisk)
{
if (totalDisk > 0)
{
// Display total disk
cout << "\n Total Disk " << totalDisk << " \n";
int disk = totalDisk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
StackNode *node = NULL;
int temp = 0;
while (disk > 0 || this->stack->isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this->stack->push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk--;
}
else
{
// Get top element of stack
node = this->stack->peek();
// Display movement of disk
node->printResult();
// Get new execution info
source = node->auxiliary;
destination = node->destination;
disk = node->disk - 1;
auxiliary = node->source;
// Remove stack elemnt
this->stack->pop();
}
}
}
}
};
int main()
{
TowerOfHanoi process = TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
return 0;
}Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]// Include namespace system
using System;
/*
C# Program
Implement tower of hanoi using stack
*/
// Define stack node
public class StackNode
{
public int disk;
public int source;
public int auxiliary;
public int destination;
public StackNode next;
public StackNode(int disk, int source, int destination, int auxiliary)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
public void printResult()
{
Console.Write(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(StackNode node)
{
node.next = this.top;
this.top = node;
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public StackNode peek()
{
return this.top;
}
}
public class TowerOfHanoi
{
public MyStack stack;
public TowerOfHanoi()
{
this.stack = new MyStack();
}
// Iterative tower of hanoi implementation
public void towerOfHanoi(int totalDisk)
{
if (totalDisk > 0)
{
// Display total disk
Console.Write("\n Total Disk " + totalDisk + " \n");
int disk = totalDisk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
StackNode node = null;
int temp = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk--;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
public static void Main(String[] args)
{
TowerOfHanoi process = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
}Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]<?php
/*
Php Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
public $disk;
public $source;
public $auxiliary;
public $destination;
public $next;
function __construct($disk, $source, $destination, $auxiliary)
{
$this->disk = $disk;
$this->source = $source;
$this->destination = $destination;
$this->auxiliary = $auxiliary;
}
// Display the movement of current disk
public function printResult()
{
echo " Move disk ". $this->disk ." from tower [". $this->source ."] to [". $this->destination ."]\n";
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
function __construct()
{
//Set node values
$this->top = null;
$this->size = 0;
}
// Add node at the top of stack
public function push($node)
{
$node->next = $this->top;
$this->top = $node;
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != null)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = null;
$this->size--;
}
}
// return top element of stack
public function peek()
{
return $this->top;
}
}
class TowerOfHanoi
{
public $stack;
function __construct()
{
$this->stack = new MyStack();
}
// Iterative tower of hanoi implementation
public function towerOfHanoi($totalDisk)
{
if ($totalDisk > 0)
{
// Display total disk
echo "\n Total Disk ". $totalDisk ." \n";
$disk = $totalDisk;
// Set the poles tag
$source = 1;
$auxiliary = 2;
$destination = 3;
$node = null;
$temp = 0;
while ($disk > 0 || $this->stack->isEmpty() == false)
{
if ($disk > 0)
{
// Reduce disk size
$node = new StackNode($disk, $source, $destination, $auxiliary);
// Add stack node
$this->stack->push($node);
// Change execution variables
$temp = $destination;
$destination = $auxiliary;
$auxiliary = $temp;
$disk--;
}
else
{
// Get top element of stack
$node = $this->stack->peek();
// Display movement of disk
$node->printResult();
// Get new execution info
$source = $node->auxiliary;
$destination = $node->destination;
$disk = $node->disk - 1;
$auxiliary = $node->source;
// Remove stack elemnt
$this->stack->pop();
}
}
}
}
}
function main()
{
$process = new TowerOfHanoi();
// Test case
$process->towerOfHanoi(4);
$process->towerOfHanoi(3);
}
main();Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]/*
Node Js Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
constructor(disk, source, destination, auxiliary)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
printResult()
{
process.stdout.write(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(node)
{
node.next = this.top;
this.top = node;
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
return this.top;
}
}
class TowerOfHanoi
{
constructor()
{
this.stack = new MyStack();
}
// Iterative tower of hanoi implementation
towerOfHanoi(totalDisk)
{
if (totalDisk > 0)
{
// Display total disk
process.stdout.write("\n Total Disk " + totalDisk + " \n");
var disk = totalDisk;
// Set the poles tag
var source = 1;
var auxiliary = 2;
var destination = 3;
var node = null;
var temp = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk--;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
}
function main()
{
var process = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
main();Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]# Python 3 Program
# Implement tower of hanoi using stack
# Define stack node
class StackNode :
def __init__(self, disk, source, destination, auxiliary) :
self.disk = disk
self.source = source
self.destination = destination
self.auxiliary = auxiliary
# Display the movement of current disk
def printResult(self) :
print(" Move disk [{0}] from tower [{1}] to [{2}]".format(self.disk,self.source,self.destination))
# Define a custom stack
class MyStack :
def __init__(self) :
# Set node values
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, node) :
node.next = self.top
self.top = node
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
return self.top
class TowerOfHanoi :
def __init__(self) :
self.stack = MyStack()
# Iterative tower of hanoi implementation
def towerOfHanoi(self, totalDisk) :
if (totalDisk > 0) :
# Display total disk
print("\n Total Disk ", totalDisk ," ")
disk = totalDisk
# Set the poles tag
source = 1
auxiliary = 2
destination = 3
node = None
temp = 0
while (disk > 0 or self.stack.isEmpty() == False) :
if (disk > 0) :
node = StackNode(disk, source, destination, auxiliary)
# Add stack node
self.stack.push(node)
# Change execution variables
temp = destination
destination = auxiliary
auxiliary = temp
# Reduce disk size
disk -= 1
else :
# Get top element of stack
node = self.stack.peek()
# Display movement of disk
node.printResult()
# Get new execution info
source = node.auxiliary
destination = node.destination
disk = node.disk - 1
auxiliary = node.source
# Remove stack elemnt
self.stack.pop()
def main() :
process = TowerOfHanoi()
# Test case
process.towerOfHanoi(4)
process.towerOfHanoi(3)
if __name__ == "__main__": main()Output
Total Disk 4
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [3] from tower [1] to [2]
Move disk [1] from tower [3] to [1]
Move disk [2] from tower [3] to [2]
Move disk [1] from tower [1] to [2]
Move disk [4] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [2] from tower [2] to [1]
Move disk [1] from tower [3] to [1]
Move disk [3] from tower [2] to [3]
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Total Disk 3
Move disk [1] from tower [1] to [3]
Move disk [2] from tower [1] to [2]
Move disk [1] from tower [3] to [2]
Move disk [3] from tower [1] to [3]
Move disk [1] from tower [2] to [1]
Move disk [2] from tower [2] to [3]
Move disk [1] from tower [1] to [3]# Ruby Program
# Implement tower of hanoi using stack
# Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :disk, :source, :auxiliary, :destination, :next
attr_accessor :disk, :source, :auxiliary, :destination, :next
def initialize(disk, source, destination, auxiliary)
self.disk = disk
self.source = source
self.destination = destination
self.auxiliary = auxiliary
end
# Display the movement of current disk
def printResult()
print(" Move disk ", self.disk ," from tower [", self.source ,"] to [", self.destination ,"]\n")
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
# Set node values
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(node)
node.next = self.top
self.top = node
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
return self.top
end
end
class TowerOfHanoi
# Define the accessor and reader of class TowerOfHanoi
attr_reader :stack
attr_accessor :stack
def initialize()
self.stack = MyStack.new()
end
# Iterative tower of hanoi implementation
def towerOfHanoi(totalDisk)
if (totalDisk > 0)
# Display total disk
print("\n Total Disk ", totalDisk ," \n")
disk = totalDisk
# Set the poles tag
source = 1
auxiliary = 2
destination = 3
node = nil
temp = 0
while (disk > 0 || self.stack.isEmpty() == false)
if (disk > 0)
node = StackNode.new(disk, source, destination, auxiliary)
# Add stack node
self.stack.push(node)
# Change execution variables
temp = destination
destination = auxiliary
auxiliary = temp
# Reduce disk size
disk -= 1
else
# Get top element of stack
node = self.stack.peek()
# Display movement of disk
node.printResult()
# Get new execution info
source = node.auxiliary
destination = node.destination
disk = node.disk - 1
auxiliary = node.source
# Remove stack elemnt
self.stack.pop()
end
end
end
end
end
def main()
process = TowerOfHanoi.new()
# Test case
process.towerOfHanoi(4)
process.towerOfHanoi(3)
end
main()Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
/*
Scala Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode(var disk: Int , var source: Int , var auxiliary: Int , var destination: Int , var next: StackNode)
{
def this(disk: Int, source: Int, destination: Int, auxiliary: Int)
{
this(disk, source, auxiliary, destination, null);
}
// Display the movement of current disk
def printResult(): Unit = {
print(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(node: StackNode): Unit = {
node.next = this.top;
this.top = node;
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): StackNode = {
return this.top;
}
}
class TowerOfHanoi(var stack: MyStack)
{
def this()
{
this(new MyStack());
}
// Iterative tower of hanoi implementation
def towerOfHanoi(totalDisk: Int): Unit = {
if (totalDisk > 0)
{
// Display total disk
print("\n Total Disk " + totalDisk + " \n");
var disk: Int = totalDisk;
// Set the poles tag
var source: Int = 1;
var auxiliary: Int = 2;
var destination: Int = 3;
var node: StackNode = null;
var temp: Int = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk -= 1;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var process: TowerOfHanoi = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
}Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]/*
Swift 4 Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
var disk: Int;
var source: Int;
var auxiliary: Int;
var destination: Int;
var next: StackNode? ;
init(_ disk: Int, _ source: Int, _ destination: Int, _ auxiliary: Int)
{
self.disk = disk;
self.source = source;
self.destination = destination;
self.auxiliary = auxiliary;
}
// Display the movement of current disk
func printResult()
{
print(" Move disk [\(self.disk)] from tower [\(self.source)] to [\(self.destination)]");
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ node: StackNode? )
{
node!.next = self.top;
self.top = node;
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek()->StackNode?
{
return self.top;
}
}
class TowerOfHanoi
{
var stack: MyStack? ;
init()
{
self.stack = MyStack();
}
// Iterative tower of hanoi implementation
func towerOfHanoi(_ totalDisk: Int)
{
if (totalDisk > 0)
{
// Display total disk
print("\n Total Disk ", totalDisk ," ");
var disk: Int = totalDisk;
// Set the poles tag
var source: Int = 1;
var auxiliary: Int = 2;
var destination: Int = 3;
var node: StackNode? = nil;
var temp: Int = 0;
while (disk > 0 || self.stack!.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = StackNode(disk, source, destination, auxiliary);
// Add stack node
self.stack!.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk -= 1;
}
else
{
// Get top element of stack
node = self.stack!.peek();
// Display movement of disk
node!.printResult();
// Get new execution info
source = node!.auxiliary;
destination = node!.destination;
disk = node!.disk - 1;
auxiliary = node!.source;
// Remove stack elemnt
self.stack!.pop();
}
}
}
}
}
func main()
{
let process: TowerOfHanoi = TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
main();Output
Total Disk 4
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [3] from tower [1] to [2]
Move disk [1] from tower [3] to [1]
Move disk [2] from tower [3] to [2]
Move disk [1] from tower [1] to [2]
Move disk [4] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [2] from tower [2] to [1]
Move disk [1] from tower [3] to [1]
Move disk [3] from tower [2] to [3]
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Total Disk 3
Move disk [1] from tower [1] to [3]
Move disk [2] from tower [1] to [2]
Move disk [1] from tower [3] to [2]
Move disk [3] from tower [1] to [3]
Move disk [1] from tower [2] to [1]
Move disk [2] from tower [2] to [3]
Move disk [1] from tower [1] to [3]/*
Kotlin Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
var disk: Int;
var source: Int;
var auxiliary: Int;
var destination: Int;
var next: StackNode ? = null;
constructor(disk: Int, source: Int, destination: Int, auxiliary: Int)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
fun printResult(): Unit
{
print(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(node: StackNode ? ): Unit
{
node?.next = this.top;
this.top = node;
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size>0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size>0 && this.top != null)
{
var temp: StackNode? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): StackNode ?
{
return this.top;
}
}
class TowerOfHanoi
{
var stack: MyStack;
constructor()
{
this.stack = MyStack();
}
// Iterative tower of hanoi implementation
fun towerOfHanoi(totalDisk: Int): Unit
{
if (totalDisk>0)
{
// Display total disk
print("\n Total Disk " + totalDisk + " \n");
var disk: Int = totalDisk;
// Set the poles tag
var source: Int = 1;
var auxiliary: Int = 2;
var destination: Int = 3;
var node: StackNode? ;
var temp: Int ;
while (disk>0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk -= 1;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node?.printResult();
if(node!=null)
{
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
}
// Remove stack elemnt
this.stack.pop();
}
}
}
}
}
fun main(args: Array<String>): Unit
{
var process: TowerOfHanoi = TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]Time Complexity
The time complexity of the iterative Tower of Hanoi algorithm is O(2^n), where n is the number of disks. Since we are simulating the recursive steps iteratively, the number of iterations in the while loop is 2^n. This is equivalent to the number of recursive function calls in the standard recursive solution.
Resultant Output Explanation
For the given test case with four disks:
towerOfHanoi(4);The output shows the sequence of movements to solve the Tower of Hanoi puzzle:
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
The output demonstrates the sequence of disk movements required to solve the Tower of Hanoi puzzle iteratively using a stack.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment