Tower of Hanoi Problem in DSA Rust - 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 in order

The problem moves disks step-by-step using recursion: move smaller stacks to auxiliary, move largest disk, then move smaller stacks to destination.

Execution Sample

DSA Rust

fn hanoi(n: u32, src: char, aux: char, dst: char) {
    if n == 1 {
        println!("Move disk 1 from {} to {}", src, dst);
    } else {
        hanoi(n-1, src, aux, dst);
        println!("Move disk {} from {} to {}", n, src, dst);
        hanoi(n-1, aux, dst, src);
    }
}

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

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Aux Peg	Visual State
1	Move disk 1	1	A	C	B	A: [3,2], B: [], C: [1]
2	Move disk 2	2	A	B	C	A: [3], B: [2], C: [1]
3	Move disk 1	1	C	B	A	A: [3], B: [2,1], C: []
4	Move disk 3	3	A	C	B	A: [], B: [2,1], C: [3]
5	Move disk 1	1	B	A	C	A: [1], B: [2], C: [3]
6	Move disk 2	2	B	C	A	A: [1], B: [], C: [3,2]
7	Move disk 1	1	A	C	B	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
A (Source Peg)	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]
B (Aux Peg)	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]
C (Destination Peg)	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]
Current Disk Moved	None	1	2	1	3	1	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 move of the largest disk always in the middle of the recursion?

Because after moving n-1 disks away, the largest disk can safely move to destination (step 4), then smaller disks move on top (steps 5-7).

How does the visual state help understand the problem?

It shows the exact disks on each peg after each move, helping track progress and verify rules are followed (see Visual State column).

Visual Quiz - 3 Questions

Look at the execution_table, what disks are on peg B after step 3?

A [3]

B [2,1]

C []

D [1]

💡 Hint

Check the Visual State column in row for step 3.

At which step is the largest disk moved from peg A to peg C?

A Step 4

B Step 5

C Step 3

D Step 7

💡 Hint

Look for the operation 'Move disk 3' in the Operation column.

If we had only 2 disks, how many steps would the solution take?

A 4

B 2

C 3

D 1

💡 Hint

Recall the pattern: minimum moves = 2^n - 1; check variable_tracker for n=3 steps.

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
- Minimum moves = 2^n - 1
- Recursive solution prints each move step-by-step

Full Transcript

The Tower of Hanoi problem moves disks from one peg to another following rules: only one disk moves at a time, and no disk can be placed on a smaller disk. The recursive solution moves n-1 disks to an auxiliary peg, moves the largest disk to the destination, then moves the n-1 disks from auxiliary to destination. The execution table shows each move with the disks on each peg. The variable tracker shows peg states after each step. Key moments clarify why the largest disk moves in the middle and how the visual state helps. The quiz tests understanding of peg states and move counts. The snapshot summarizes the recursive approach and minimum moves formula.

Practice

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

easy

A. 7

B. 6

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 A

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Calculating 2*n - 1 instead of 2^n - 1
• Confusing number of disks with moves
• Choosing the next integer after 7

2. Which of the following Rust function signatures correctly represents the Tower of Hanoi recursive function for moving disks?

easy

A. fn tower_of_hanoi(n: i32, from: String, to: String)

B. fn tower_of_hanoi(n: u32, from: char, to: char, aux: char)

C. fn tower_of_hanoi(n: u32, from: i32, to: i32, aux: i32)

D. fn tower_of_hanoi(n: u32, from: char, to: char)

Solution

1. Step 1: Identify correct parameter types

   The function needs number of disks (u32) and three rods (chars) to represent pegs.

2. Step 2: Check function signature options

   fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) uses u32 for disks and char for rods, matching common Tower of Hanoi implementations.

3. Final Answer:

   fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) -> Option B

4. Quick Check:

   Correct parameter types and count [OK]

Hint: Use u32 for disks and char for rods in signature [OK]

Common Mistakes:

• Using String instead of char for rods
• Missing auxiliary rod parameter
• Using signed integer for disk count

3. What will be the output sequence of moves for the Tower of Hanoi function call tower_of_hanoi(2, 'A', 'C', 'B')?

medium

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

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

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

Solution

1. Step 1: Understand the recursive steps for 2 disks

   Move disk 1 from source to auxiliary, move disk 2 from source to target, then move disk 1 from auxiliary to target.

2. Step 2: Apply to given rods

   From 'A' to 'B' (aux), then 'A' to 'C' (target), then 'B' to 'C' (target).

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 C

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: For 2 disks, move small to aux, big to target, small to target [OK]

Common Mistakes:

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

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

fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) {
    if n == 0 {
        return;
    }
    tower_of_hanoi(n - 1, from, to, aux);
    println!("Move disk {} from {} to {}", n, from, to);
    tower_of_hanoi(n - 1, aux, to, from);
}

medium

A. The recursive calls have incorrect rod parameters swapped

B. The println! macro syntax is incorrect

C. The function does not return any value but should return an integer

D. The base case should be n == 1, not n == 0

Solution

1. Step 1: Recall standard Tower of Hanoi recursion

   To move n disks from src to dst using aux: move n-1 src->aux using dst; move n src->dst; move n-1 aux->dst using src.

2. Step 2: Check first recursive call

   Code has tower_of_hanoi(n-1, from, to, aux); but should be tower_of_hanoi(n-1, from, aux, to); dst and aux swapped in first call.

3. Step 3: Other parts correct

   Base case n==0 fine for u32; println! syntax correct; second recursive call correct.

4. Final Answer:

   The recursive calls have incorrect rod parameters swapped -> Option A

5. Quick Check:

   First call: dst/aux swapped [OK]

Hint: Check order of rods in recursive calls carefully [OK]

Common Mistakes:

• Confusing base case condition
• Mixing up source, target, auxiliary rods
• Expecting return value in void function

5. You want to solve the Tower of Hanoi problem for 4 disks but only have 2 rods available. What is the minimum number of moves required?

hard

A. 15

B. 31

C. 7

D. Impossible to solve with 2 rods

Solution

1. Step 1: Understand Tower of Hanoi rod requirements

   The classic Tower of Hanoi problem requires 3 rods to move disks following the rules.

2. Step 2: Check if 2 rods suffice

   With only 2 rods, it is impossible to move all disks without breaking the rules (no larger disk on smaller disk).

3. Final Answer:

   Impossible to solve with 2 rods -> Option D

4. Quick Check:

   Minimum rods needed = 3 [OK]

Hint: Tower of Hanoi needs 3 rods; 2 rods can't solve it [OK]

Common Mistakes:

• Applying formula 2^n - 1 without checking rods
• Assuming fewer rods still work
• Confusing rods with disks