Tower of Hanoi Program in Python

The Tower of Hanoi is a mathematical concept first presented in 1883 by the French mathematician Edouard Lucas. It comprises three pegs (or towers) and two or more disks (illustrated in the image below).

The disks may vary in size and are organized in a descending sequence, indicating that the largest disk occupies the bottom position, the medium-sized disk is positioned in the middle, and the smallest disk is located at the top. In this illustration, we are using three disks; nonetheless, the number of disks can fluctuate, while the total number of towers must remain at three.

Rules of the Game

The objective of the puzzle is to transfer all the disks to a different tower while maintaining the order of arrangement, meaning the largest disk must be at the bottom and the smallest on the top.

Following are the rules to be followed for Tower of Hanoi:

✅ Only one disk can be moved at a time.
✅ You can only remove the upper disk.
✅ No large disk can be placed on top of a small disk.

Presented below is a detailed, step-by-step guide to resolving a Tower of Hanoi challenge involving three disks.

Step 0: All disks are arranged on the rod in an increasing order.

Step 1: The uppermost disk will be relocated to the central tower.

Step 2: Subsequently, we will transfer the middle disk to the third tower. Consequently, there will be one disk on each rod.

Step 3: Transfer the disk from the second tower to the third tower.

Step 4: Will transfer the initial disk from tower one to tower two.

Step 5: Once more, transfer the upper disk from tower 3 to tower 1.

Step 6: Subsequently, move the disk from tower 3 and place it on the top of tower 2.

Step 7: The final action involves transferring the disk from tower 1 to the summit of tower 2.

Consequently, we have effectively moved all the disks from one tower to another while adhering to all the regulations.

In the Tower of Hanoi problem, the total moves required can be determined by the formula 2n - 1 steps, with n denoting the number of disks.

In this scenario, with a total of 3 disks, the formula mentioned earlier will yield a calculation of 2^3 - 1 = 7 steps.

Algorithm to Solve Tower of Hanoi

The Tower of Hanoi algorithm is quite straightforward once you grasp the reasoning behind moving 1 disk, then 2 disks, and finally 3 disks simultaneously. We have designated the three towers as source, target, and aux (these names are temporarily assigned to facilitate the tracking of disk movements between the various towers).

For 1 disk:

It can navigate around the towers with great ease. It is capable of being transferred from the source peg to the destination peg.

For 2 disks:

✅ Since we can only move the top disk, we will move it to the aux peg.
✅ Next, we will move the bottom disk to the target peg.
✅ The last step would be to move the smaller disk from the aux peg to the target peg.

For 3 disks:

Having grasped the reasoning behind moving one and two disks, we can readily derive the algorithm for the Tower of Hanoi involving three disks. This will be addressed in two segments. The first segment will focus on the bottom disk (the largest disk, or nth), while the second segment will handle the remaining disks (n-1).

The objective is to transfer disk n (the largest disk) from the source to the target while stacking all other (n-1) disks on top of it. This process can be visualized as being applied recursively to the entire collection of disks.

Following are the steps:

✅ Create a towerofhanoi recursive function and pass two arguments: the number of disks n and the name of the rods such as source, aux, and target .
✅ We can define the base case when the number of disks is 1. In this case, simply move the one disk from the source to target and return.
✅ Now, move remaining n-1 disks from source to auxiliary using the target as the auxiliary .
✅ After that, the remaining 1 disk move on the source to target .
✅ Move the n-1 disks on the auxiliary to the target using the source as the auxiliary.

Python Program to implement Tower of Hanoi

The subsequent illustration demonstrates the execution of the Tower of Hanoi Puzzle utilizing the Python programming language:

Example


# Creating a recursive function

def tower_of_hanoi(disks, source, auxiliary, target):

    if(disks == 1):

        print('Move disk 1 from rod {} to rod {}.'.format(source, target))

        return

    # function call itself

    tower_of_hanoi(disks - 1, source, target, auxiliary)

    print('Move disk {} from rod {} to rod {}.'.format(disks, source, target))

    tower_of_hanoi(disks - 1, auxiliary, source, target)

disks = int(input('Enter the number of disks: '))

# We are referring source as A, auxiliary as B, and target as C

tower_of_hanoi(disks, 'A', 'B', 'C')  # Calling the function

Output:

Output


Enter the number of disks: 3

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.

Explanation:

In this illustration, we have addressed the Tower of Hanoi challenge through a recursive function. This function transfers a designated quantity of disks from the source rod 'A' to the destination rod 'C', utilizing rod 'B' as a helper. It guarantees that only a single disk is moved at any given moment while preserving the sequence.

Conclusion

The Tower of Hanoi problem serves as an excellent illustration of how recursion can be applied in programming. In this guide, we have discussed all the key aspects of the puzzle, its straightforward but rigid rules, and demonstrated the recursive solution through Python. By deconstructing the issue into simpler subproblems, we successfully tackled the entire puzzle incrementally.

Learning is an endless journey. Thus, do not halt your progress; you can experiment with the logic of this program using a greater number of disks and note the corresponding increase in the number of steps required.

Tower of Hanoi Puzzle using Python FAQs

1. What is the Tower of Hanoi puzzle?

The Tower of Hanoi is a classic mathematical puzzle that involves moving a set of disks from one rod to another, following three rules:

✅ Only one disk can be moved at a time.
✅ A disk can only be placed on top of a larger disk or an empty rod.
✅ Only the top disk of any rod can be moved.

2. How does recursion apply in Tower of Hanoi?

Recursion solves Tower of Hanoi by breaking the problem into smaller sub-problems:

✅ Move n-1 disks to the auxiliary rod.
✅ Move the largest disk to the target rod.
✅ Move n-1 disks from auxiliary to target rod.

3. What is the base case in the recursive function?

The fundamental case occurs when n equals 1. In this scenario, you merely transfer the single disk from the source rod to the target rod.

4. How many moves are required to solve Tower of Hanoi with n disks?

The minimum number of moves required is 2ⁿ - 1 .

5. What are the typical use cases of Tower of Hanoi in learning?

✅ Understanding recursion
✅ Base and recursive case analysis
✅ Algorithmic thinking
✅ Stack-based problems