Tower of Hanoi Algorithm

The Tower of Hanoi problem consists of three rods (for example A, B, and C) and N disks initially stacked on rod A in decreasing order of diameter (smallest one is at the top). The goal is to transfer the entire stack to another rod (in this case, rod C) with the help of auxiliary rod(in this case, rod B).

Example:

Rules to be Followed During Shifting From the Source to Destination Peg

There are following three rules to be followed while solving tower of hanoi algorithm:

1. We can move only one disk at a time.
2. A disk can only be moved if it's the topmost one on a stack.
3. No disk should be placed at the top of the smaller disk which means that the disk of larger diameter cannot be placed on a disk of smaller diameter.

Tower of Hanoi using Recursion Algorithm

Utilize recursion to transfer disks from the source rod to the destination rod via a helper rod.

1. Move 'N-1' disks from the source rod(A) to the auxiliary rod(B), using the destination rod (C) as the helper.
2. Move the last disk from the source rod(A) to the destination(C) rod directly.
3. Move the 'N-1' disks from the auxiliary rod(B) to the destination rod(C), using the source rod(A) as the helper.

Explanation:

Following are the steps to solve the problem:

1. The function towerOfHanoi takes four parameters: N (the current number of disks to move), from_rod (the rod from which to move the disks), to_rod (the rod to which to move the disks), and aux_rod (the auxiliary rod that can be used as a temporary storage).
2. If there is only one disk (base case, N == 1), move it directly from from_rod to to_rod and return.
3. For N > 1, follow these steps:
   • Recursively call towerOfHanoi for N - 1 disks to move them from from_rod to aux_rod, using to_rod as the auxiliary rod.
   • Move the Nth disk (the bottom disk) from from_rod to to_rod.
   • Recursively call towerOfHanoi for N - 1 disks to move them from aux_rod to to_rod, using from_rod as the auxiliary rod.
4. The initial function call to solve the puzzle with n disks from rod A to rod C with B as an auxiliary rod would be towerOfHanoi(n, 'A', 'C', 'B').

Code Implementation

C++ Implementation of the Tower of Hanoi Using Recursion

Python Implementation of the Tower of Hanoi Using Recursion

Java Implementation of the Tower of Hanoi Using Recursion

Output:

Complexity Analysis

Time Complexity: O(2^N) i.e, For each disk, there are two possibilities. Therefore, if we have N disks, the total number of possibilities is 2 raised to the power of N. Hence, the time complexity of tower of hanoi in data structure is 2^N.

Space complexity: O(N). Auxiliary stack space used during recursion for the Tower of Hanoi algorithm.