Tower of Hanoi Puzzle Using Python

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.

If you aren’t familiar with the Recursion function concepts, visit our Python recursive function tutorial (https://tutoraspire.com/python-factorial-number-using-recursion).

What is the Tower of Hanoi?

In 1883, the Tower of Hanoi mathematical puzzle was invented by the French mathematician Edouard Lucas. The inspiration came from a legend that states – In Ancient Hindu temple, this puzzle was presented to the young priest. The puzzle is, there are three poles, and 64 disks, and each disk is smaller than the other. To solve this problem, move all 64 disks from one of the three poles to another pole without violating the essential constraints.

The disks can be moved one disk at a time and they should place a smaller disk top of a larger one.

Other folktale states, when they would solve this puzzle, the temple would smash into dust, and the world would end. But it would take a lot of time because to solve this problem 2⁶⁴ – 1 moves are necessary i.e., 18,446,744,073,709,551,615 per second that is equal to 5, 84,942,417,355 years according to the rules.

Rules of the game

The rules of “Tower of Hanoi” are quite simple, but the solution is slightly hard. There are three rods. The disks are stacked in the descending order; the largest disk stacked at the bottom and the smallest one on top.

The task is to transfer the disks from one source rod to another target rod.

The following rule must not be violated

• Only one disk can be moved at a time.
• The most upper disk from one of the rod can be stimulated in move.
• The smaller disk cannot be placed at the lower of the largest disk.

The number of moves can be calculated as 2ⁿ – 1.

Solution:

At the beginning of this tutorial, we have mentioned that we will use the recursive function to find the solution.

Suppose we have three disks on the first rod; we need total 7 moves from the above formula. The most left rod is called SOURCE, and the rightmost rod is called TARGET. The middle rod is referred to as an AUX.

The AUX is needed to deposit disks temporarily.

Problem Approach

1. Create a tower_of_hanoi recursive function and pass two arguments: the number of disks n and the name of the rods such as source, aux, and target.
2. 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.
3. Now, move remaining n-1 disks from source to auxiliary using the target as the auxiliary.
4. Then, the remaining 1 disk move on the source to target.
5. Move the n-1 disks on the auxiliary to the target using the source as the auxiliary.

Python Program/ Source Code

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.  

Case – 2:

According to the formula, the moves can be happened 2ⁿ – 1, so n = 3 took 7 moves and, n = 2 took 3 moves.