Problem Statement: “The Tower of Hanoi, is a mathematical problem which consists of three rods and multiple disks. Initially, all the disks are placed on one rod, one over the other in ascending order of size similar to a cone-shaped tower.”

The objective of this problem is to move the stack of disks from the initial rod to another rod, following these rules:

1. Move one disk at a time.
2. No disk can be placed on top of smaller disk.
3. Only the top disk may be moved.

Examples:

Example 1:
Input: N = 3, 
Output: 
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
Explanation: Moving disks from one rod to another using an auxiliary rod takes these steps.

Example 2:
Input: N = 4
Output:
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Explanation: Moving disks from one rod to another using an auxiliary rod takes these steps.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

This problem can be solved using recursion.

Recursion problems consist of the base cases, recursion calls where we don’t have to worry about the result and small a calculation. While making recursion calls we just have to assume that we will get the result.

A similar way this problem can be solved:

On the first recursion, call move n-1 disks from source rod to auxiliary using destination rod. This is a recursion call that goes till n becomes zero. We just have to assume that this will put n-1 disks into the auxiliary rod.

Here we will do some small calculations that are put the remaining disk from the source rod to the destination rod since we are left with only one disk.

Now make a recursion call that will move n-1 disks from auxiliary rod to destination rod using source rod.

In the base case when n becomes zero we will simply return.

Given :

Step 1:

Step 2:

Step 3:

Code:

#include <bits/stdc++.h>

using namespace std;

void towerOfHanoi(int n, char source,
 char aux, char dest) {
  if (n == 0) {
    return;
  }
  towerOfHanoi(n - 1, source, dest, aux);
  cout << "Move disk " << n << " from rod " << source <<
 " to rod " << 
  dest << endl;
  towerOfHanoi(n - 1, aux, source, dest);
}

int main() {
  int n = 4; // Number of disks
  towerOfHanoi(n, 'A', 'B', 'C'); // A, B and C are names of rods
  return 0;
}

import java.util.*;
import java.io.*;
import java.math.*;
class TUF {
  static void towerOfHanoi(int n, char source,char aux, char dest) {
    if (n == 0) {
      return;
    }
    towerOfHanoi(n - 1, source, dest, aux);
    System.out.println("Move disk " + n + " from rod " +source + " to rod 
    " + dest);
    towerOfHanoi(n - 1, aux, source, dest);
  }

  public static void main(String args[]) {
    int n = 4; // Number of disks
    towerOfHanoi(n, 'A', 'B', 'C'); // A, B and C are names of rods
  }
}   

Special thanks to Rushikesh Adhav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article