Advanced C++ Programming and Algorithms

Implement Tower of Hanoi using C++

Board Infinity
Board Infinity
Implement Tower of Hanoi using C++

    OOPs (Object Oriented Programming) in C++

    A Quick Guide to Encapsulation in C++

    OOPs Abstraction in C++

    OOPS Polymorphism with C++

    Multiple Inheritance in C++

    Virtual Base Class in C++

    How to Perform Insertion Sort in C++?

    Counting Sort Algorithm: Using C++

    Bucket Sort Algorithm with C++

    Implementing Binary Search in C++

    Print all Permutations of given String: using C++

    Sliding Window Problem – C++ Implementation

    Implement Tower of Hanoi using C++

    Rabin Karp Algorithm: C++ Implementation

    Job Sequencing Problem with C++

    Biconnected Graph Algorithm with C++

    Hamiltonian Path Algorithm with C++

Introduction

In this blog, we are going to study an interesting algorithm problem known as Tower of Hanoi. French mathematician Edouard Lucas created the mathematical puzzle known as "The Tower of Hanoi" in 1883. Source (A), Auxiliary (B), and Destination are the three pegs (C). The discs on Peg A are arranged in a tower-like configuration, with the largest disc at the base and the smallest disc at the top. The goal is to move the entire disc tower from peg A to peg C while maintaining the discs' original order.

The following rules are set:

  1. A single disc can only be transferred at once.
  2. A disc can only be moved if it is the uppermost disc of the peg. Each move involves taking the upper disc from one peg and placing it on top of another peg.
  3. Never during the transfer is a larger disc put on a smaller disc.

Approach

Applying recursive functions is required for the puzzle's solution. The following is an outline of a basic recursive method for solving the problem with N discs:

  • Top N-1 discs should be moved from peg A to peg B. (using C as an auxiliary peg)
  • Change the bottom disk's peg from A to C.
  • Move the N-1 discs over to Peg C from Peg B. (A will now be the auxiliary peg)

For the sake of simplicity, let us assume that N=3 for the problem statement, now the image below depicts the flow of the 3 discs as per the set rules.

Code

Let us look at the C++ implementation of this problem.

#include<iostream>
using namespace std;

void TOH(int n,char Sour, char Aux,char Des)
{
if(n==1)
 {
 cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
 return;
 }
TOH(n-1,Sour,Des,Aux);
 cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
 TOH(n-1,Aux,Sour,Des);
}

//main program
int main()
{
int n;
cout<<"Enter no. of disks:";
cin>>n;
 //calling the TOH
TOH(n,'A','B','C');
return 0;
}

Enter no. of disks:3

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


write your code here: Coding Playground

Complexity Analysis

Time complexity: O(2N), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2N

Auxiliary Space: O(N), Function call stack space.