Python Program to Solve the Tower of Hanoi Problem Using Recursion

Introduction

The Tower of Hanoi is a classic problem in computer science and mathematics that involves moving a stack of disks from one rod to another, following certain rules. The problem consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest disk at the top.

Rules:

Only one disk can be moved at a time.
Each move involves taking the top disk from one of the stacks and placing it on top of another stack or an empty rod.
No disk may be placed on top of a smaller disk.

The objective of the puzzle is to move the entire stack of disks from one rod to another, following these rules.

The problem can be solved using recursion, where the solution to the problem with n disks involves solving smaller subproblems with n-1 disks.

Problem Statement

Create a Python program that:

Defines a recursive function named tower_of_hanoi.
The function takes four arguments: n (the number of disks), source (the rod from which the disks are to be moved), target (the rod to which the disks are to be moved), and auxiliary (the auxiliary rod used during the process).
The function prints the steps required to move the disks from the source rod to the target rod.

Solution Steps

Define the Recursive Function: Use the def keyword to define a function named tower_of_hanoi.
Add the Base Case: If there is only one disk, move it directly from the source rod to the target rod.
Implement the Recursive Case:

Move n-1 disks from the source rod to the auxiliary rod, using the target rod as a helper.
Move the nth disk from the source rod to the target rod.
Move the n-1 disks from the auxiliary rod to the target rod, using the source rod as a helper.

Call the Function: Call the tower_of_hanoi function with the appropriate arguments to solve the problem for n disks.

Python Program

# Python Program to Solve the Tower of Hanoi Problem Using Recursion
# Author: https://www.rameshfadatare.com/

# Step 1: Define the recursive function
def tower_of_hanoi(n, source, target, auxiliary):
    # Step 2: Add the base case
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    # Step 3: Implement the recursive case
    tower_of_hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n - 1, auxiliary, target, source)

# Step 4: Call the function with sample values
n = 3  # Number of disks
tower_of_hanoi(n, 'A', 'C', 'B')  # A is the source rod, C is the target rod, B is the auxiliary rod

Explanation

Step 1: Define the Recursive Function

The function tower_of_hanoi is defined using the def keyword. It takes four parameters:
- n: The number of disks to move.
- source: The rod from which the disks are moved.
- target: The rod to which the disks are moved.
- auxiliary: The rod used as a helper during the process.

Step 2: Add the Base Case

The base case checks if there is only one disk (n == 1). If so, the function prints the move of that disk directly from the source rod to the target rod.

Step 3: Implement the Recursive Case

The function moves the top n-1 disks from the source rod to the auxiliary rod, using the target rod as a helper.
The nth disk is then moved from the source rod to the target rod.
Finally, the n-1 disks are moved from the auxiliary rod to the target rod, using the source rod as a helper.

Step 4: Call the Function

The tower_of_hanoi function is called with n = 3 to solve the problem for three disks. The rods are labeled ‘A’ (source), ‘C’ (target), and ‘B’ (auxiliary).

Output Example

Example Output:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Explanation of the 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.

Additional Examples

Example 1: Tower of Hanoi with 2 Disks

# Solving Tower of Hanoi for 2 disks
n = 2
tower_of_hanoi(n, 'A', 'C', 'B')

Output:

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

Example 2: Tower of Hanoi with 4 Disks

# Solving Tower of Hanoi for 4 disks
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')