Tower of Hanoi Problem in DSA Python

Mental Model

Move a stack of disks from one peg to another, one disk at a time, never placing a bigger disk on a smaller one.

Analogy: Imagine moving a stack of different sized plates from one table to another using a third empty table, following the rule that you can only move one plate at a time and never put a bigger plate on top of a smaller one.

Peg A       Peg B       Peg C
  |           |           |
 [3]          |           |
 [2]          |           |
 [1]          |           |
-----------------------------

Dry Run Walkthrough

Input: 3 disks on Peg A, move all to Peg C using Peg B

Goal: Move all disks from Peg A to Peg C following the rules

Step 1: Move disk 1 from Peg A to Peg C

Peg A: [3, 2]
Peg B: []
Peg C: [1]

Why: Smallest disk moves first to free up bigger disks

Step 2: Move disk 2 from Peg A to Peg B

Peg A: [3]
Peg B: [2]
Peg C: [1]

Why: Move next bigger disk to free the largest disk

Step 3: Move disk 1 from Peg C to Peg B

Peg A: [3]
Peg B: [2, 1]
Peg C: []

Why: Place smallest disk on top of disk 2 on Peg B

Step 4: Move disk 3 from Peg A to Peg C

Peg A: []
Peg B: [2, 1]
Peg C: [3]

Why: Move largest disk to target peg

Step 5: Move disk 1 from Peg B to Peg A

Peg A: [1]
Peg B: [2]
Peg C: [3]

Why: Free disk 2 to move to Peg C

Step 6: Move disk 2 from Peg B to Peg C

Peg A: [1]
Peg B: []
Peg C: [3, 2]

Why: Move disk 2 on top of disk 3 on Peg C

Step 7: Move disk 1 from Peg A to Peg C

Peg A: []
Peg B: []
Peg C: [3, 2, 1]

Why: Place smallest disk on top to complete the stack

Result:

Peg A: []
Peg B: []
Peg C: [3, 2, 1]

Annotated Code

DSA Python

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 0:
        return
    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)

# Driver code
n = 3
print(f"Tower of Hanoi solution for {n} disks:")
tower_of_hanoi(n, 'Peg A', 'Peg C', 'Peg B')

if n == 0:

base case: no moves needed for 0 disks

tower_of_hanoi(n - 1, source, auxiliary, target)

move top n-1 disks to auxiliary peg

print(f"Move disk {n} from {source} to {target}")

move the largest disk to target peg

tower_of_hanoi(n - 1, auxiliary, target, source)

move n-1 disks from auxiliary to target peg

Output

Tower of Hanoi solution for 3 disks:

Move disk 1 from Peg A to Peg C

Move disk 2 from Peg A to Peg B

Move disk 1 from Peg C to Peg B

Move disk 3 from Peg A to Peg C

Move disk 1 from Peg B to Peg A

Move disk 2 from Peg B to Peg C

Move disk 1 from Peg A to Peg C

Complexity Analysis

Time: O(2^n) because the number of moves doubles with each additional disk

Space: O(n) due to the recursion call stack depth equal to number of disks

vs Alternative: No simpler algorithm exists; this is the minimal number of moves required

Edge Cases

n = 1 (single disk)

Directly move the disk from source to target

DSA Python

print(f"Move disk {n} from {source} to {target}")

n = 0 (no disks)

No moves are made, function returns immediately

DSA Python

if n == 0:

When to Use This Pattern

When you see a problem about moving disks or items between pegs with size constraints, think of the Tower of Hanoi pattern because it uses recursion to break down the problem into smaller moves.

Common Mistakes

Mistake: Trying to move multiple disks at once violating the rules
Fix: Always move only one disk at a time and use recursion to handle smaller stacks

Mistake: Mixing up the order of pegs in recursive calls
Fix: Carefully track source, target, and auxiliary pegs in each recursive call

Summary

It solves the problem of moving disks between pegs following size rules using recursion.

Use it when you need to move stacked items with constraints on order and size.

The key insight is breaking the problem into moving smaller stacks recursively.

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