Tower of Hanoi Problem in DSA C++ - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with n 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: move top n-1 disks to auxiliary, move largest disk to destination, then move n-1 disks from auxiliary to destination.

Execution Sample

DSA C++

void towerOfHanoi(int n, char source, char dest, char aux) {
  if (n == 1) {
    std::cout << "Move disk 1 from " << source << " to " << dest << std::endl;
    return;
  }
  towerOfHanoi(n-1, source, aux, dest);
  std::cout << "Move disk " << n << " from " << source << " to " << dest << std::endl;
  towerOfHanoi(n-1, aux, dest, source);
}

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

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Visual State
1	Move disk 1	1	A	C	A: [3,2] B: [] C: [1]
2	Move disk 2	2	A	B	A: [3] B: [2] C: [1]
3	Move disk 1	1	C	B	A: [3] B: [2,1] C: []
4	Move disk 3	3	A	C	A: [] B: [2,1] C: [3]
5	Move disk 1	1	B	A	A: [1] B: [2] C: [3]
6	Move disk 2	2	B	C	A: [1] B: [] C: [3,2]
7	Move disk 1	1	A	C	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
Peg A	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[]	[]
Peg B	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]
Peg C	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]

Key Moments - 3 Insights

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

Because the largest disk cannot be placed on a smaller disk, so we clear the top n-1 disks to the auxiliary peg first (see steps 1-3 in execution_table).

Why do we move disks back to the destination peg after moving the largest disk?

After moving the largest disk, the n-1 disks on auxiliary must be moved to destination to complete the puzzle (see steps 5-7 in execution_table).

How does the visual state help understand the moves?

It shows the exact disks on each peg after each move, making it clear how disks shift without breaking rules.

Visual Quiz - 3 Questions

Look at the execution_table, after which step is disk 3 moved for the first time?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Check the 'Operation' and 'Disks Moved' columns for disk 3 moves.

At which step does Peg B become empty again after holding disks?

A Step 7

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Peg B' row in variable_tracker for when it becomes empty.

If we had 2 disks instead of 3, how many total steps would the execution_table show?

A 4

B 5

C 3

D 7

💡 Hint

Recall the formula 2^n - 1 steps; check the number of rows for 3 disks.

Concept Snapshot

Tower of Hanoi:
- Move 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
- Total moves = 2^n - 1
- Recursive solution with base case n=1

Full Transcript

The Tower of Hanoi problem moves disks from one peg to another following size rules. The recursive solution moves n-1 disks to auxiliary peg, moves the largest disk to destination, then moves n-1 disks from auxiliary to destination. The execution table shows each move step with disks moved and peg states. Variable tracker shows peg contents after each step. Key moments clarify why n-1 disks move first and how visual states help. Quiz questions test understanding of steps and peg states.

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 base case condition in the Tower of Hanoi recursive function in C++?

easy

A. if (n == 1) move disk from source to destination;

B. if (n == 0) return;

C. if (n > 1) call recursive function;

D. if (n < 0) return;

Solution

1. Step 1: Identify the base case for recursion

   The base case is when there is only 1 disk to move, so move it directly.

2. Step 2: Check the options

   if (n == 1) move disk from source to destination; correctly states the base case: if (n == 1) move disk from source to destination.

3. Final Answer:

   if (n == 1) move disk from source to destination; -> Option A

4. Quick Check:

   Base case is n == 1 [OK]

Hint: Base case moves single disk directly [OK]

Common Mistakes:

• Using n == 0 as base case
• Not defining a base case
• Using incorrect condition like n < 0

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

medium

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

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

Solution

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

   Move top disk (1) from A to B, move bottom disk (2) from A to C, then move disk (1) from B to C.

2. Step 2: Match the sequence with options

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C matches the correct sequence exactly.

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 B

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: For 2 disks: move top to aux, bottom to dest, top to dest [OK]

Common Mistakes:

• Swapping auxiliary and destination pegs
• Moving larger disk before smaller disk
• Incorrect move order

4. Identify the error in the following Tower of Hanoi recursive function snippet in C++:

void towerOfHanoi(int n, char source, char aux, char dest) {
  if (n == 1) {
    cout << "Move disk 1 from " << source << " to " << dest << endl;
    return;
  }
  towerOfHanoi(n - 1, source, dest, aux);
  cout << "Move disk " << n << " from " << source << " to " << dest << endl;
  towerOfHanoi(n - 1, aux, source, dest);
}

medium

A. The order of auxiliary and destination pegs is swapped in recursive calls.

B. Base case condition should be n == 0 instead of n == 1.

C. The function does not print the moves correctly.

D. The function lacks a return statement after recursive calls.

Solution

1. Step 1: Analyze recursive calls parameters

   The first recursive call should move n-1 disks from source to auxiliary using destination as auxiliary, so parameters should be (n-1, source, dest, aux).

2. Step 2: Identify incorrect parameter order

   In the code, the first call uses (n-1, source, aux, dest) which swaps aux and dest incorrectly.

3. Final Answer:

   The order of auxiliary and destination pegs is swapped in recursive calls. -> Option A

4. Quick Check:

   Correct peg order is crucial in recursion [OK]

Hint: Check peg order in recursive calls carefully [OK]

Common Mistakes:

• Swapping auxiliary and destination pegs
• Wrong base case condition
• Missing return statements

5. If the Tower of Hanoi problem is modified to have 4 pegs instead of 3, which of the following statements is true about the minimum number of moves required to move n disks?

hard

A. It remains the same as 3 pegs: 2^n - 1 moves.

B. It is always more than 2^n - 1 moves due to extra peg.

C. It is always less than 2^n - 1 moves but no exact formula is known.

D. It is exactly n^2 moves for any n.

Solution

1. Step 1: Understand the classic formula for 3 pegs

   For 3 pegs, minimum moves = 2^n - 1.

2. Step 2: Consider 4 pegs case

   With 4 pegs, the problem is more complex; fewer moves than 2^n - 1 are possible but no simple closed formula exists.

3. Final Answer:

   It is always less than 2^n - 1 moves but no exact formula is known. -> Option C

4. Quick Check:

   4 pegs reduce moves but formula unknown [OK]

Hint: More pegs reduce moves but no simple formula [OK]

Common Mistakes:

• Assuming formula 2^n - 1 applies to 4 pegs
• Thinking more pegs increase moves
• Assuming quadratic moves for 4 pegs