Tower of Hanoi in Python: Recursive Solution & Code Example

The Tower of Hanoi is a cool mathematical puzzle that was 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. These disks were arranged in descending order, with the largest at the bottom and the smallest on top. The priests had to follow strict rules:

1. Only one disk could be moved at a time.

2. A larger disk could never be placed on top of a smaller disk.

3. Disks could only be placed on one of the three available poles.

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 move to complete. Even if one move were made per second, it would take over 584 billion years and far exceed 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. In the method, a complex problem is broken into smaller, more manageable subproblems.

This problem has practical applications in areas like:

• Data organisation (e.g., sorting algorithms)
• Recursive problem-solving (e.g., backtracking)
• Artificial intelligence (e.g., planning and decision-making)
• Algorithm analysis

To solve the Tower of Hanoi puzzle, we have to use a recursive approach. Recursion allows us to break down the problem into smaller subproblems. So it becomes 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 leftmost rod is called the SOURCE, where all disks start.
• The rightmost rod is the TARGET, where all disks must be moved.
• The middle rod is known as the AUXILIARY (AUX), which helps temporarily hold disks during the transfer.

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 now the steps of the solution works: 

Initial State: All three disks (1, 2, 3) are stacked on Tower A. 1 is the smallest disc on top and 3 the largest at the bottom.

Move 1: Transfer Disk 1 from Tower A to Tower C.

Move 2: Transfer Disk 2 from Tower A to Tower B.

Move 3: Transfer Disk 1 from Tower C to Tower B and placing it on top of Disk 2.

Move 4: Transfer Disk 3 from Tower A to Tower C.

Move 5: Transfer Disk 1 from Tower B to Tower A.

Move 6: Transfer Disk 2 from Tower B to Tower C and placing it on top of Disk 3.

Move 7: Transfer Disk 1 from Tower A to Tower C and 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.

In the next section, we will examine the algorithm for Tower of Hanoi in Python and implement a Python program to demonstrate this recursive solution.

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 disks.
• source is the rod where the disks start.
• target is the rod where disks need to be moved.
• aux is the auxiliary rod used for temporary storage.

2. Base Case:

• If there is only one disk, move it directly from the source rod to the target rod.

3. Recursive Steps:

• Move n-1 disks from source to aux using target as the auxiliary rod.
• Move the nth (largest) disk from source to target.
• Move the n-1 disks from aux to target using source as the auxiliary rod.

4. Repeat this process until all disks are successfully transferred to the target rod following the given constraints.

Tower of Hanoi Program in Python Using Recursion 

Now let’s look at the Hanoi Tower Python code

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')

How the code works

1. The function tower_of_hanoi(n, source, target, aux) follows the recursive logic discussed earlier.

2. If there's only one disk, it moves directly from source to target.

3. Otherwise, it moves n-1 disks to the auxiliary rod, then moves the largest disk to the target rod, and finally moves the n-1 disks from the auxiliary rod to the target rod.

4. The function prints each move to track the process.

Output

Enter 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 

1. Time Complexity: O(2ⁿ - 1) ≈ O(2ⁿ). This is because each move follows a recursive pattern doubling at every step.

2. Space Complexity: O(n). This is because the recursive function calls are stored in the call stack up to a depth of n.

To wrap it up, we can say that it 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. Enroll today and get a letup in your career!

1. What is the Tower of Hanoi problem?

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.

2. Why is recursion used in the Tower of Hanoi?

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.

3. What is the time complexity of the Tower of Hanoi?

The time complexity is O(2ⁿ - 1), meaning it grows exponentially as the number of disks increases.

4. How many moves are needed for n disks?

The formula 2ⁿ - 1 gives the total moves required. For 3 disks, it takes 7 moves. Then, for 4 disks, it takes 15 moves.

5. Where is the Tower of Hanoi used in real life?

The concept helps in data organisation, recursion learning, algorithm design, AI problem-solving, and computer disk storage management.