Tower of Hanoi Problem in DSA Python - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move n-1 disks from Source to Auxiliary

↓

Move largest disk from Source to Destination

↓

Move n-1 disks from Auxiliary to Destination

↓

All disks moved to Destination

The Tower of Hanoi moves disks recursively: move smaller stacks to auxiliary, move largest disk, then move smaller stacks to destination.

Execution Sample

DSA Python

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

This code prints the steps to move n disks from source to destination using auxiliary.

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Visual State
1	Move disk 1	1	A	C	A: [3,2] B: [] C: [1]
2	Move disk 2	2	A	B	A: [3] B: [2] C: [1]
3	Move disk 1	1	C	B	A: [3] B: [2,1] C: []
4	Move disk 3	3	A	C	A: [] B: [2,1] C: [3]
5	Move disk 1	1	B	A	A: [1] B: [2] C: [3]
6	Move disk 2	2	B	C	A: [1] B: [] C: [3,2]
7	Move disk 1	1	A	C	A: [] B: [] C: [3,2,1]
8	End	All disks moved	-	-	A: [] B: [] C: [3,2,1]

💡 All disks moved from Source (A) to Destination (C) following rules.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
A (Source Peg)	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]	[]
B (Auxiliary Peg)	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]	[]
C (Destination Peg)	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]	[3,2,1]

Key Moments - 3 Insights

Why do we move n-1 disks to the auxiliary peg before moving the largest disk?

Because the largest disk can only be moved when the smaller disks above it are out of the way, as shown in steps 1 to 3 in the execution_table.

Why can't we move a larger disk onto a smaller disk?

The rules forbid placing a larger disk on top of a smaller one to keep the stack ordered. The visual state in each step confirms this rule is never broken.

How does the recursion stop?

When n equals 1, the base case moves the smallest disk directly, as seen in step 1, preventing infinite recursion.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of peg B after step 3?

A B: [2]

B B: [2,1]

C B: []

D B: [1]

💡 Hint

Check the Visual State column in row for step 3.

At which step is the largest disk moved from peg A to peg C?

A Step 3

B Step 5

C Step 4

D Step 7

💡 Hint

Look for the operation 'Move disk 3' in the Operation column.

If we had 2 disks instead of 3, how many total moves would be made?

A 3 moves

B 4 moves

C 2 moves

D 1 move

💡 Hint

Recall the formula 2^n - 1 moves; check variable_tracker for n=3 moves count.

Concept Snapshot

Tower of Hanoi:
- Move n disks from Source to Destination using Auxiliary
- Move n-1 disks to Auxiliary
- Move largest disk to Destination
- Move n-1 disks from Auxiliary to Destination
- Base case: move 1 disk directly
- Total moves = 2^n - 1

Full Transcript

The Tower of Hanoi problem moves disks between three pegs following rules: only one disk moves at a time, and no larger disk can be placed on a smaller disk. The recursive solution moves n-1 disks to an auxiliary peg, moves the largest disk to the destination, then moves the n-1 disks from auxiliary to destination. The execution table shows each move and the state of pegs after each step. The variable tracker follows the disks on each peg. Key moments clarify why recursion stops, why the largest disk moves last, and the rule about disk sizes. The quiz tests understanding of peg states and move counts. The snapshot summarizes the recursive approach and move count formula.

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