The Tower of Hanoi is a mathematical puzzle with three poles and stacked disks of different sizes.
The goal is to move all disks from the source pole to the destination pole using an auxiliary pole, following two rules:
- Only one disk can be moved at a time.
- A larger disk cannot be placed on a smaller one.
We've already discussed a recursive solution for the Tower of Hanoi. We have also seen that for n disks, a total of 2n – 1 moves are required.
Iterative Algorithm:
1. Calculate the total number of moves required i.e. "pow(2, n) - 1" here n is number of disks.
2. If number of disks (i.e. n) is even then interchange destination pole and auxiliary pole.
3. for i = 1 to total number of moves
- if i%3 == 1: legal movement of top disk between source pole and destination pole
- if i%3 == 2: legal movement of top disk between source pole and auxiliary pole
- if i%3 == 0: legal movement of top disk between auxiliary pole and destination pole
Example:
Let us understand with a simple example with 3 disks:
After all iterations, the destination pole holds the disks in order of size. Each time a disk (other than the smallest) is moved, the next move must involve the smallest disk, as it remains on top of the spare pole with no other options available.
C++
#include <bits/stdc++.h>
using namespace std;
char rod[] = {'S', 'A', 'D'};
vector<stack<int>> stacks(3);
void moveDisk(int a, int b)
{
if (stacks[b].empty() || (!stacks[a].empty() && stacks[a].top() < stacks[b].top()))
{
cout << "Move disk " << stacks[a].top() << " from rod " << rod[a] << " to rod " << rod[b] << "\n";
stacks[b].push(stacks[a].top());
stacks[a].pop();
}
else
moveDisk(b, a);
}
void towerOfHanoi(int n)
{
cout << "Tower of Hanoi for " << n << " disks:\n";
int src = 0, aux = 1, dest = 2;
for (int i = n; i > 0; i--)
stacks[src].push(i);
int totalMoves = (1 << n) - 1;
if (n % 2 == 0)
swap(aux, dest);
for (int i = 1; i <= totalMoves; i++)
{
if (i % 3 == 0)
moveDisk(aux, dest);
else if (i % 3 == 1)
moveDisk(src, dest);
else
moveDisk(src, aux);
}
}
int main()
{
int n = 3; // number of disks
towerOfHanoi(n);
return 0;
}
import java.util.Stack;
public class GfG {
static char[] rod = { 'S', 'A', 'D' };
static Stack<Integer>[] stacks = new Stack[3];
static
{
for (int i = 0; i < 3; i++) {
stacks[i] = new Stack<>();
}
}
static void moveDisk(int a, int b)
{
if (stacks[b].isEmpty()
|| (!stacks[a].isEmpty()
&& stacks[a].peek() < stacks[b].peek())) {
System.out.println("Move disk "
+ stacks[a].peek()
+ " from rod " + rod[a]
+ " to rod " + rod[b]);
stacks[b].push(stacks[a].pop());
}
else {
moveDisk(b, a);
}
}
static void towerOfHanoi(int n)
{
System.out.println("Tower of Hanoi for " + n
+ " disks:");
int src = 0, aux = 1, dest = 2;
for (int i = n; i > 0; i--) {
stacks[src].push(i);
}
int totalMoves = (1 << n) - 1;
if (n % 2 == 0) {
int temp = aux;
aux = dest;
dest = temp;
}
for (int i = 1; i <= totalMoves; i++) {
if (i % 3 == 0)
moveDisk(aux, dest);
else if (i % 3 == 1)
moveDisk(src, dest);
else
moveDisk(src, aux);
}
}
public static void main(String[] args)
{
int n = 3; // number of disks
towerOfHanoi(n);
}
}
rod = ['S', 'A', 'D']
stacks = [[], [], []]
def moveDisk(a, b):
if not stacks[b] or (stacks[a] and stacks[a][-1] < stacks[b][-1]):
print(f"Move disk {stacks[a][-1]} from rod {rod[a]} to rod {rod[b]}")
stacks[b].append(stacks[a].pop())
else:
moveDisk(b, a)
def towerOfHanoi(n):
print(f"Tower of Hanoi for {n} disks:")
src, aux, dest = 0, 1, 2
stacks[src] = list(range(n, 0, -1))
totalMoves = (1 << n) - 1
if n % 2 == 0:
aux, dest = dest, aux
for i in range(1, totalMoves + 1):
if i % 3 == 0:
moveDisk(aux, dest)
elif i % 3 == 1:
moveDisk(src, dest)
else:
moveDisk(src, aux)
if __name__ == "__main__":
n = 3 # number of disks
towerOfHanoi(n)
using System;
using System.Collections.Generic;
class GfG {
static char[] rod = { 'S', 'A', 'D' };
static List<Stack<int> > stacks
= new List<Stack<int> >() {
new Stack<int>(), new Stack<int>(),
new Stack<int>()
};
static void moveDisk(int a, int b)
{
if (stacks[b].Count == 0
|| (stacks[a].Count > 0
&& stacks[a].Peek() < stacks[b].Peek())) {
Console.WriteLine(
$
"Move disk {stacks[a].Peek()} from rod {rod[a]} to rod {rod[b]}");
stacks[b].Push(stacks[a].Pop());
}
else {
moveDisk(b, a);
}
}
static void towerOfHanoi(int n)
{
Console.WriteLine(
$ "Tower of Hanoi for {n} disks:\n");
int src = 0, aux = 1, dest = 2;
for (int i = n; i > 0; i--)
stacks[src].Push(i);
int totalMoves = (1 << n) - 1;
if (n % 2 == 0)
(aux, dest) = (dest, aux);
for (int i = 1; i <= totalMoves; i++) {
if (i % 3 == 0)
moveDisk(aux, dest);
else if (i % 3 == 1)
moveDisk(src, dest);
else
moveDisk(src, aux);
}
}
static void Main()
{
int n = 3; // Number of disks
towerOfHanoi(n);
}
}
const rod = [ "S", "A", "D" ];
const stacks = [ [], [], [] ];
function moveDisk(a, b)
{
if (stacks[b].length === 0
|| (stacks[a].length > 0
&& stacks[a][stacks[a].length - 1]
< stacks[b][stacks[b].length - 1])) {
console.log(`Move disk ${
stacks[a][stacks[a].length - 1]} from rod ${
rod[a]} to rod ${rod[b]}`);
stacks[b].push(stacks[a].pop());
}
else {
moveDisk(b, a);
}
}
function towerOfHanoi(n)
{
console.log(`Tower of Hanoi for ${n} disks:\n`);
let src = 0, aux = 1, dest = 2;
for (let i = n; i > 0; i--)
stacks[src].push(i);
let totalMoves = (1 << n) - 1;
if (n % 2 === 0)
[aux, dest] = [ dest, aux ];
for (let i = 1; i <= totalMoves; i++) {
if (i % 3 === 0)
moveDisk(aux, dest);
else if (i % 3 === 1)
moveDisk(src, dest);
else
moveDisk(src, aux);
}
}
// Example: Run Tower of Hanoi for 3 disks
let n = 3;
towerOfHanoi(n);
OutputTower of Hanoi for 3 disks:
Move disk 1 from rod S to rod D
Move disk 2 from rod S to rod A
Move disk 1 from rod D to rod A
Move disk 3 from rod S to rod D
Move disk 1 from rod A to rod S
Move disk 2 ...
Time Complexity: O(2n) Since the iterative solution needs to generate and process all possible combinations of moves for n disks, the number of iterations grows exponentially with the number of disks.
Auxiliary Space: O(n)
Related Articles
References:
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem