Solve Tower of Hanoi Probelem in Python

Solve Tower of Hanoi Probelem in Python

Manav Narula May-31, 2021 Python

The Tower of Hanoi problem is a fundamental mathematical puzzle that is introduced to new programmers at the start for them to amplify their problem-solving quiz.

The problem is simple, involving three rods. One rod contains several disks in decreasing order, with the largest disk at the bottom and the smallest at the top. We have to transfer this from rod one to rod three using the second rod.

We have to keep certain rules in mind. We can move only one disk simultaneously and have to take the disk at the top of the rod. Also, we cannot place a larger disk on top of a smaller disk. Keeping all this in mind, we have to solve this problem and calculate the total number of moves taken to solve it.

In this tutorial, we will introduce how to solve this problem. We will use a recursive method to solve the Tower of Hanoi problem in Python.

This method will create a function that will call itself recursively based on some conditions to solve the Tower of Hanoi problem. We implement the logic for this in the following code.

def ToH(n , A, B, C):
    if n==1:
        print("Disk 1 from",A,"to",B)
        return 
    ToH(n-1, A, C, B)
    print("Disk",n,"from",A,"to",B)
    ToH(n-1, C, B, A)
          
ToH(3,'A','B','C')

Output:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

In the above example, we move three disks from Rod A to Rod B using Rod C.

As you can see, the total number of moves taken in the above example is 7. For n number of disks, the total moves taken using this method are always equal to 2^n -1.

Over time, a few other solutions have emerged to solve the Tower of Hanoi problem using stacks. Still, it is not recommended to use them because such methods are very inefficient in time taken and speed.

Author: Manav Narula
Manav Narula avatar Manav Narula avatar

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.

LinkedIn