Algotree > Algorithms > Recursive Algorithms 🌀 🌀 🌀 > Algorithm for Solving Tower Of Hanoi

Algorithm for Solving Tower Of Hanoi

Tower of Hanoi is a mathematical puzzle consisting of 3 pegs / towers [ A, B, C ] and some disks of varying diameter.

Beginning : The puzzle starts with all the N disks stacked on top of each other in decreasing order of diameter on peg A.
i.e the bottom most disk is biggest in diameter and as we go to the top the diameter of the stacked disks decreases.
Objective : The puzzle would be solved if the entire stack of disks on peg A is moved to peg B using some simple rules.
Rules
- At a time only one disk can be moved and placed on other peg.
- A bigger disk cannot be placed on a peg containing a smaller disk.

Below is the example of solving the Tower Of Hanoi puzzle with 3 disks. Tower_Of_Hanoi

It can be mathematically proved that the minumum number of moves required to move N disks is 2 ^N - 1.

If N = 1, we could just moved the disk from peg A to peg C without using the auxiliary peg. i.e 2 ¹ - 1 = 1 move.
If N = 2, we could have 2 ² - 1 = 3 moves
1: Move the smaller disk at the top from peg A to peg B.
2: Move the bigger disk at the bottom from A to peg C.
3: Move the smaller disk from peg B to peg C.
If N = 3, we could have 2 ³ - 1 = 7 moves

Idea : The idea behind recursion is to move the top ( N - 1 ) disks from source peg to auxiliary peg. The bottom-most disk that is now left on the source peg is then moved to the desitnation peg. Thus the rules of the puzzle are obeyed and we get the below recursive algorithm for solving the puzzle of Tower Of Hanoi.

Algorithm : MoveDisks ( Integer disks, String source_peg, String using_peg, String dest_peg )

1.    If there is just 1 disk then
          Move disk 1 from source_peg to dest_peg. ( w/o using any auxiliary peg )
2.    Else
3.        First move the top ( N - 1 ) disks from source_peg to aux_peg using dest_peg ( which is used as an auxiliary peg ).
           i.e MoveDisks ( N - 1, source_peg, dest_peg, aux_peg ).
4.        Move the bottom-most disk N left on the source_peg to dest_peg.
5.        Now that we have N - 1 disks on aux_peg, we could move them to dest_peg using source_peg ( as auxiliary peg )
           i.e MoveDisks ( N - 1, aux_peg, source_peg, dest_peg ).

def MoveDisks ( disks, src_peg, aux_peg, dest_peg ) : 
    if ( disks == 1 ) : 
        print("Move disk 1 from " + src_peg + " to " + dest_peg)
    else :
        # First move the top N-1 disks to aux_peg using dest_peg ( as auxiliary peg )
        MoveDisks ( disks-1, src_peg, dest_peg, aux_peg )

        # Move the bottom-most disk to the destination peg.
        print ( "Move disk " + str(disks) + " from " + src_peg + " to " + dest_peg )

        # We have N-1 disks ( moved in previous step ) on aux_peg. So move these disks from aux_peg 
        # to dest_peg using src_peg ( as auxiliary peg ) by recursively calling MoveDisks
        MoveDisks ( disks-1, aux_peg, src_peg, dest_peg )
 
def main() :

    disks = 3 
    MoveDisks(disks, "A", "B", "C")

if __name__ == "__main__":
    main()

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

#include<iostream>
#include<string>
using namespace std;

void MoveDisks ( int disks, string src_peg, string aux_peg, string dest_peg ) { 
    if ( disks == 1 ) { 
        cout << "Move disk 1 from " << src_peg << " to " <<  dest_peg << endl;
    } else { 
        // First move the top N-1 disks to aux_peg using dest_peg ( as auxiliary peg )
        MoveDisks ( disks-1, src_peg, dest_peg, aux_peg );

        // Move the bottom-most disk to the destination peg.
        cout << "Move disk " << disks << " from " << src_peg << " to " << dest_peg << endl;

        // We have N-1 disks ( moved in previous step ) on aux_peg. So move these disks from aux_peg 
        // to dest_peg using src_peg ( as auxiliary peg ) by recursively calling MoveDisks
        MoveDisks ( disks-1, aux_peg, src_peg, dest_peg );
    }   
}
 
int main() {

    int disks = 3;
    MoveDisks(disks, "A", "B", "C");
    return 0;
}

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

class TowerOfHanoi {

    void MoveDisks ( int disks, String src_peg, String aux_peg, String dest_peg ) { 
        if ( disks == 1 ) { 
            System.out.println("Move disk 1 from " + src_peg + " to " +  dest_peg);
        } else { 
            // First move the top N-1 disks to aux_peg using dest_peg ( as auxiliary peg )
            MoveDisks ( disks-1, src_peg, dest_peg, aux_peg );
    
            // Move the bottom-most disk to the destination peg.
            System.out.println("Move disk " + disks + " from " + src_peg + " to " + dest_peg);
    
            // We have N-1 disks ( moved in previous step ) on aux_peg. So move these disks from aux_peg 
            // to dest_peg using src_peg ( as auxiliary peg ) by recursively calling MoveDisks
            MoveDisks ( disks-1, aux_peg, src_peg, dest_peg );
        }
    }   
    
    public static void main (String[] args) {
        TowerOfHanoi t = new TowerOfHanoi();
        int disks = 3;
        t.MoveDisks(disks, "A", "B", "C");
    }
}

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C