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.
Run Code Copy
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')
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
In this tutorial, we learned how to solve the problem of Tower of Hanoi using recursion, with examples.