Tower of Hanoi Problem in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to print the move from source to destination.

DSA Python

def move_disk([1], source, destination):
    print(f"Move disk [1] from {source} to {destination}")

Drag options to blanks, or click blank then click option'

An

Bdisk

Ccount

Dstep

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable names that do not represent the disk number.

Confusing source and destination parameters.

The function parameter should be 'n' to represent the disk number being moved.

2fill in blank

medium

Complete the code to call the tower_of_hanoi function recursively for n-1 disks.

DSA Python

def tower_of_hanoi([1], source, auxiliary, destination):
    if n == 1:
        move_disk(n, source, destination)
        return
    tower_of_hanoi(n-1, source, destination, auxiliary)
    move_disk(n, source, destination)
    tower_of_hanoi(n-1, auxiliary, source, destination)

Drag options to blanks, or click blank then click option'

An

Bstep

Ccount

Ddisk

Attempts:

3 left

💡 Hint

Common Mistakes

Using a different variable name than in recursive calls.

Not matching the parameter with the recursive calls.

The function parameter should be 'n' to represent the number of disks.

3fill in blank

hard

Fix the error in the base case condition to stop recursion correctly.

DSA Python

def tower_of_hanoi(n, source, auxiliary, destination):
    if n [1] 1:
        move_disk(n, source, destination)
        return
    tower_of_hanoi(n-1, source, destination, auxiliary)
    move_disk(n, source, destination)
    tower_of_hanoi(n-1, auxiliary, source, destination)

Drag options to blanks, or click blank then click option'

A!=

B<

C==

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '<' which causes incorrect recursion.

Using '!=' which never stops recursion properly.

The base case should check if n is equal to 1 to stop recursion.

4fill in blank

hard

Fill both blanks to correctly call the recursive steps in Tower of Hanoi.

DSA Python

def tower_of_hanoi(n, source, auxiliary, destination):
    if n == 1:
        move_disk(n, source, destination)
        return
    tower_of_hanoi(n-1, source, [1], [2])
    move_disk(n, source, destination)
    tower_of_hanoi(n-1, auxiliary, source, destination)

Drag options to blanks, or click blank then click option'

Aauxiliary

Bdestination

Csource

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping source and auxiliary incorrectly.

Using 'n' as a rod name.

The first recursive call moves n-1 disks from source to auxiliary using destination as temporary.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps disk numbers to their move count if greater than zero.

DSA Python

moves = [1]: [2] for [3] in range(1, n+1) if [2] > 0

Drag options to blanks, or click blank then click option'

Adisk

Bcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same variable name for key and loop variable incorrectly.

Not matching the variable names in the comprehension.

The comprehension maps each disk to its count if count is greater than zero.

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