Skip to main content

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:

  1. Only one disk can be moved at a time.
  2. 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

  1. Check if the total number of disks is non-positive (total_disk <= 0), if so, return as there is nothing to move.
  2. Create an empty custom stack to store the disk movement information.
  3. Initialize the current disk size (disk) to the total number of disks.
  4. Initialize the source, auxiliary, and destination poles to 1, 2, and 3, respectively.
  5. 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.

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.





Comment

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