Tower of Hanoi Algorithm

The Tower of Hanoi is a classic mathematical puzzle involving three rods (A, B, and C) and n disks of different sizes. Initially, all disks are stacked on rod A in decreasing order of diameter - the largest disk at the bottom and the smallest at the top.
Goal is to move the entire stack to another rod (rod C) while following these rules:

• Move only one disk at a time.
• At each step, you can take the top disk from any rod and place it on another rod.
• A disk can only be moved if it is the topmost disk of a rod.
• No larger disk may be placed on top of a smaller disk.

Examples:

Input: n = 3
Output:
Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C

Input: n = 4
Output:
Disk 1 moved from A to B
Disk 2 moved from A to C
Disk 1 moved from B to C
Disk 3 moved from A to B
Disk 1 moved from C to A
Disk 2 moved from C to B
Disk 1 moved from A to B
Disk 4 moved from A to C
Disk 1 moved from B to C
Disk 2 moved from B to A
Disk 1 moved from C to A
Disk 3 moved from B to C
Disk 1 moved from A to B
Disk 2 moved from A to C
Disk 1 moved from B to C

Illustrations:

[Approach] Tower of Hanoi using Recursion

 The idea is to use the helper node to reach the destination using recursion. Below is the pattern for this problem:

• Shift 'n-1' disks from 'A' to 'B', using C.
• Shift last disk from 'A' to 'C'.
• Shift 'n-1' disks from 'B' to 'C', using A.

Follow the steps below to solve the problem:

• Create a function towerOfHanoi where pass the n (current number of disk), fromRod, toRod, auxRod.
• Make a function call for n - 1 th disk.
• Then print the current the disk along with from_rod and to_rod
• Again make a function call for n - 1 th disk.

#include <iostream>
using namespace std;

void towerOfHanoi(int n, char fromRod, char toRod,
                  char auxRod){
    if (n == 0) {
        return;
    }
    towerOfHanoi(n - 1, fromRod, auxRod, toRod);
    cout << "Disk " << n << " moved from " << fromRod
         << " to " << toRod << endl;
    towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

int main(){
    int n = 3;

    // A, B and C are names of rods
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

#include <stdio.h>

void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
    if (n == 0) {
        return;
    }
    towerOfHanoi(n - 1, fromRod, auxRod, toRod);
    printf("Disk %d moved from %c to %c\n", n, fromRod, toRod);
    towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

int main() {
    int n = 3;

    // A, B and C are names of rods
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

class GFG {
    static void towerOfHanoi(int n, char fromRod,
                             char toRod, char auxRod){
        if (n == 0) {
            return;
        }
        towerOfHanoi(n - 1, fromRod, auxRod, toRod);
        System.out.println("Disk " + n + " moved from "
                           + fromRod + " to "
                           + toRod);
        towerOfHanoi(n - 1, auxRod, toRod, fromRod);
    }
    public static void main(String args[]){
        int n = 3;
        
        // A, B and C are names of rods
        towerOfHanoi(n, 'A', 'C', 'B');
    }
}

def TowerOfHanoi(n, fromRod, toRod, auxRod):
    if n == 0:
        return
    TowerOfHanoi(n-1, fromRod, auxRod, toRod)
    print("Disk", n, " moved from ", fromRod, " to ", toRod)
    TowerOfHanoi(n-1, auxRod, toRod, fromRod)

if __name__ == "__main__":
    n = 3
    
    # A, C, B are the name of rods
    TowerOfHanoi(n, 'A', 'C', 'B')

using System;
class GFG {
    static void towerOfHanoi(int n, char fromRod,
                             char toRod, char auxRod){
        if (n == 0) {
            return;
        }
        towerOfHanoi(n - 1, fromRod, auxRod, toRod);
        Console.WriteLine("Disk " + n + " moved from "
                          + fromRod + " to " + toRod);
        towerOfHanoi(n - 1, auxRod, toRod, fromRod);
    }
    public static void Main(String[] args){
        int n = 3;

        // A, B and C are names of rods
        towerOfHanoi(n, 'A', 'C', 'B');
    }
}

function towerOfHanoi(n, fromRod,  toRod,  auxRod){
        if (n == 0){
            return;
        }
        towerOfHanoi(n - 1, fromRod, auxRod, toRod);
        console.log("Disk " + n + " moved from " + fromRod +
        " to " + toRod);
        towerOfHanoi(n - 1, auxRod, toRod, fromRod);
    }

    // Driver code
    var n = 3;
    
    // A, B and C are names of rods
    towerOfHanoi(n, 'A', 'C', 'B');

Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C

Time complexity: O(2ⁿ), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(n times) is 2ⁿ
Auxiliary Space: O(n), Function call stack space

Related Articles 

• Iterative solution to TOH puzzle
• Quiz on Recursion