How to Solve Tower of Hanoi Probelem in Python

1. Understanding the Tower of Hanoi Problem
2. Recursive Solution
3. Iterative Solution
4. Conclusion
5. FAQ

The Tower of Hanoi is a classic problem that has fascinated mathematicians and programmers alike for decades. It involves moving a stack of disks from one peg to another, following specific rules. If you’re looking to understand how to solve the Tower of Hanoi problem using Python, you’re in the right place.

This tutorial will guide you through the steps and provide you with clear code examples to illustrate the solution. By the end of this article, you’ll not only grasp the logic behind the Tower of Hanoi but also be able to implement it efficiently in Python. Let’s dive in!

Understanding the Tower of Hanoi Problem

Before we jump into coding, let’s clarify the problem. The Tower of Hanoi consists of three pegs and a number of disks of different sizes that can slide onto any peg. The challenge is to move the entire stack from one peg to another, adhering to these 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 peg.
3. No larger disk may be placed on top of a smaller disk.

The objective is to move all disks from the source peg to the destination peg using the auxiliary peg as needed. Now, let’s explore how to implement this in Python.

Recursive Solution

The recursive approach is the most straightforward way to solve the Tower of Hanoi problem. This method leverages the power of recursion, breaking down the problem into smaller sub-problems. Here’s how it works:

1. Move the top n-1 disks from the source peg to the auxiliary peg.
2. Move the nth disk (largest) directly to the destination peg.
3. Finally, move the n-1 disks from the auxiliary peg to the destination peg.

Here’s a simple implementation in Python:

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)

# Example usage
n = 3
tower_of_hanoi(n, 'A', 'C', 'B')

Output:

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

In this code, we define a function tower_of_hanoi that takes four parameters: the number of disks (n), the source peg, the destination peg, and the auxiliary peg. The base case for the recursion is when there’s only one disk to move, which we handle directly. For more than one disk, we make recursive calls to move the smaller disks around before moving the largest disk. This elegant solution is not only efficient but also easy to understand.

Iterative Solution

While recursion is a natural fit for the Tower of Hanoi problem, an iterative solution can also be implemented. This method uses a stack data structure to simulate the recursive calls. The iterative approach may be less intuitive but can be beneficial in certain scenarios, especially when dealing with a large number of disks.

Here’s how you can implement the iterative solution in Python:

def tower_of_hanoi_iterative(n):
    total_moves = 2 ** n - 1
    source, destination, auxiliary = 'A', 'C', 'B'
    
    if n % 2 == 0:
        destination, auxiliary = auxiliary, destination

    for i in range(1, total_moves + 1):
        if i % 3 == 1:
            print(f"Move disk {((i - 1) % n) + 1} from {source} to {destination}")
        elif i % 3 == 2:
            print(f"Move disk {((i - 1) % n) + 1} from {source} to {auxiliary}")
        else:
            print(f"Move disk {((i - 1) % n) + 1} from {auxiliary} to {destination}")

# Example usage
n = 3
tower_of_hanoi_iterative(n)

Output:

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

In this iterative version, we first calculate the total number of moves required, which is 2^n - 1. Depending on whether the number of disks is odd or even, we determine the order of moves. The loop then simulates the moves based on the current iteration, ensuring that the rules of the Tower of Hanoi are followed. This approach can help to avoid deep recursion issues and is often easier to debug.

Conclusion

In this tutorial, we explored two methods to solve the Tower of Hanoi problem using Python: the recursive and iterative approaches. Both methods have their unique advantages, and understanding them can enhance your problem-solving skills in programming. Whether you choose to implement the recursive solution for its clarity or the iterative one for its efficiency, you now have the tools to tackle this classic problem. Happy coding!

FAQ

1. What is the Tower of Hanoi problem?
   The Tower of Hanoi is a mathematical puzzle that involves moving a stack of disks from one peg to another, following specific rules.

2. Can the Tower of Hanoi problem be solved iteratively?
   Yes, the Tower of Hanoi problem can be solved using an iterative approach, which simulates the recursive process using loops.

3. How many moves are required to solve the Tower of Hanoi problem?
   The minimum number of moves required to solve the Tower of Hanoi problem with n disks is 2^n - 1.

4. Is recursion the only way to solve the Tower of Hanoi problem?
   No, while recursion is a common method, the Tower of Hanoi problem can also be solved iteratively.

5. What are the rules for moving disks in the Tower of Hanoi?
   Only one disk can be moved at a time, no larger disk may be placed on top of a smaller disk, and disks can only be moved between pegs.