Advanced C++ Programming and Algorithms

# Implement Tower of Hanoi using 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:

- A single disc can only be transferred at once.
- 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.
- 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.

**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.