Tower of hanoi problem solution using Python

In this tutorial, we will learn about how tower of Hanoi problem solution can be solved using Python.

So, now let’s know what actually the problem is. Here Tower of Hanoi is a common problem in the design of recursive algorithms. Here the aim is to use the third rod to move the wheel assembly from one rod to another with the help of the third rod, so we have some rules for this problem.

  1. Only one disk can be used at a time.
  2. The wheel can be mounted on a large wheel or simply on an empty rod.

Now let’s see the Python solution to the Tower of Hanoi problem, with input and output:

Python Solution

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

# Input: Number of disks
n = int(input("Enter the number of disks: "))

# Call the function to solve the problem
tower_of_hanoi(n, 'A', 'C', 'B')

How It Works

 

For the above written code, the following are the working steps in the program. So basically, there are 2 working steps involved in this solution. They are Base case, Recurring issue.

  1. Base case: If there is only one cycle (n==1), drive directly from the source rod to the target rod.
  2. Recurring issues:
  • Run the upper n-1 cycles from the source rod to the auxiliary rod, using the target rod as auxiliaries.
  • Move the nth cycle from the source rod to the target rod.
  • Run n-1 cycles from the auxiliary rod to the target rod, using the source rod as auxiliaries.

Example Input and Output

Input

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

Explanation

For n=3 disks:

  1. Move disk 1 from rod A to rod C.
  2. Move disk 2 from rod A to rod B.
  3. Move disk 1 from rod C to rod B.
  4. Move disk 3 from rod A to rod C.
  5. Move disk 1 from rod B to rod A.
  6. Move disk 2 from rod B to rod C.
  7. Move disk 1 from rod A to rod C.

The work follows an iterative approach to optimize the Tower of Hanoi problem and demonstrates the power of iteration in algorithm design.

Conclusion

The Tower of Hanoi problem is a good example of the power and beauty of repetition to solve complex algorithmic problems. Through our Python project, we demonstrated how a seemingly complex task can be broken down into smaller, simpler problems, which can be solved in an iterative manner

By understanding and practicing the Tower of Hanoi:

  • We learned how to solve problems, breaking them down into smaller ones of the same problem.
  • We have seen how clear rules (to enable one disk at a time and never put a smaller disk on top of a larger disk) can lead to efficient and elegant solutions.
  • We applied theoretical concepts to code implementation, reinforcing the importance of algorithms in design.
  • Thus, Tower of Hanoi problem can be solved using Python.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top