Tower of Hanoi Problem in DSA C# - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move top 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

↓

End

The problem moves disks step-by-step: first move smaller disks to auxiliary, then largest disk to destination, then smaller disks from auxiliary to destination.

Execution Sample

DSA C#

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

This recursive code moves n disks from source to destination using auxiliary.

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	State of Pegs (Source | Auxiliary | Destination)
1	Move disk 1	1	A	C	[3,2] | [] | [1]
2	Move disk 2	2	A	B	[3] | [2] | [1]
3	Move disk 1	1	C	B	[3] | [2,1] | []
4	Move disk 3	3	A	C	[] | [2,1] | [3]
5	Move disk 1	1	B	A	[1] | [2] | [3]
6	Move disk 2	2	B	C	[1] | [] | [3,2]
7	Move disk 1	1	A	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
Source Peg (A)	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]
Auxiliary Peg (B)	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]
Destination Peg (C)	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]

Key Moments - 3 Insights

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

Because the largest disk cannot be placed on a smaller disk, so we clear the way by moving smaller disks first (see steps 1-3 in execution_table).

Why is the base case moving disk 1 directly important?

It stops recursion and moves the smallest disk directly, as shown in step 1 and repeated moves of disk 1 in the table.

How do we know when all disks are moved correctly?

When the source peg is empty and destination peg has all disks in order, as shown after step 7 in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table, after which step is the largest disk moved from Source to Destination?

A Step 3

B Step 5

C Step 4

D Step 7

💡 Hint

Check the 'Operation' and 'Disks Moved' columns in execution_table for the largest disk move.

According to variable_tracker, what is the state of Auxiliary Peg after Step 3?

A [2]

B [2,1]

C []

D [1]

💡 Hint

Look at the Auxiliary Peg row and the column 'After Step 3' in variable_tracker.

If we increase the number of disks to 4, how would the number of steps in execution_table change?

A It would be 2^4 - 1 steps

B It would double

C It would roughly double plus one

D It would increase by 1

💡 Hint

Recall the Tower of Hanoi formula for minimum moves: 2^n - 1.

Concept Snapshot

Tower of Hanoi moves n disks from Source to Destination using Auxiliary.
Rules: move one disk at a time, never place larger on smaller.
Recursive steps: move n-1 disks to Auxiliary, move largest disk, move n-1 disks to Destination.
Minimum moves: 2^n - 1.
Base case: move single disk directly.

Full Transcript

The Tower of Hanoi problem moves disks between three pegs following strict rules. The recursive solution moves n-1 disks to an auxiliary peg, then moves the largest disk to the destination, and finally moves the n-1 disks from auxiliary to destination. The execution table shows each move step-by-step, tracking which disk moves from which peg to which peg, and the state of all pegs after each move. The variable tracker records the disks on each peg after every step. Key moments clarify why the largest disk moves last, the importance of the base case, and how to recognize completion. The quiz tests understanding of move order, peg states, and the formula for total moves. The snapshot summarizes the recursive approach and rules clearly.

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