Home »
Python »
Python Programs
Python program for Tower of Hanoi
Here, we are going to learn how to implement the solution to the Tower of Hanao problem using a Python program.
By Anuj Singh Last updated : January 04, 2024
Problem statement: Tower of Hanoi
You are challenged for a challenge to find the number of moves required to move a stack of disks from one peg to another peg. Wait for a second, it sounds easy? Let’s find are what is going on and in this article, we are introducing a chapter of "TOWER OF HANOI".
You are given with a stack of n disks on a peg arranges as largest is at the bottom and smallest is at the top. We are required to shift this whole stack to another peg (total three pegs, two are empty initially) with considering the following rule:
- No larger disk can be placed over a smaller one.
- One disk at a time.
Solving Tower of Hanoi Problem in Python
The problem is looking easy but it's not. The way we are going to tackle it is recursion. The problem is simple when you see it from a recursion perspective.
Key: The number of steps required to shift the stack is exactly equal to the twice of steps for shifting the stack of one less disk (The largest one) plus one step.
Consider the case of shifting one disk : T(1) = 1
Consider the case of shifting two disk : T(2) = 2*T(1) + 1 = 3
Consider the case of shifting three disk : T(3) = 2*T(2) + 1 = 7
.
.
.
.
T(n) = 2*T(n-1) + 1
Implementing this formula now in our python program is our next goal of solving this.
Python program to implement Towe of Hanoi
# Code to implement Towe of Hanoi
# defining function
def hanoi(x):
if x == 1:
return 1
else:
return 2 * hanoi(x - 1) + 1
# Reading number of disks
x = int(input("Enter the number of disks: "))
# Printing number of steps
print("Number of steps: ", hanoi(x))
Output
The output of the above example is:
RUN 1:
Enter the number of disks: 2
Number of steps: 3
RUN 2:
Enter the number of disks: 4
Number of steps: 15
RUN 3:
Enter the number of disks: 5
Number of steps: 31
To understand the above program, you should have the basic knowledge of the following Python topics:
Python Basic Programs »