Python Program for Tower of Hanoi

Introduction

The Tower of Hanoi is a classic problem in computer science and mathematics. It was introduced by the French mathematician Édouard Lucas in 1883. The problem involves moving a stack of disks from one rod to another under certain constraints. In this blog post, we will explore the Tower of Hanoi problem, understand the recursive algorithm to solve it, and implement a Python program. The post will also provide the logic behind the Tower of Hanoi and demonstrate the program’s output.

Tower of Hanoi Problem

The Tower of Hanoi 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. 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.

Recursive Algorithm for Tower of Hanoi

The Tower of Hanoi problem can be efficiently solved using recursion. The recursive algorithm follows these steps:

1. Base Case: If there is only one disk, move it from the source rod to the destination rod.
2. Recursive Case: If there are more than one disk, perform the following steps:
   • Move the top (n-1) disks from the source rod to an auxiliary rod.
   • Move the nth disk from the source rod to the destination rod.
   • Move the (n-1) disks from the auxiliary rod to the destination rod.

Python Program for Tower of Hanoi

Now, let’s implement the Tower of Hanoi algorithm in Python:

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

# Example Usage
num_of_disks = int(input("Enter the number of disks: "))
tower_of_hanoi(num_of_disks, 'A', 'B', 'C')

Output:

For example, if the user enters 3 as the number of disks, the output will be:

Enter the number of disks: 3
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

Conclusion

The Tower of Hanoi is an interesting problem that demonstrates the elegance and power of recursive algorithms. By understanding the problem’s recursive nature, you can efficiently solve it with a concise and clear algorithm. The Python program provided in this post offers a practical implementation of the Tower of Hanoi solution. Feel free to experiment with different numbers of disks and observe how the program performs the optimal moves to solve the problem. Happy coding!