Tower of Hanoi Solution in CPP

The Tower of Hanoi is a classic mathematical puzzle that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks stacked in ascending order of size on one rod, with the smallest disk at the top, making a conical shape resembling a tower. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the top disk from one stack and placing it onto another stack.
3. No disk may be placed on top of a smaller disk.

The minimal number of moves required to solve the Tower of Hanoi puzzle with n disks is 2n−1.

The Tower of Hanoi problem is often used to illustrate the concept of recursion in computer science because it can be solved recursively. The recursive algorithm involves breaking down the problem into smaller subproblems and solving each subproblem recursively.

Here’s a brief overview of the recursive algorithm to solve the Tower of Hanoi problem:

1. Move n−1 disks from the source rod to the auxiliary rod using the destination rod as the auxiliary.
2. Move the nth disk from the source rod to the destination rod.
3. Move the n−1 disks from the auxiliary rod to the destination rod using the source rod as the auxiliary.

This algorithm is implemented in the C++ code provided earlier. Each recursive call corresponds to one of these steps, and the base case is when there is only one disk to move.

You can get the full code On my Git hub repo https://github.com/Nagendrarana/CodingSolutions/blob/main/CPP/TowerOfhanoi.cpp

Explanation of the code –>

This C++ program implements the Tower of Hanoi problem using recursion. Let’s break down the code step by step:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

This section includes necessary header files for input/output operations and standard C++ libraries.

void towerHanoi(int n,char start, char end,char aux){

This function towerHanoi takes four parameters:

• n: Number of disks to be moved.
• start: Source peg from which the disks are moved.
• end: Destination peg to which the disks are moved.
• aux: Auxiliary peg used for the movement of disks.

    //base condition
    if(n==1){
        cout << "move disc 1 " << "from " << start << " to " << end <<endl;
        return;
    }

This is the base condition of the recursive function. If there is only one disk to move, it prints the move from the start peg to the end peg.

towerHanoi(n-1,start,aux,end);
    cout << "move disc " << n << " from " << start << " to " << end <<endl;
    towerHanoi(n-1,aux,end,start);

This is the recursive part of the function. It moves n-1 disks from the start peg to the auxiliary peg, then moves the nth disk from the start peg to the end peg, and finally moves the n-1 disks from the auxiliary peg to the end peg.

int main(){
    //Tower of hanoi
    towerHanoi(2,'A', 'B','C');
    return 0;
}

In the main() function, towerHanoi(2,'A', 'B','C'); is called with the parameters 2 for the number of disks, and 'A', 'B', 'C' representing the source, destination, and auxiliary pegs respectively. After printing the moves for Tower of Hanoi, it prints “hello” to indicate the end of the program.

Overall, the program demonstrates the Tower of Hanoi problem solution using recursion in C++.