Tower of Hanoi Program in Python
Python Program - Tower of Hanoi
The Tower of Hanoi is a classic puzzle game consisting of three pegs and a number of disks of different sizes, which can slide onto any peg.
The puzzle starts with the disks in a neat stack in ascending order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg.
And the movement of disks between the pegs must obey the following simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
- No disk may be placed on top of a smaller disk.
The puzzle is commonly used in computer science and programming as an example of a recursive function.
Tower of Hanoi Program using Recursion
In the following program, we will use recursion technique to solve the Tower of Hanoi problem.
tower_of_hanoi() function has four parameters.
n
- the number of disks.from_rod
- The rod which has all the disks at the start.to_rod
- The rod to which all the disks has to be moved.aux_rod
- The auxiliary rod which can be used to place the disks temporarily.
Python Program
def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
if n == 1:
print("Move disk 1 from rod", from_rod, "to rod", to_rod)
return
tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)
# Number of disks
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')
Output
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
Summary
In this tutorial, we learned how to solve the problem of Tower of Hanoi using recursion, with examples.