Tower of Hanoi Puzzle Using Python

28 Jun 2025 | 6 min read

In this tutorial, we will implement the famous Tower of Hanoi puzzle using the Python program. We will solve this problem by using recursion function.

To know more about the Recursion function in Python, refer to the page python-factorial-number-using-recursion.

Tower of Hanoi

The Tower of Hanoi is a mathematical function introduced in 1883 by the French mathematician Edouard Lucas. It consists of three towers (pegs) and two or more disks (as shown in the image below).

The disks can be of different sizes, and they are arranged in a decreasing order, which means the largest disk is placed at the bottom, the smaller one in the middle and the smallest of the three at the top. In this example, we have taken three disks, but the disk count can increase or decrease; however, the tower count has to be 3.

Rules of the Game

The goal of the puzzle is to move all the disks to another tower without disturbing the sequence of arrangement i.e., the largest disk stacked at the bottom and the smallest one on 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.

Given below is the step-to-step illustration to solve a Tower of Hanoi puzzle with three disks.

Step 0: All the disks are placed on the rod in an ascending order.

Step 1: We will move the top disk to the middle tower.

Step 2: Next, we will move the middle disk to the third tower. As a result, we will have one disks in each rod.

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

Step 4: Will move the first disk form tower one to tower two.

Step 5: Again will move the top disk from tower 3 to tower 1.

Step 6: Next shift the disk from tower 3 to the top of tower 2.

Step 7: The last step would be to move the disk from tower 1 to the top of tower 2.

As a result, we have successfully shifted all the disks from one tower to another abiding all the rules.

In the Tower of Hanoi puzzle, the number of moves can be calculated using 2n - 1 steps (where n represents the disks).

In our case, since we have 3 disks, the above formula will be calculated as 23 - 1 = 7 steps.

Algorithm to Solve Tower of Hanoi

The algorithm for Tower of Hanoi is very easy if you initially understand the logic to 1 disks, 2 disks and at last move 3 disks at a time. We have named the three towers as source, target and aux (these names are temporarily given to track the disk movement among different towers easily).

For 1 disk:

It can move around the towers very easily. It can be moved from the source 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:

Since we already understood the logic for moving one disk and two disks, we can easily conclude the algorithm for the Tower of Hanoi with three disks. We will conclude it in two parts. The bottom disk (nth or the largest disk) would be the first part, and all other disks (n-1) would be solved in the second part.

The goal is to shift disk n (the largest disk) from source to target and resemble all other (n-1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.

Following are the steps:

Create a tower_of_hanoirecursive 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 sourceto target and return.
Now, move remaining n-1 disks from sourceto auxiliary using the target as the auxiliary.
Then, the remaining 1 disk move on the sourceto 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 following is the implementation of Tower of Hanoi Puzzle using Python programming language:

Example

Execute Now

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 example, we have solve the Tower of Hanoi problem using a recursive function. It moves a specified number of disks from the source rod 'A' to the target rod 'C', using rod 'B' as an auxiliary. The function ensures only one disk moves at a time and maintains the order.

Conclusion

The Tower of Hanoi puzzle is a perfect example to show how recursion can be used in programming. In this tutorial, we have covered all the important details of the puzzle, its simple yet strict rules, and implemented the recursive solution using Python. By breaking down the problem into smaller subproblems, we were able to solve the entire puzzle step-by-step.

There is no limit to learning. Therefore, don't stop here, you can try the logic of this program of higher number disks and observe how the number of steps increases with it.