Tower of Hanoi in Python

Published in

Geek Culture

13 min readMar 17, 2022

What is the Tower of Hanoi?

The Tower of Hanoi is the problem in which there are 3 towers, let’s mark it with the names Tower A, Tower B, and Tower C. And in Tower A, we have n number of disks. And the task is to move all disks from Tower A to Tower C using Tower B.

Origin of the Problem-

This problem was created by French mathematician Édouard Lucas in the 19th century. This problem was related to Hindu Mythology. And this is also called the Tower of Brahmas or Lucas Tower.

This problem is believed to be unsolvable. Because there is a story behind this. And that is related to the priests of the temple. It is being said that in Kashi Vishwanath Temple in India, there is a stack of 64 golden disks that are kept sequentially on top of another. And priests are trying to rearrange that disk on another tower from many years ago. They used to believe that once all 64 disks are successfully moved then the world is going to end. And the other version of the story is about the place (Hanoi) in Vietnam. The golden plate belongs there.

This mathematical puzzle is supposed to be unsolvable. But using the help of recursion it becomes very easy to solve.

What is Recursion? In terms of programming, A recursion is a function that calls itself. There is a base case in the recursion that helps to terminate the recursion. If the base case is not present then it will never terminate.

Rules for Solving the Tower of Hanoi Problem —

In every step, only one disk is allowed to move.
No Disk should overlay its smaller disk. This means if the disk with size 2 then it can’t be put on disk with size 1, but it can be put on any other disk that is larger with that disk.

So these 2 conditions must have to be applied for moving these disks from Tower A to Tower C. And with only 2 towers we cannot move the disk. So we have taken an auxiliary tower (Tower B) to achieve that.

So the extra condition that also needs to be satisfied is that we have to use Tower B to keep the disk on that for a temporary basis because we can’t put the disk outside the tower.

Problem Statement:

How can we solve this problem using the help of Recursion? For understanding the solution better. Let’s understand the steps we need to follow when we have only 1 disk. Because that will be like a base case for our solution.

So for only 1 disk to move, we simply moved that 1 disk, from source to destination. Then the algorithm is like — Move disk from source to destination using the auxiliary tower.
Although we are not using that auxiliary tower, consider that.

Then for 2 disks, the steps should be like -

So, the algorithm for the moving 2 disks will be -

TOH( A, B, C, 2)

TOH( A, B, C, 1)
Movie disk from A to C
TOH( B, A, C, 1)

Then using this approach, Can we solve this with any number of disks? So let’s take an example to solve it with the help of 4 disks.
If we consider the tower of 4 disks then we can judge that to move these 4 disks from source tower to destination tower we need to follow some steps -

We have to move 3 disks out of 4 from the source tower (Tower A) to the auxiliary tower (Tower B).

Then Move the 4th disk from the source tower (Tower A) to the destination tower (Tower C).

And at last, move the 3 disks from the auxiliary tower (Tower B) to the destination tower (Tower C).

Problem Solved, With just 3 simple steps to have concluded the solution of the problem. But the condition 1 that is stated for solving the problem is that we need to move only 1 disk at a time. But here we are moving 3 disks at a time (Move 3 Disks from A to B and Move 3 disks from B to C). How do we solve this problem?

So, why can’t we do one thing that at the very first step, instead of moving 3 disks, we can ask someone to move 1 disk from source to destination, then that person ask someone else for the same, and then we proceed accordingly?
Yes, that’s the recursive function that we have to make, and that will solve our problem.

Now let’s take a deep dive into each of the steps to solve this puzzle -

We have given a total of 4 disks and 3 towers ‘A’, ‘B’, and ‘C’. The task is to move this disk from tower ‘A’ (Source) to Tower ‘B’ (Destination) by following the rules of the Tower of Hanoi. So steps for solving the Tower of Hanoi problem with 4 disks are-

Given -

Steps -

Step 1: Move Disk from A to B using C:

Step 2: Move Disk from A to C using B:

Step 3: Move Disk from B to C using A:

Step 4: Move Disk from A to B using C:

Step 5: Move Disk from C to A using B:

Step 6: Move Disk from C to B using A:

Step 7: Move Disk from A to B using C:

Step 8: Move Disk from A to C using B:

Step 9: Move Disk from B to C using A:

Step 10: Move Disk from B to A using C:
+

Step 11: Move Disk from C to A using B:

Step 12: Move Disk from B to C using A:

Step 13: Move Disk from A to B using C:

Step 14: Move Disk from A to C using B:

Step 15: Move Disk from B to C using A.

So the algorithm for the solution of Tower of Hanoi with 4 steps will be -

TOH( source, auxiliary, destination, 4)

TOH( source, destination, auxiliary, 3 )
Move the disk from source to destination using auxiliary.
TOH( auxiliary, source, destination, 3 )

Python Code for solving the Tower of Hanoi for 4 disks will be-

Input — 4 Disk.
Output-

Move 1 disk from A to B using C.
Move 1 disk from A to C using B.
Move 1 disk from B to C using A.
Move 1 disk from A to B using C.
Move 1 disk from C to A using B.
Move 1 disk from C to B using A.
Move 1 disk from A to B using C.
Move 1 disk from A to C using B.
Move 1 disk from B to C using A.
Move 1 disk from B to A using C.
Move 1 disk from C to A using B.
Move 1 disk from B to C using A.
Move 1 disk from A to B using C.
Move 1 disk from A to C using B.
Move 1 disk from B to C using A.

Now consider the problem’s solution with the 5 Disk-

We have been given 5 disk’s stack arranged on tower ‘A’ source. Now we need to move this disk from source to destination tower ‘C’ following the tower of Hanoi rules. So the steps for solving the puzzle with 5 disks will be -

Given -

Steps -

Step 1: Move 1 disk from A to C using B.

Step 2: Move 1 disk from A to B using C.

Step 3: Move 1 disk from C to B using A.

Step 4: Move 1 disk from A to C using B.

Step 5: Move 1 disk from B to A using C.

Step 6: Move 1 disk from B to C using A.

Step 7: Move 1 disk from A to C using B.

Step 8: Move 1 disk from A to B using C.

Step 9: Move 1 disk from C to B using A.

Step 10: Move 1 disk from C to A using B.

Step 11: Move 1 disk from B to A using C.

Step 12: Move 1 disk from C to B using A.

Step 13: Move 1 disk from A to C using B.

Step 14: Move 1 disk from A to B using C.

Step 15: Move 1 disk from C to B using A.

Step 16: Move 1 disk from A to C using B.

Step 17: Move 1 disk from B to A using C.

Step 18: Move 1 disk from B to C using A.

Step 19: Move 1 disk from A to C using B.

Step 20: Move 1 disk from B to A using C.

Step 21: Move 1 disk from C to B using A.

Step 22: Move 1 disk from C to A using B.

Step 23: Move 1 disk from B to A using C.

Step 24: Move 1 disk from B to C using A.

Step 25: Move 1 disk from A to C using B.

Step 26: Move 1 disk from A to B using C.

Step 27: Move 1 disk from C to B using A.

Step 28: Move 1 disk from A to C using B.

Step 29: Move 1 disk from B to A using C.

Step 30: Move 1 disk from B to C using A.

Step 31: Move 1 disk from A to C using B.

So the algorithm for the solution of Tower of Hanoi with 5 disks will be -

TOH( source, auxiliary, destination, 5)

TOH( source, destination, auxiliary, 4 )
Move the disk from source to destination using auxiliary.
TOH( auxiliary, source, destination, 4 )

Python code for solving the Tower of Hanoi using 5 Disk —

Input — 5 Disk.
Output — Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from C to A using B.
Move 1 disk from B to A using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from C to B using A.
Move 1 disk from C to A using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.
Move 1 disk from A to B using C.
Move 1 disk from C to B using A.
Move 1 disk from A to C using B.
Move 1 disk from B to A using C.
Move 1 disk from B to C using A.
Move 1 disk from A to C using B.

After analyzing these 2 examples of solving the tower of Hanoi with 4 and 5 disks, the algorithm for n number of disks will be -

TOH( source, auxiliary, destination, numOfDisk)

TOH( source, destination, auxiliary, numOfDisk )
Move the disk from source to destination using auxiliary.
TOH( auxiliary, source, destination, numOfDisk )

Explanation of Algorithm —

Like we have analyzed above for the 4 disk solution,

For any n number of disks, firstly the n-1 disk will be moved from source to auxiliary.
Then the nth disk will be moved from the source tower to the destination tower.
And then last, the n-1 disk will be moved from the auxiliary tower to the destination tower.

And these n-1 moves are called recursively such that individual function call is responsible to handle the 1 disk move in each call.

Python program for Solving Tower of Hanoi is -

def TOH(source, auxiliary, destination, numOfDisk):
 #Base case of Recursion that when there is no disk to move 
 #then terminate the call.
 if numOfDisk > 0:
 #Recursively calling for moving the n-1 disk from source
 #to auxiliary using destination. 
 TOH(source, destination, auxiliary, numOfDisk-1)#Moving the disk from source to destination
 print(“Move 1 disk from {0} to {1} using {2}.”
 .format(source, destination, auxiliary))
 
 #Recursively asking to move remaining disk from 
 #auxiliary to destination using source.
 TOH(auxiliary, source, destination, numOfDisk-1)if __name__ == “__main__”:
 numOfDisk = int(input())
 TOH(‘A’, ‘B’, ‘C’, numOfDisk)

Time Complexity Analysis —

If we check the steps of solving this problem then we find that firstly it is recursively calling for (n-1) problem, then it is talking one constant step. And again recursively calling for (n-1) steps. So in the mathematical term we can state the time function as — T(n) = 2T(n-1) +1.

So, if we solve this equation then the time complexity will be O(2n).
Although we can verify the time complexity by the number of steps it has taken for the different inputs.

For 1 Disk — 1 Move. (2^1–1)
For 2 Disk — 3 Moves. (2^2–1)
For 3 Disk — 7 Moves. (2^3–1)
For 4 Disk — 15 Moves. (2^4–1)
For 5 Disk — 31 Moves. (2^5–1)

So the degree of the equation O(2n-1) is O(2n).

Space Complexity — Since the time is taken of O(2n), we are using recursion for solving the problem. So the space complexity also will be O(2n). Because recursion uses call stack.

Conclusion —

The Tower of Hanoi is a mathematical puzzle discovered by the French mathematician Édouard Lucas. And this puzzle is based on some mythology.
This problem seems to be impossible to solve in the real world considering the temple priest example. But in the programming using recursion. It can be easily solved.

Tower of Hanoi in Python

Written by sonia jessica