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.
- Only one disk can be used at a time.
- 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.
- Base case: If there is only one cycle (n==1), drive directly from the source rod to the target rod.
- 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:
- Move disk 1 from rod A to rod C.
- Move disk 2 from rod A to rod B.
- Move disk 1 from rod C to rod B.
- Move disk 3 from rod A to rod C.
- Move disk 1 from rod B to rod A.
- Move disk 2 from rod B to rod C.
- 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.