Puzzles are fun to solve, aren’t they? Have you ever heard of the Tower of Hanoi puzzle? The Tower of Hanoi is a mathematical puzzle == also known as the Lucas Tower or the Tower of Brahma. It’s a simple game where you have three rods and some disks of different sizes, and you have to move those disks from one rod to the other. However, there are specific rules that you have to keep in mind.

Rules of the Tower of Hanoi problem

There are three rules that you must follow to solve the problem.

You can only move one disk at a time.
You cannot place the larger disk on top of the smaller disk.
You can only move the uppermost disk in a rod.

An example of the Tower of Hanoi Problem

Let’s see the example given below to understand the problem better. There are three rods A. B, and C, and three disks. You have to move all the disks from Rod A to Rod C.

How to solve the tower of hanoi problem using python?

Start with moving the smallest disk from Rod A to Rod C. Then, you move the second disk from Rod A to Rod B. Note that you cannot move the bigger disk on top of the smaller disk; thus, you cannot move the second disk to Rod C.

You can move the smaller disk on top of the bigger disk. Thus in step 4, you move the smallest disk on top of the second disk. Now, since rod C is empty, you can move the biggest disk to rod C, as shown in step 5.

You can only move one disk at a time; therefore, you have to move the smallest disk to rod A and then move the bigger disk from rod B to rod C, as shown in steps 6 and 7. Lastly, you can move the smallest disk back to rod C. You can see in step 8 all of the disk from rod A has been moved to rod C.

As we can see in the example above, eight moves were required to move three disks. Therefore, to move the ‘n’ disk, the number of moves required is n^2 -1.

Python code to solve the Tower of Hanoi problem

You can solve the Tower of Brahma using a recursive function. Let’s see the Python code.

import math

# the variable disk has the number of disk
disk = int(input("Number of disks = "))

#the recursive function to solve the problem
def TowerOfHanoi(disk, source, destination, auxiliary):
    if disk == 1:
        print("Moving disk 1 from ",source," to ",destination)
        return
    TowerOfHanoi(disk-1,source,auxiliary,destination)
    print("Moving disk ",disk," from ",source," to ",destination)
    TowerOfHanoi(disk-1,auxiliary,destination,source)
    

#calculating the total number of moves required.
moves = int(math.pow(disk, 2) - 1)
print("\nTotal number of moves required to move ",disk," disks are: ",moves,"\n")

# calling the recursive function for three rods: A,B,C where the Rod A is the source and Rod C is the destination
TowerOfHanoi(disk, 'Rod A','Rod C','Rod B')

First of all, you take the input from the user on how many disks they want to move. Then, you declare the recursive method TowerOfHanoi(). Moving further, you calculate the number of moves required to move the disks from one rod to the other. In the end, you call out the recursive method to move the disks.

The image below shows what the output of the above code will look like.