Published: 12 Mar 2025 | Reading Time: 4 min
The Tower of Hanoi is a mathematical puzzle that is well-known as a favourite among programmers and mathematician circles. The challenge is to move a set of disks from one rod to another while following specific rules. Therefore, it is an excellent example of problem-solving with recursion.
This article explores the Tower of Hanoi in Python, where recursion helps break down the problem into smaller, manageable steps. We'll examine the algorithm for Tower of Hanoi in Python to understand how it works, then implement a Python program for Tower of Hanoi that shows the sequence of moves required to solve the puzzle.
The Tower of Hanoi is a mathematical puzzle invented in 1883 by French mathematician Édouard Lucas. The puzzle concept comes from an ancient legend that tells of a Hindu temple where priests were given the challenge of moving 64 golden disks from one pole to another.
The disks are arranged in descending order, with the largest at the bottom and the smallest on top. The priests had to follow strict rules:
According to the legend, once the priests completed the task, the temple would crumble, and the world would come to an end. However, mathematically, the puzzle requires 2⁶⁴ - 1 moves to complete. Even if one move were made per second, it would take over 584 billion years—far exceeding the age of the universe itself.
Other than its mythical origins, the Tower of Hanoi is studied in computer science and mathematics due to its strong connection with recursion. The puzzle is an excellent example of divide and conquer algorithms, where a complex problem is broken into smaller, more manageable subproblems.
This problem has practical applications in areas like:
To solve the Tower of Hanoi puzzle, we use a recursive approach. Recursion allows us to break down the problem into smaller subproblems, making it easier to understand and implement.
Let's consider a simple case where we have three disks stacked on the first rod. Based on the formula 2ⁿ - 1, solving this requires 7 moves. In this setup:
The AUX rod plays a crucial role in the process, allowing disks to be moved strategically while following the puzzle's constraints.
By applying recursion, we can systematically shift the disks from the SOURCE to the TARGET using the AUX rod. Here is how the solution works:
| Step | Action | Description |
|---|---|---|
| Initial State | - | All three disks (1, 2, 3) are stacked on Tower A. Disk 1 is the smallest on top and Disk 3 is the largest at the bottom |
| Move 1 | Disk 1: A → C | Transfer Disk 1 from Tower A to Tower C |
| Move 2 | Disk 2: A → B | Transfer Disk 2 from Tower A to Tower B |
| Move 3 | Disk 1: C → B | Transfer Disk 1 from Tower C to Tower B, placing it on top of Disk 2 |
| Move 4 | Disk 3: A → C | Transfer Disk 3 from Tower A to Tower C |
| Move 5 | Disk 1: B → A | Transfer Disk 1 from Tower B to Tower A |
| Move 6 | Disk 2: B → C | Transfer Disk 2 from Tower B to Tower C, placing it on top of Disk 3 |
| Move 7 | Disk 1: A → C | Transfer Disk 1 from Tower A to Tower C, placing it on top of Disk 2 |
| Final State | - | Problem is solved and all disks are stacked on Tower C in the same order as they started on Tower A |
The Tower of Hanoi in Python problem follows a recursive approach where we break the problem into smaller bits. Below is the step-by-step algorithm for Tower of Hanoi in Python:
1. Define a function tower_of_hanoi(n, source, target, aux):
n represents the number of diskssource is the rod where the disks starttarget is the rod where disks need to be movedaux is the auxiliary rod used for temporary storage2. Base Case:
source rod to the target rod3. Recursive Steps:
source to aux using target as the auxiliary rodsource to targetaux to target using source as the auxiliary rod4. Repeat this process until all disks are successfully transferred to the target rod following the given constraints.
def tower_of_hanoi(n, source, target, aux):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
# Move n-1 disks from source to aux using target as auxiliary
tower_of_hanoi(n - 1, source, aux, target)
# Move the nth disk from source to target
print(f"Move disk {n} from {source} to {target}")
# Move n-1 disks from aux to target using source as auxiliary
tower_of_hanoi(n - 1, aux, target, source)
# Example usage
n = int(input("Enter the number of disks: "))
tower_of_hanoi(n, 'A', 'C', 'B')
tower_of_hanoi(n, source, target, aux) follows the recursive logic discussed earliersource to targetEnter the number of disks: 3
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
=== Code Execution Successful ===
| Complexity Type | Value | Explanation |
|---|---|---|
| Time Complexity | O(2ⁿ - 1) ≈ O(2ⁿ) | Each move follows a recursive pattern doubling at every step |
| Space Complexity | O(n) | The recursive function calls are stored in the call stack up to a depth of n |
The Tower of Hanoi is a wonderful example of recursion and algorithmic thinking. Understanding and implementing the Tower of Hanoi in Python helps improve problem-solving skills, making it an essential concept for anyone learning data structures and algorithms.
For those looking to further strengthen their coding skills and become proficient at the level of professionals even before joining work, the CCBP Academy 4.0 program is the perfect place to start.
The Tower of Hanoi is a puzzle in which disks must be moved from one rod to another by following certain rules. The rules are as follows: only one disk can be moved at a time, and no larger disk can be placed on a smaller one.
Recursion simplifies the problem by breaking it into smaller steps. It moves n-1 disks first, places the largest disk, and then moves n-1 disks again, following a structured pattern.
The time complexity is O(2ⁿ - 1), meaning it grows exponentially as the number of disks increases.
The formula 2ⁿ - 1 gives the total moves required. For 3 disks, it takes 7 moves. For 4 disks, it takes 15 moves.
The concept helps in data organisation, recursion learning, algorithm design, AI problem-solving, and computer disk storage management.