Tower of Hanoi Problem in DSA C - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move 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

The Tower of Hanoi moves disks recursively: 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) {
    printf("Move disk 1 from %c to %c\n", src, dest);
    return;
  }
  hanoi(n-1, src, dest, aux);
  printf("Move disk %d from %c to %c\n", n, src, dest);
  hanoi(n-1, aux, src, dest);
}

This code prints the steps to move n disks from source to destination using auxiliary.

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Recursive Call	Visual State
1	Move disk 1	1	A	C	No	[A:3,2] [B:] [C:1]
2	Move disk 2	2	A	B	Yes	[A:3] [B:2] [C:1]
3	Move disk 1	1	C	B	No	[A:3] [B:2,1] [C:]
4	Move disk 3	3	A	C	No	[A:] [B:2,1] [C:3]
5	Move disk 1	1	B	A	No	[A:1] [B:2] [C:3]
6	Move disk 2	2	B	C	Yes	[A:1] [B:] [C:3,2]
7	Move disk 1	1	A	C	No	[A:] [B:] [C:3,2,1]
8	All disks moved	3	-	-	No	[A:] [B:] [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	Final
Peg A	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]	[]
Peg B	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]	[]
Peg C	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]	[3,2,1]

Key Moments - 3 Insights

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

Because the largest disk can only be moved when the smaller disks above it are out of the way, as shown in steps 1-3 in the execution_table.

Why do we use recursion twice in the function?

The first recursion moves n-1 disks to auxiliary peg, and the second moves them from auxiliary to destination after moving the largest disk, as seen in steps 2 and 6.

How do we know when the recursion stops?

When n equals 1, the base case is reached and a single disk is moved directly, as in step 1 and other single disk moves.

Visual Quiz - 3 Questions

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

A Step 3

B Step 6

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 Peg B after Step 3?

A [2,1]

B [2]

C []

D [3]

💡 Hint

Look at the Peg B row and the 'After Step 3' column 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 stay the same

B It would increase exponentially

C It would double

D It would decrease

💡 Hint

Recall Tower of Hanoi requires 2^n - 1 moves; increasing disks increases steps exponentially.

Concept Snapshot

Tower of Hanoi moves n disks from Source to Destination using Auxiliary.
Move n-1 disks to Auxiliary,
Move largest disk to Destination,
Move n-1 disks from Auxiliary to Destination.
Base case: move single disk directly.
Total moves: 2^n - 1.

Full Transcript

The Tower of Hanoi problem moves disks between three pegs following rules: only one disk at a time, larger disks cannot be placed on smaller disks. The recursive solution moves n-1 disks to auxiliary peg, then moves the largest disk to destination, then moves n-1 disks from auxiliary to destination. The base case moves a single disk directly. The execution table shows each move step-by-step, and the variable tracker shows peg states after each step. This helps visualize how disks shift between pegs until all are moved to the destination peg.

Practice

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

easy

A. 6

B. 5

C. 9

D. 7

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 D

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 recursive function signature in C for solving Tower of Hanoi?

easy

A. void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod);

B. int towerOfHanoi(int n, char from_rod, char to_rod);

C. void towerOfHanoi(int n, int from_rod, int to_rod);

D. void towerOfHanoi(int n, char from_rod, char to_rod);

Solution

1. Step 1: Identify parameters needed for Tower of Hanoi

   We need number of disks and names of three rods: source, destination, auxiliary.

2. Step 2: Check function signature matching these parameters

   void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod); has int n and three char rods, matching the problem requirements.

3. Final Answer:

   void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod); -> Option A

4. Quick Check:

   Function needs 3 rods and disk count [OK]

Hint: Tower of Hanoi needs 3 rods as parameters [OK]

Common Mistakes:

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

3. What will be the output of the following C code snippet for Tower of Hanoi with 2 disks?

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
  if (n == 1) {
    printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
    return;
  }
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
  printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

int main() {
  towerOfHanoi(2, 'A', 'C', 'B');
  return 0;
}

medium

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

B. 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

C. 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

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

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: Match output with options

   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 matches the exact sequence of moves printed by the code.

3. Final Answer:

   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 -> Option C

4. Quick Check:

   Recursive moves for 2 disks = 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 [OK]

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

Common Mistakes:

• Swapping auxiliary and destination rods
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in the following Tower of Hanoi C function and select the correct fix:

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
  if (n == 0) {
    return;
  }
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
  printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

medium

A. Change base case condition to if (n == 1) instead of if (n == 0)

B. Add else before recursive calls

C. Change printf to print n-1 instead of n

D. Swap aux_rod and to_rod in recursive calls

Solution

1. Step 1: Analyze base case condition

   Base case should stop recursion when n == 1, not 0, to print the last move.

2. Step 2: Understand effect of current base case

   With n == 0, no moves are printed for the smallest disk, causing no output.

3. Final Answer:

   Change base case condition to if (n == 1) instead of if (n == 0) -> Option A

4. Quick Check:

   Base case must be n == 1 to print moves [OK]

Hint: Base case must be n == 1 to print last move [OK]

Common Mistakes:

• Using n == 0 as base case
• Changing print statement unnecessarily
• Swapping rods incorrectly

5. You want to solve Tower of Hanoi for 4 disks but print only the moves where disk 1 is moved. Which modification to the recursive function is correct?

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
  if (n == 1) {
    printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
    return;
  }
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
  printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

hard

A. Remove all recursive calls except for n == 1 case

B. Add condition to print only if n == 1 inside the function

C. Print all moves but filter disk 1 moves outside the function

D. Change base case to n == 0 and print only disk 1 moves

Solution

1. Step 1: Understand requirement to print only disk 1 moves

   We must print moves only when disk number is 1 inside the recursive function.

2. Step 2: Modify print statements accordingly

   Keep recursive calls intact but print only when n == 1, skipping other prints.

3. Final Answer:

   Add condition to print only if n == 1 inside the function -> Option B

4. Quick Check:

   Print condition inside recursion for disk 1 only [OK]

Hint: Print moves only when disk number is 1 inside recursion [OK]

Common Mistakes:

• Removing recursive calls breaks solution
• Filtering outside loses recursion context
• Changing base case incorrectly