The Tower of Hanoi is a mathematical puzzle. It consists of three poles and a number of disks of different sizes which can slide onto any pole. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks from one pole (say ‘source pole’) to another pole (say ‘destination pole’) with the help of the third pole (say auxiliary pole).
The puzzle has the following two rules:
     1. You can’t place a larger disk onto a smaller diskÂ
     2. Only one disk can be moved at a time
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 top disk between source pole and auxiliary pole if i%3 == 0: legal movement top disk between auxiliary pole and destination pole
Example:Â
Let us understand with a simple example with 3 disks: So, total number of moves required = 7
S A D When i= 1, (i % 3 == 1) legal movement between‘S’ and ‘D’
When i = 2, (i % 3 == 2) legal movement between ‘S’ and ‘A’
When i = 3, (i % 3 == 0) legal movement between ‘A’ and ‘D’ ’
When i = 4, (i % 3 == 1) legal movement between ‘S’ and ‘D’
When i = 5, (i % 3 == 2) legal movement between ‘S’ and ‘A’
When i = 6, (i % 3 == 0) legal movement between ‘A’ and ‘D’
When i = 7, (i % 3 == 1) legal movement between ‘S’ and ‘D’
So, after all these destination poles contains all the in order of size.Â
After observing above iterations, we can think that after a disk other than the smallest disk is moved, the next disk to be moved must be the smallest disk because it is the top disk resting on the spare pole and there are no other choices to move a disk.
C++
// C++ Program for Iterative Tower of Hanoi using STL Â
#include <iostream> #include <vector> #include <stack> using namespace std; Â
char rod[]={ 'S' , 'A' , 'D' }; vector<stack< int >> stacks(3); // 3 stacks for 3 rods Â
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; } |
C
// C Program for Iterative Tower of Hanoi #include <stdio.h> #include <math.h> #include <stdlib.h> #include <limits.h> Â
// A structure to represent a stack struct Stack { unsigned capacity; int top; int *array; }; Â
// function to create a stack of given capacity. 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; } Â
// Stack is full when top is equal to the last index int isFull( struct Stack* stack) { return (stack->top == stack->capacity - 1); } Â
// Stack is empty when top is equal to -1 int isEmpty( struct Stack* stack) { return (stack->top == -1); } Â
// Function to add an item to stack. It increases // top by 1 void push( struct Stack *stack, int item) { Â Â Â Â if (isFull(stack)) Â Â Â Â Â Â Â Â return ; Â Â Â Â stack -> array[++stack -> top] = item; } Â
// Function to remove an item from stack. It // decreases top by 1 int pop( struct Stack* stack) { Â Â Â Â if (isEmpty(stack)) Â Â Â Â Â Â Â Â return INT_MIN; Â Â Â Â return stack -> array[stack -> top--]; } Â
//Function to show the movement of disks void moveDisk( char fromPeg, char toPeg, int disk) { Â Â Â Â printf ( "Move the disk %d from \'%c\' to \'%c\'\n" , Â Â Â Â Â Â Â Â disk, fromPeg, toPeg); } Â
// Function to implement legal movement between // two poles void moveDisksBetweenTwoPoles( struct Stack *src, Â Â Â Â Â Â Â Â Â Â Â Â struct Stack *dest, char s, char d) { Â Â Â Â int pole1TopDisk = pop(src); Â Â Â Â int pole2TopDisk = pop(dest); Â
    // When pole 1 is empty     if (pole1TopDisk == INT_MIN)     {         push(src, pole2TopDisk);         moveDisk(d, s, pole2TopDisk);     } Â
    // When pole2 pole is empty     else if (pole2TopDisk == INT_MIN)     {         push(dest, pole1TopDisk);         moveDisk(s, d, pole1TopDisk);     } Â
    // When top disk of pole1 > top disk of pole2     else if (pole1TopDisk > pole2TopDisk)     {         push(src, pole1TopDisk);         push(src, pole2TopDisk);         moveDisk(d, s, pole2TopDisk);     } Â
    // When top disk of pole1 < top disk of pole2     else     {         push(dest, pole2TopDisk);         push(dest, pole1TopDisk);         moveDisk(s, d, pole1TopDisk);     } } Â
//Function to implement TOH puzzle void tohIterative( int num_of_disks, struct Stack             *src, struct Stack *aux,             struct Stack *dest) {     int i, total_num_of_moves;     char s = 'S' , d = 'D' , a = 'A' ; Â
    //If number of disks is even, then interchange     //destination pole and auxiliary pole     if (num_of_disks % 2 == 0)     {         char temp = d;         d = a;         a = temp;     }     total_num_of_moves = pow (2, num_of_disks) - 1; Â
    //Larger disks will be pushed first     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);     } } Â
// Driver Program int main() {     // Input: number of disks     unsigned num_of_disks = 3; Â
    struct Stack *src, *dest, *aux; Â
    // Create three stacks of size 'num_of_disks'     // to hold the disks     src = createStack(num_of_disks);     aux = createStack(num_of_disks);     dest = createStack(num_of_disks); Â
    tohIterative(num_of_disks, src, aux, dest);     return 0; } |
Java
// Java program for iterative // Tower of Hanoi class TOH{ Â Â Â Â Â // A structure to represent a stack class Stack { Â Â Â Â int capacity; Â Â Â Â int top; Â Â Â Â int array[]; } Â
// Function to create a stack of given capacity. Stack createStack( int capacity) { Â Â Â Â Stack stack = new Stack(); Â Â Â Â stack.capacity = capacity; Â Â Â Â stack.top = - 1 ; Â Â Â Â stack.array = new int [capacity]; Â Â Â Â return stack; } Â
// Stack is full when the top is equal // to the last index boolean isFull(Stack stack) { Â Â Â Â return (stack.top == stack.capacity - 1 ); } Â
// Stack is empty when top is equal to -1 boolean isEmpty(Stack stack) { Â Â Â Â return (stack.top == - 1 ); } Â
// Function to add an item to stack.It // increases top by 1 void push(Stack stack, int item) { Â Â Â Â if (isFull(stack)) Â Â Â Â Â Â Â Â return ; Â Â Â Â Â Â Â Â Â Â Â Â Â stack.array[++stack.top] = item; } Â
// Function to remove an item from stack.It // decreases top by 1 int pop(Stack stack) { Â Â Â Â if (isEmpty(stack)) Â Â Â Â Â Â Â Â return Integer.MIN_VALUE; Â Â Â Â Â Â Â Â Â Â Â Â Â return stack.array[stack.top--]; } Â
// Function to implement legal movement between // two poles void moveDisksBetweenTwoPoles(Stack src, Stack dest, Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â char s, char d) { Â Â Â Â int pole1TopDisk = pop(src); Â Â Â Â int pole2TopDisk = pop(dest); Â
    // When pole 1 is empty     if (pole1TopDisk == Integer.MIN_VALUE)     {         push(src, pole2TopDisk);         moveDisk(d, s, pole2TopDisk);     }          // When pole2 pole is empty     else if (pole2TopDisk == Integer.MIN_VALUE)     {         push(dest, pole1TopDisk);         moveDisk(s, d, pole1TopDisk);     }          // When top disk of pole1 > top disk of pole2     else if (pole1TopDisk > pole2TopDisk)     {         push(src, pole1TopDisk);         push(src, pole2TopDisk);         moveDisk(d, s, pole2TopDisk);     }     // When top disk of pole1 < top disk of pole2     else     {         push(dest, pole2TopDisk);         push(dest, pole1TopDisk);         moveDisk(s, d, pole1TopDisk);     } } Â
// Function to show the movement of disks void moveDisk( char fromPeg, char toPeg, int disk) { Â Â Â Â System.out.println( "Move the disk " + disk + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â " from " + fromPeg + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â " to " + toPeg); } Â
// Function to implement TOH puzzle void tohIterative( int num_of_disks, Stack                   src, Stack aux, Stack dest) {     int i, total_num_of_moves;     char s = 'S' , d = 'D' , a = 'A' ;       // If number of disks is even, then     // interchange destination pole and     // auxiliary pole     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 );       // Larger disks will be pushed first     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);     } } Â
// Driver code public static void main(String[] args) {          // Input: number of disks     int num_of_disks = 3 ;          TOH ob = new TOH();     Stack src, dest, aux;          // Create three stacks of size 'num_of_disks'     // to hold the disks     src = ob.createStack(num_of_disks);     dest = ob.createStack(num_of_disks);     aux = ob.createStack(num_of_disks);          ob.tohIterative(num_of_disks, src, aux, dest); } } Â
// This code is contributed by Sumit Ghosh |
Python3
# Python3 program for iterative Tower of Hanoi import sys Â
# A structure to represent a stack class Stack:     # Constructor to set the data of     # the newly created tree node     def __init__( self , capacity):         self .capacity = capacity         self .top = - 1         self .array = [ 0 ] * capacity Â
# function to create a stack of given capacity. def createStack(capacity):     stack = Stack(capacity)     return stack   # Stack is full when top is equal to the last index def isFull(stack):     return (stack.top = = (stack.capacity - 1 ))    # Stack is empty when top is equal to -1 def isEmpty(stack):     return (stack.top = = - 1 )    # Function to add an item to stack. # It increases top by 1 def push(stack, item):     if (isFull(stack)):         return     stack.top + = 1     stack.array[stack.top] = item    # Function to remove an item from stack. # It decreases top by 1 def Pop(stack):     if (isEmpty(stack)):         return - sys.maxsize     Top = stack.top     stack.top - = 1     return stack.array[Top]    # Function to implement legal # movement between two poles def moveDisksBetweenTwoPoles(src, dest, s, d):     pole1TopDisk = Pop(src)     pole2TopDisk = Pop(dest) Â
    # When pole 1 is empty     if (pole1TopDisk = = - sys.maxsize):         push(src, pole2TopDisk)         moveDisk(d, s, pole2TopDisk)            # When pole2 pole is empty     else if (pole2TopDisk = = - sys.maxsize):         push(dest, pole1TopDisk)         moveDisk(s, d, pole1TopDisk)            # When top disk of pole1 > top disk of pole2     else if (pole1TopDisk > pole2TopDisk):         push(src, pole1TopDisk)         push(src, pole2TopDisk)         moveDisk(d, s, pole2TopDisk)            # When top disk of pole1 < top disk of pole2     else :         push(dest, pole2TopDisk)         push(dest, pole1TopDisk)         moveDisk(s, d, pole1TopDisk)    # Function to show the movement of disks def moveDisk(fromPeg, toPeg, disk):     print ( "Move the disk" , disk, "from '" , fromPeg, "' to '" , toPeg, "'" )    # Function to implement TOH puzzle def tohIterative(num_of_disks, src, aux, dest):     s, d, a = 'S' , 'D' , 'A'        # If number of disks is even, then interchange     # destination pole and auxiliary pole     if (num_of_disks % 2 = = 0 ):         temp = d         d = a         a = temp     total_num_of_moves = int ( pow ( 2 , num_of_disks) - 1 )        # Larger disks will be pushed first     for i in range (num_of_disks, 0 , - 1 ):         push(src, i)        for i in range ( 1 , total_num_of_moves + 1 ):         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) Â
# Input: number of disks num_of_disks = 3 Â
# Create three stacks of size 'num_of_disks' # to hold the disks src = createStack(num_of_disks) dest = createStack(num_of_disks) aux = createStack(num_of_disks) Â
tohIterative(num_of_disks, src, aux, dest) Â
# This code is contributed by divyeshrabadiya07. |
C#
// C# program for iterative // Tower of Hanoi using System; Â
class GFG {     // A structure to represent a stack     public class Stack     {         public int capacity;         public int top;         public int []array;     }          // function to create a stack of given capacity.     Stack createStack( int capacity)     {         Stack stack = new Stack();         stack.capacity = capacity;         stack.top = -1;         stack.array = new int [capacity];         return stack;     }          // Stack is full when top is equal to the last index     Boolean isFull(Stack stack)     {         return (stack.top == stack.capacity - 1);     }          // Stack is empty when top is equal to -1     Boolean isEmpty(Stack stack)     {         return (stack.top == -1);     }          // Function to add an item to stack.     // It increases top by 1     void push(Stack stack, int item)     {         if (isFull(stack))             return ;         stack.array[++stack.top] = item;     }          // Function to remove an item from stack.     // It decreases top by 1     int pop(Stack stack)     {         if (isEmpty(stack))             return int .MinValue;         return stack.array[stack.top--];     }          // Function to implement legal     // movement between two poles     void moveDisksBetweenTwoPoles(Stack src, Stack dest,                                             char s, char d)     {         int pole1TopDisk = pop(src);         int pole2TopDisk = pop(dest); Â
        // When pole 1 is empty         if (pole1TopDisk == int .MinValue)         {             push(src, pole2TopDisk);             moveDisk(d, s, pole2TopDisk);         }                  // When pole2 pole is empty         else if (pole2TopDisk == int .MinValue)         {             push(dest, pole1TopDisk);             moveDisk(s, d, pole1TopDisk);         }                  // When top disk of pole1 > top disk of pole2         else if (pole1TopDisk > pole2TopDisk)         {             push(src, pole1TopDisk);             push(src, pole2TopDisk);             moveDisk(d, s, pole2TopDisk);         }                  // When top disk of pole1 < top disk of pole2         else         {             push(dest, pole2TopDisk);             push(dest, pole1TopDisk);             moveDisk(s, d, pole1TopDisk);         }     }          // Function to show the movement of disks     void moveDisk( char fromPeg, char toPeg, int disk)     {         Console.WriteLine( "Move the disk " +disk +                         " from " +fromPeg+ " to " +toPeg);     }          // Function to implement TOH puzzle     void tohIterative( int num_of_disks, Stack                 src, Stack aux, Stack dest)     {         int i, total_num_of_moves;         char s = 'S' , d = 'D' , a = 'A' ;              // If number of disks is even, then interchange         // destination pole and auxiliary pole         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);              // Larger disks will be pushed first         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);         }     }          // Driver code     public static void Main(String []args)     {                  // Input: number of disks         int num_of_disks = 3;                  GFG ob = new GFG();         Stack src, dest, aux;                  // Create three stacks of size 'num_of_disks'         // to hold the disks         src = ob.createStack(num_of_disks);         dest = ob.createStack(num_of_disks);         aux = ob.createStack(num_of_disks);                  ob.tohIterative(num_of_disks, src, aux, dest);     } } Â
// This code is Contributed by Arnab Kundu |
Javascript
<script>     // Javascript program for iterative Tower of Hanoi          // A structure to represent a stack     class Stack     {         constructor(capacity) {             this .capacity = capacity;             this .top = -1;             this .array = new Array(capacity);         }     }          // function to create a stack of given capacity.     function createStack(capacity)     {         let stack = new Stack(capacity);         return stack;     }          // Stack is full when top is equal to the last index     function isFull(stack)     {         return (stack.top == (stack.capacity - 1));     }           // Stack is empty when top is equal to -1     function isEmpty(stack)     {         return (stack.top == -1);     }           // Function to add an item to stack.     // It increases top by 1     function push(stack, item)     {         if (isFull(stack))             return ;         stack.array[++stack.top] = item;     }           // Function to remove an item from stack.     // It decreases top by 1     function pop(stack)     {         if (isEmpty(stack))             return Number.MIN_VALUE;         return stack.array[stack.top--];     }           // Function to implement legal     // movement between two poles     function moveDisksBetweenTwoPoles(src, dest, s, d)     {         let pole1TopDisk = pop(src);         let pole2TopDisk = pop(dest);           // When pole 1 is empty         if (pole1TopDisk == Number.MIN_VALUE)         {             push(src, pole2TopDisk);             moveDisk(d, s, pole2TopDisk);         }                   // When pole2 pole is empty         else if (pole2TopDisk == Number.MIN_VALUE)         {             push(dest, pole1TopDisk);             moveDisk(s, d, pole1TopDisk);         }                   // When top disk of pole1 > top disk of pole2         else if (pole1TopDisk > pole2TopDisk)         {             push(src, pole1TopDisk);             push(src, pole2TopDisk);             moveDisk(d, s, pole2TopDisk);         }                   // When top disk of pole1 < top disk of pole2         else         {             push(dest, pole2TopDisk);             push(dest, pole1TopDisk);             moveDisk(s, d, pole1TopDisk);         }     }           // Function to show the movement of disks     function moveDisk(fromPeg, toPeg, disk)     {         document.write( "Move the disk " +disk +                         " from '" +fromPeg+ "' to '" +toPeg + "'</br>" );     }           // Function to implement TOH puzzle     function tohIterative(num_of_disks, src, aux, dest)     {         let i, total_num_of_moves;         let s = 'S' , d = 'D' , a = 'A' ;               // If number of disks is even, then interchange         // destination pole and auxiliary pole         if (num_of_disks % 2 == 0)         {             let temp = d;             d = a;             a = temp;         }         total_num_of_moves = parseInt(Math.pow(2, num_of_disks) - 1, 10);               // Larger disks will be pushed first         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);         }     }          // Input: number of disks     let num_of_disks = 3; Â
    let src, dest, aux; Â
    // Create three stacks of size 'num_of_disks'     // to hold the disks     src = createStack(num_of_disks);     dest = createStack(num_of_disks);     aux = createStack(num_of_disks); Â
    tohIterative(num_of_disks, src, aux, dest);          // This code is contributed by decode2207 </script> |
Tower 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 from rod A to rod D Move disk 1 from rod S to rod D
Time Complexity: O(2á´º) 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
This article is contributed by Anand Barnwal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!