Tower of Hanoi Problem in DSA Python - Build from Scratch

Tower of Hanoi Problem

📖 Scenario: Imagine you have 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 at the top, making a conical shape.Your task is to move the entire stack to another rod, obeying 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 rod.No disk may be placed on top of a smaller disk.

🎯 Goal: You will write a Python program that solves the Tower of Hanoi problem for 3 disks. The program will print each move step-by-step, showing which disk moves from which rod to which rod.

📋 What You'll Learn

Create a list called rods with three strings: 'A', 'B', and 'C' representing the rods.

Create a variable called num_disks and set it to 3.

Write a recursive function called tower_of_hanoi that takes four parameters: n (number of disks), source, target, and auxiliary rods.

The function should print the moves to solve the puzzle following the rules.

Call the function with the correct initial arguments to solve the puzzle for 3 disks.

Print the moves exactly as: Move disk {disk_number} from {source} to {target}.

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion and problem-solving strategies used in computer science and mathematics.

💼 Career

Understanding recursion and algorithmic thinking is essential for software development, especially in areas like algorithm design, coding interviews, and solving complex problems.

1

Setup the rods list

Create a list called rods with the exact strings 'A', 'B', and 'C' in that order.

DSA Python

# Create the rods list
# Your code here

Hint

Use square brackets to create a list and put the strings 'A', 'B', and 'C' inside it separated by commas.

2

Set the number of disks

Create a variable called num_disks and set it to the integer 3.

DSA Python

rods = ['A', 'B', 'C']
# Set the number of disks
# Your code here

Hint

Just write num_disks = 3 to store the number of disks.

3

Write the Tower of Hanoi function

Write a recursive function called tower_of_hanoi with parameters n, source, target, and auxiliary. The function should do the following:
1. If n == 1, print Move disk 1 from {source} to {target}.
2. Otherwise, call itself to move n-1 disks from source to auxiliary using target.
3. Print the move of disk n from source to target.
4. Call itself to move n-1 disks from auxiliary to target using source.

DSA Python

rods = ['A', 'B', 'C']
num_disks = 3
# Define the tower_of_hanoi function
# Your code here

Hint

Use recursion: the function calls itself with smaller values of n to move disks step by step.

4

Call the function and print the moves

Call the function tower_of_hanoi with num_disks, rods[0] as source, rods[2] as target, and rods[1] as auxiliary to print the moves for 3 disks.

DSA Python

rods = ['A', 'B', 'C']
num_disks = 3

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
    else:
        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)

# Call the function to solve for 3 disks
# Your code here

Hint

Call tower_of_hanoi(num_disks, rods[0], rods[2], rods[1]) to start the solution.

Practice

1. What is the minimum number of moves required to solve the Tower of Hanoi problem with 3 disks?

easy

A. 5

B. 7

C. 9

D. 6

Solution

1. Step 1: Understand the formula for minimum moves

   The minimum moves required for n disks is 2^n - 1.

2. Step 2: Calculate for 3 disks

   For 3 disks, minimum moves = 2^3 - 1 = 8 - 1 = 7.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Using n instead of 2^n - 1
• Calculating 2*n - 1 instead of 2^n - 1
• Confusing number of disks with moves

2. Which of the following is the correct base case condition in a recursive Tower of Hanoi function in Python?

easy

A. if n == 0: return

B. if n < 0: return

C. if n > 1: call recursion

D. if n == 1: move disk

Solution

1. Step 1: Identify base case for recursion

   The base case stops recursion when only one disk is left, i.e., n == 1.

2. Step 2: Understand base case action

   When n == 1, the disk is moved directly from source to target.

3. Final Answer:

   if n == 1: move disk -> Option D

4. Quick Check:

   Base case is n == 1 [OK]

Hint: Base case is when only one disk remains (n == 1) [OK]

Common Mistakes:

• Using n == 0 as base case incorrectly
• Not defining a base case causing infinite recursion
• Using invalid conditions like n < 0

3. What will be the output of the following Python code snippet for Tower of Hanoi with 2 disks?

def hanoi(n, source, target, auxiliary):
    if n == 0:
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n-1, auxiliary, target, source)

hanoi(2, 'A', 'C', 'B')

medium

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

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

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

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

Solution

1. Step 1: Trace recursive calls for n=2

   First, move disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

2. Step 2: Verify print statements order

   Prints match the moves: disk 1 A->B, disk 2 A->C, disk 1 B->C.

3. Final Answer:

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C -> Option A

4. Quick Check:

   Correct move sequence for 2 disks [OK]

Hint: Follow recursive calls step-by-step [OK]

Common Mistakes:

• Mixing source and auxiliary rods
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in this Tower of Hanoi recursive function and select the correct fix:

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk {n} from {source} to {target}")
    else:
        hanoi(n-1, source, target, auxiliary)
        print(f"Move disk {n} from {source} to {target}")
        hanoi(n-1, auxiliary, target, source)

medium

A. Change first recursive call to hanoi(n-1, source, auxiliary, target)

B. Change base case to if n == 0

C. Swap print statements order

D. Remove the else block

Solution

1. Step 1: Analyze recursive calls

   The first recursive call incorrectly moves disks from source to target instead of auxiliary.

2. Step 2: Correct the first recursive call

   It should be hanoi(n-1, source, auxiliary, target) to move disks to auxiliary rod first.

3. Final Answer:

   Change first recursive call to hanoi(n-1, source, auxiliary, target) -> Option A

4. Quick Check:

   Correct recursive call order fixes the error [OK]

Hint: First recursive call moves disks to auxiliary rod [OK]

Common Mistakes:

• Calling recursion with wrong target rod
• Changing base case incorrectly
• Swapping print statements unnecessarily

5. You want to solve Tower of Hanoi for 4 disks but only have 3 rods. What is the minimum number of moves required, and why can't it be less than that?

hard

A. 14 moves, because the largest disk can be moved directly

B. 16 moves, because one extra move is needed for 4 disks

C. 15 moves, because 2^4 - 1 is the minimum for 3 rods

D. 7 moves, because only half the disks need moving

Solution

1. Step 1: Apply minimum moves formula for 3 rods

   Minimum moves for n disks with 3 rods is 2^n - 1, so for 4 disks: 2^4 - 1 = 15.

2. Step 2: Understand why moves can't be less

   With 3 rods, no shortcut exists; all disks must be moved following rules, so 15 is minimum.

3. Final Answer:

   15 moves, because 2^4 - 1 is the minimum for 3 rods -> Option C

4. Quick Check:

   Minimum moves = 2^n - 1 for 3 rods [OK]

Hint: Use 2^n - 1 formula for 3 rods minimum moves [OK]

Common Mistakes:

• Assuming fewer moves possible with 3 rods
• Adding extra moves unnecessarily
• Confusing number of rods with moves