Lecture 72:- Tower of Hanoi Problem

The Tower of Hanoi is a classic mathematical puzzle that involves moving a stack of disks from one peg to another, using a temporary peg, while following specific rules:

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

Here's an example implementation of the Tower of Hanoi problem using recursion in Python:

pythonCopy code

def tower_of_hanoi(n, source, destination, auxiliary):    if n == 1:        print(f"Move disk 1 from {source} to {destination}")        return    tower_of_hanoi(n - 1, source, auxiliary, destination)    print(f"Move disk {n} from {source} to {destination}")    tower_of_hanoi(n - 1, auxiliary, destination, source)

Let's break down how the code works:

1. The tower_of_hanoi function takes four parameters: n (the number of disks), source (the source peg), destination (the destination peg), and auxiliary (the auxiliary peg).
2. The base case is when there is only one disk remaining (n == 1). In this case, we directly move the disk from the source peg to the destination peg.
3. In the recursive case, we break down the problem into smaller subproblems. We move n-1 disks from the source peg to the auxiliary peg using the destination peg as the temporary peg, using a recursive call to tower_of_hanoi.
4. After moving the n-1 disks, we move the remaining disk (disk n) from the source peg to the destination peg.
5. Finally, we recursively move the n-1 disks from the auxiliary peg to the destination peg using the source peg as the temporary peg.

Here's an example usage of the tower_of_hanoi function:

pythonCopy code

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

In this example, we solve the Tower of Hanoi problem with 3 disks, starting from peg 'A', moving them to peg 'C', using peg 'B' as the temporary peg. The function will print the sequence of moves to solve the problem:

cssCopy code

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

The output shows the sequence of moves required to solve the Tower of Hanoi puzzle with 3 disks.