Explain Tower of Hanoi with all necessary steps by using Stack and Recursion.

Tower of Hanoi

The Tower of Hanoi is a 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 in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

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

Mathematical Analysis

The puzzle can be solved using a recursive algorithm. Let's define the following function:

def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
"""
Moves n disks from from_rod to to_rod using aux_rod as an auxiliary rod.
"""

# Base case: no disks to move
if n == 0:
    return

# Recursive case: move n-1 disks from from_rod to aux_rod
tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)

# Move the nth disk from from_rod to to_rod
print("Move disk", n, "from", from_rod, "to", to_rod)

# Recursive case: move n-1 disks from aux_rod to to_rod
tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)

This function works by recursively dividing the problem into smaller subproblems. In each recursive call, we move n-1 disks from one rod to another, using the third rod as an auxiliary rod. This reduces the problem to one of moving a single disk, which is the base case of the recursion.

The following is an example of how the algorithm would solve the puzzle for n = 3:

tower_of_hanoi(3, 'A', 'B', 'C')

# Move disk 1 from A to C
print("Move disk", 1, "from", 'A', "to", 'C')

# Move disk 2 from A to B
print("Move disk", 2, "from", 'A', "to", 'B')

# Move disk 1 from C to B
print("Move disk", 1, "from", 'C', "to", 'B')

# Move disk 3 from A to C
print("Move disk", 3, "from", 'A', "to", 'C')

# Move disk 1 from B to A
print("Move disk", 1, "from", 'B', "to", 'A')

# Move disk 2 from B to C
print("Move disk", 2, "from", 'B', "to", 'C')

# Move disk 1 from A to C
print("Move disk", 1, "from", 'A', "to", 'C')

This algorithm will solve the puzzle for any number of disks n. The number of moves required to solve the puzzle is 2^n - 1.