## What is the Tower of Hanoi?

The **Tower of Hanoi **is a mathematical puzzle. It consists of **three rods** and **N** disks. The task is to move all **disks** to another **rod **following **certain rules**:

- Only one disk can be moved at a time.
- Only the uppermost disk can be moved from one stack to the top of another stack or to an empty rod.
- Larger disks cannot be placed on top of smaller disks.

## Problem Statement: Program for Tower of Hanoi Algorithm

A diagrammatic illustration of the **Tower of Hanoi:**

**Image Source – Google images**

**The result is :**

**Image Source – Google Images.**

## Recursive Approach

The idea is to use a recursive approach to solve this problem.

Let us try to solve the problem for **N = 2**.

So, one disk is moved from **rod 1** to **rod 3**. Then the second disk is moved from **rod 1 **to **rod 2** and finally, the first disk is moved again back to **rod 2**.

Similarly, the problem can be solved recursively for **N = 3**.** **Observe the below example.

The minimum number of moves to solve the Tower of Hanoi problem is **2^N – 1**, where N is the number of disks.

**Dry Run of the above illustration –**

- Move disc 1 from tower A to tower B.
- Move disc 2 from tower A to tower C.
- Move disc 1 from tower B to tower C.
- Move Disc 3 from tower A to tower B.
- Move Disc 1 from tower C to tower A.
- Move Disc 2 from tower C to tower B.
- Move Disc 1 from tower A to tower B.

**Algorithm**

- Let us consider a recursive function that takes the following argument
**N,**the number of**disks**,**to_Rod**, which indicates the rod which is moved to,**from_rod**, denoting the rod from which rod is removed, and**aux_rod**, denoting the rod which is used for transferring rods from**from_rod**to**to_rod**. - The base case is for N = 1. Move it from source to destination, i.e.
**from_rod**to**to_rod.** - Solve the problem recursively by moving disk 1, 2, 3,…, N – 1 i.e.
**from_rod**to**aux_rod**by recursively calling the function on (**N – 1**,**from_rod, aux_rod, to_rod)**. - Now, since the top
**N – 1**disks have been removed from**from_rod**, move the last disk from**from_rod**to**to_rod**. - Similarly, again remove the top
**N – 1**disk from**aux_rod**to**to_rod**and recursively call the function on**(N – 1, aux_rod, to_rod, from_rod)** - Repeat the above steps until it reaches the base case.

### C++ Code for Recursive Approach

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod<<endl; return; } towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl; towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); } solve(){ TowerOfHanoi(n, 'A', 'C', 'B'); }

### Java Code for Recursive Approach

static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { System.out.println("Move disk 1 from rod "+ from_rod+" to rod "+to_rod); return; } towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); System.out.println("Move disk "+ n + " from rod " + from_rod +" to rod " + to_rod ); towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); } solve(){ TowerOfHanoi(n, 'A', 'C', 'B') }

### Python Code for Recursive Approach

def TowerOfHanoi(n , from_rod, to_rod, aux_rod): if n == 1: print("Move disk 1 from rod",from_rod,"to rod",to_rod) return TowerOfHanoi(n-1, from_rod, aux_rod, to_rod) print("Move disk",n,"from rod",from_rod,"to rod",to_rod) TowerOfHanoi(n-1, aux_rod, to_rod, from_rod) def solve(): TowerOfHanoi(n, 'A', 'C', 'B');

**Time Complexity:** O(2^N) where N is the number of disks.**Space Complexity:** O(N), as the disks, take up the recursive stack space.

## Frequently Asked Questions

### Q.1: What are the minimum moves to solve the Tower of Hanoi problem?

**Ans:** The minimum moves required is 2^N – 1 to move all disks from Source rod A to destination rod B while following the rules.

### Q.2: What is the space complexity of the Tower of Hanoi?

Ans: The space complexity is O(N) since, for each recursion, the disks take up N – 1 recursive stack space.