Tower of Hanoi Problem in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Tower of Hanoi problem?

To move all disks from the source rod to the destination rod following the rules: only one disk can be moved at a time, a larger disk cannot be placed on top of a smaller disk, and only the top disk of any rod can be moved.

beginner

What are the three rods called in the Tower of Hanoi problem?

Source rod (where disks start), Auxiliary rod (used for temporary holding), and Destination rod (where disks need to be moved).

intermediate

Explain the recursive approach to solve the Tower of Hanoi problem.

Move n-1 disks from source to auxiliary rod, move the nth (largest) disk to destination rod, then move the n-1 disks from auxiliary to destination rod. Repeat this recursively until all disks are moved.

beginner

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

The minimum number of moves is 2^n - 1, where n is the number of disks.

beginner

Why can't a larger disk be placed on top of a smaller disk in Tower of Hanoi?

Because the rules of the problem restrict placing a larger disk on a smaller one to maintain order and challenge, ensuring the problem requires careful planning and recursion.

In the Tower of Hanoi problem, what is the role of the auxiliary rod?

A Temporary holding place for disks

B Final destination for disks

C Starting point for disks

D No role

The auxiliary rod is used as a temporary place to hold disks while moving them from source to destination.

What is the base case in the recursive solution of Tower of Hanoi?

A When there is only one disk to move

B When all disks are moved

C When no disks are left on the source rod

D When the auxiliary rod is empty

The base case is when there is only one disk to move, which can be moved directly to the destination rod.

How many moves are needed to solve Tower of Hanoi with 3 disks?

A 5

B 6

C 7

D 8

Minimum moves = 2^3 - 1 = 7.

Which of the following is NOT a rule in Tower of Hanoi?

A Only one disk can be moved at a time

B All disks start on the source rod

C Only the top disk of a rod can be moved

D A larger disk can be placed on a smaller disk

A larger disk cannot be placed on a smaller disk according to the rules.

What is the first step in the recursive solution for n disks?

A Move n disks directly to destination

B Move n-1 disks from source to auxiliary

C Move the largest disk to auxiliary

D Move all disks to auxiliary

The first step is to move n-1 disks from source to auxiliary rod.

Describe the recursive steps to solve the Tower of Hanoi problem for n disks.

Think about breaking the problem into smaller parts.

Explain why the minimum number of moves for Tower of Hanoi is 2^n - 1.

Consider how moves grow as disks increase.

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