Tower of Hanoi Problem in DSA C# - 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 peg to the destination peg 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 peg can be moved.

beginner

How many moves are required to solve the Tower of Hanoi problem with n disks?

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

intermediate

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

Move n-1 disks from source to auxiliary peg, move the nth disk from source to destination peg, then move the n-1 disks from auxiliary to destination peg recursively.

beginner

What are the three pegs used in the Tower of Hanoi problem called?

Source peg (where disks start), Auxiliary peg (used for temporary storage), and Destination peg (where disks are moved to).

intermediate

Why is the Tower of Hanoi problem a good example to understand recursion?

Because the problem naturally breaks down into smaller subproblems of the same type, making it easy to solve by calling the same function with smaller inputs until a base case is reached.

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

A When there is only one disk to move

B When all disks are on the auxiliary peg

C When no disks are left to move

D When the destination peg is empty

The base case occurs when there is only one disk to move, which can be moved directly from source to destination.

Which peg is used as temporary storage in the Tower of Hanoi problem?

A All pegs

B Destination peg

C Source peg

D Auxiliary peg

The auxiliary peg is used as temporary storage to hold disks while moving others.

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

A 5

B 7

C 3

D 9

Minimum moves = 2^3 - 1 = 7.

Which rule must be followed when moving disks in Tower of Hanoi?

A Only move the top disk of a peg

B Place larger disk on smaller disk

C Move multiple disks at once

D Disks can be moved anywhere

Only the top disk of any peg can be moved at a time.

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

A Move all disks to destination peg

B Move the largest disk to auxiliary peg

C Move n-1 disks from source to auxiliary peg

D Move n-1 disks from auxiliary to destination peg

First, move n-1 disks from source to auxiliary peg recursively.

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 Tower of Hanoi problem is a classic example of recursion.

Focus on how the problem repeats itself.

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