Tower of Hanoi Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tower of Hanoi moves for 2 disks

What is the output of the following Tower of Hanoi code for 2 disks?

DSA C#

void TowerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        Console.WriteLine($"Move disk 1 from rod {from_rod} to rod {to_rod}");
        return;
    }
    TowerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    Console.WriteLine($"Move disk {n} from rod {from_rod} to rod {to_rod}");
    TowerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

TowerOfHanoi(2, 'A', 'C', 'B');

A

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

B

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

C

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

D

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

💡 Hint

Remember the recursive steps: move n-1 disks to auxiliary rod, move nth disk to target, then move n-1 disks from auxiliary to target.

The Tower of Hanoi algorithm moves the top n-1 disks to the auxiliary rod, then moves the largest disk to the target rod, and finally moves the n-1 disks from auxiliary to target. For 2 disks, the moves are: disk 1 from A to B, disk 2 from A to C, disk 1 from B to C.

🧠 Conceptual

intermediate

Minimum moves required for Tower of Hanoi

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

A 8

B 31

C 16

D 15

💡 Hint

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

The minimum moves to solve Tower of Hanoi with n disks is 2^n - 1. For 4 disks, 2^4 - 1 = 16 - 1 = 15 moves.

🔧 Debug

advanced

Identify the error in Tower of Hanoi code

What error will this Tower of Hanoi code produce when run with n=3?

DSA C#

void TowerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 0) {
        Console.WriteLine($"Move disk {n} from rod {from_rod} to rod {to_rod}");
        return;
    }
    TowerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    Console.WriteLine($"Move disk {n} from rod {from_rod} to rod {to_rod}");
    TowerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

TowerOfHanoi(3, 'A', 'C', 'B');

A Prints moves including disk 0 which is invalid

B No output, infinite recursion causing stack overflow

C Syntax error due to missing semicolon

D Runtime error: null reference exception

💡 Hint

Check the base case condition and what happens when n=0.

The base case incorrectly checks for n == 0 and prints a move for disk 0, which is invalid. The base case should be n == 1 to stop recursion properly.

🚀 Application

advanced

Number of moves for 5 disks after 10 moves

If you have solved 10 moves in the Tower of Hanoi problem with 5 disks, how many moves remain to complete the puzzle?

A 22

B 23

C 21

D 24

💡 Hint

Calculate total moves for 5 disks and subtract 10.

Total moves for 5 disks is 2^5 - 1 = 31. After 10 moves, remaining moves = 31 - 10 = 21.

❓ Predict Output

expert

Output of Tower of Hanoi for 3 disks with custom rods

What is the output of this Tower of Hanoi code for 3 disks moving from rod X to rod Z using rod Y?

DSA C#

void TowerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        Console.WriteLine($"Move disk 1 from rod {from_rod} to rod {to_rod}");
        return;
    }
    TowerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    Console.WriteLine($"Move disk {n} from rod {from_rod} to rod {to_rod}");
    TowerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

TowerOfHanoi(3, 'X', 'Z', 'Y');

A

Move disk 1 from rod X to rod Y
Move disk 2 from rod X to rod Z
Move disk 1 from rod Y to rod Z
Move disk 3 from rod X to rod Z
Move disk 1 from rod Y to rod X
Move disk 2 from rod Z to rod Y
Move disk 1 from rod X to rod Y

B

Move disk 1 from rod X to rod Z
Move disk 2 from rod X to rod Y
Move disk 1 from rod Z to rod Y
Move disk 3 from rod X to rod Z
Move disk 1 from rod Y to rod X
Move disk 2 from rod Y to rod Z
Move disk 1 from rod X to rod Z

C

Move disk 1 from rod X to rod Y
Move disk 2 from rod X to rod Y
Move disk 1 from rod Y to rod Z
Move disk 3 from rod X to rod Z
Move disk 1 from rod Z to rod X
Move disk 2 from rod Y to rod Z
Move disk 1 from rod X to rod Z

D

Move disk 1 from rod X to rod Y
Move disk 2 from rod X to rod Z
Move disk 1 from rod Y to rod Z
Move disk 3 from rod X to rod Y
Move disk 1 from rod Z to rod X
Move disk 2 from rod Z to rod Y
Move disk 1 from rod X to rod Y

💡 Hint

Follow the recursive steps carefully with the given rod names.

The Tower of Hanoi moves for 3 disks from X to Z using Y are: disk 1 from X to Z, disk 2 from X to Y, disk 1 from Z to Y, disk 3 from X to Z, disk 1 from Y to X, disk 2 from Y to Z, disk 1 from X to Z.

Practice

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

easy

A. 6

B. 7

C. 8

D. 9

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:

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

2. Which of the following is the correct C# method signature for a recursive Tower of Hanoi function?

easy

A. void TowerOfHanoi(int n, string fromRod, string toRod)

B. int TowerOfHanoi(int n, char fromRod, char toRod, char auxRod)

C. int TowerOfHanoi(int n, string fromRod, string toRod, string auxRod)

D. void TowerOfHanoi(int n, char fromRod, char toRod, char auxRod)

Solution

1. Step 1: Identify correct parameter types

   The Tower of Hanoi function typically uses integer for disk count and characters for rods.

2. Step 2: Check return type and parameters

   The function usually returns void and takes 3 rods as char parameters plus disk count as int.

3. Final Answer:

   void TowerOfHanoi(int n, char fromRod, char toRod, char auxRod) -> Option D

4. Quick Check:

   Correct signature uses void and char rods [OK]

Hint: Use void return and char for rods in signature [OK]

Common Mistakes:

• Using string instead of char for rods
• Returning int instead of void
• Missing auxiliary rod parameter

3. What will be the output sequence of moves for Tower of Hanoi with 2 disks from rod A to rod C using rod B as auxiliary?

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 B
Move disk 1 from A to C
Move disk 2 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 2 from A to C
Move disk 1 from B to A
Move disk 2 from C to B

Solution

1. Step 1: Understand the recursive move sequence for 2 disks

   Move smaller disk 1 to auxiliary rod B, then move disk 2 to target rod C, then move disk 1 from B to C.

2. Step 2: Verify the move order

   Sequence is: 1 from A to B, 2 from A to C, 1 from B to 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 order for 2 disks [OK]

Hint: For 2 disks, move smaller disk first to aux rod [OK]

Common Mistakes:

• Swapping disk numbers in moves
• Confusing auxiliary and target rods
• Reversing move order

4. Identify the error in this Tower of Hanoi recursive call snippet:

void Hanoi(int n, char from, char to, char aux) {
  if (n == 0) return;
  Hanoi(n - 1, from, aux, to);
  Console.WriteLine($"Move disk {n} from {from} to {to}");
  Hanoi(n - 1, aux, to, from);
}

medium

A. Base case should be if (n == 1) return;

B. Recursive calls have wrong rod order in parameters

C. No error, code is correct

D. Console.WriteLine should print disk n-1 instead of n

Solution

1. Step 1: Check base case correctness

   Base case n == 0 means no disks to move, which is correct to stop recursion.

2. Step 2: Verify recursive calls and print statement

   Recursive calls correctly move n-1 disks between rods, and print statement moves disk n from 'from' to 'to'.

3. Final Answer:

   No error, code is correct -> Option C

4. Quick Check:

   Base case and recursion are correctly implemented [OK]

Hint: Base case n==0 is correct to stop recursion [OK]

Common Mistakes:

• Changing base case to n==1 incorrectly
• Mixing up rod parameters in recursive calls
• Printing wrong disk number

5. You want to solve Tower of Hanoi for 4 disks but print only the moves where disk 1 is moved. How many such moves will be printed?

hard

A. 8

B. 15

C. 7

D. 4

Solution

1. Step 1: Calculate total moves for 4 disks

   Total moves = 2^4 - 1 = 15 moves.

2. Step 2: Count moves involving disk 1

   Disk 1 moves every alternate move, so number of moves = (total moves + 1) / 2 = (15 + 1)/2 = 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Disk 1 moves half the times plus one [OK]

Hint: Disk 1 moves on every alternate move, count half plus one [OK]

Common Mistakes:

• Assuming disk 1 moves equal to total moves
• Using total moves minus one
• Confusing disk 1 moves with total disks