Tower of Hanoi Problem in DSA Rust

Mental Model

Move a stack of disks from one peg to another, one disk at a time, never placing a bigger disk on a smaller one.

Analogy: Imagine moving a stack of different-sized plates from one table to another using a third empty table, moving only one plate at a time and never putting a bigger plate on a smaller one.

Peg A: [3, 2, 1]
Peg B: []
Peg C: []
(3 is largest disk at bottom, 1 is smallest at top)

Dry Run Walkthrough

Input: 3 disks on Peg A, move all to Peg C using Peg B

Goal: Move all disks from Peg A to Peg C following the rules

Step 1: Move disk 1 from Peg A to Peg C

Peg A: [3, 2]
Peg B: []
Peg C: [1]

Why: Start by moving the smallest disk to the target peg

Step 2: Move disk 2 from Peg A to Peg B

Peg A: [3]
Peg B: [2]
Peg C: [1]

Why: Free the largest disk by moving the middle disk to the helper peg

Step 3: Move disk 1 from Peg C to Peg B

Peg A: [3]
Peg B: [2, 1]
Peg C: []

Why: Place the smallest disk on top of the middle disk on helper peg

Step 4: Move disk 3 from Peg A to Peg C

Peg A: []
Peg B: [2, 1]
Peg C: [3]

Why: Move the largest disk to the target peg

Step 5: Move disk 1 from Peg B to Peg A

Peg A: [1]
Peg B: [2]
Peg C: [3]

Why: Free the middle disk by moving the smallest disk back to the start peg

Step 6: Move disk 2 from Peg B to Peg C

Peg A: [1]
Peg B: []
Peg C: [3, 2]

Why: Move the middle disk to the target peg on top of the largest disk

Step 7: Move disk 1 from Peg A to Peg C

Peg A: []
Peg B: []
Peg C: [3, 2, 1]

Why: Finally, move the smallest disk to the target peg on top of all disks

Result:

Peg A: []
Peg B: []
Peg C: [3, 2, 1]
All disks moved to Peg C in correct order

Annotated Code

DSA Rust

fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) {
    if n == 1 {
        println!("Move disk 1 from Peg {} to Peg {}", from, to);
        return;
    }
    tower_of_hanoi(n - 1, from, aux, to); // move n-1 disks to aux peg
    println!("Move disk {} from Peg {} to Peg {}", n, from, to); // move largest disk to target peg
    tower_of_hanoi(n - 1, aux, to, from); // move n-1 disks from aux to target peg
}

fn main() {
    let n = 3;
    println!("Starting Tower of Hanoi with {} disks", n);
    tower_of_hanoi(n, 'A', 'C', 'B');
}

if n == 1 {

base case: move the smallest disk directly

tower_of_hanoi(n - 1, from, aux, to);

move top n-1 disks to auxiliary peg

println!("Move disk {} from Peg {} to Peg {}", n, from, to);

move the largest disk to target peg

tower_of_hanoi(n - 1, aux, to, from);

move n-1 disks from auxiliary peg to target peg

Output

Starting Tower of Hanoi with 3 disks

Move disk 1 from Peg A to Peg C

Move disk 2 from Peg A to Peg B

Move disk 1 from Peg C to Peg B

Move disk 3 from Peg A to Peg C

Move disk 1 from Peg B to Peg A

Move disk 2 from Peg B to Peg C

Move disk 1 from Peg A to Peg C

Complexity Analysis

Time: O(2^n) because each disk move doubles the number of moves needed

Space: O(n) due to recursion call stack depth equal to number of disks

vs Alternative: No simpler approach exists; this is the minimal number of moves required

Edge Cases

n = 1 (only one disk)

Directly move the single disk from source to target

DSA Rust

if n == 1 {

n = 0 (no disks)

No moves are made; function returns immediately

DSA Rust

if n == 0 { return; }

When to Use This Pattern

When you see a problem about moving disks or items between pegs with size constraints, use the Tower of Hanoi pattern because it solves the problem with minimal moves using recursion.

Common Mistakes

Mistake: Trying to move more than one disk at once or placing a bigger disk on a smaller disk
Fix: Always move only one disk at a time and never place a bigger disk on a smaller disk

Mistake: Not correctly swapping the roles of pegs in recursive calls
Fix: Carefully pass the pegs in the correct order to recursive calls to maintain rules

Summary

It moves disks between pegs following rules to solve the Tower of Hanoi puzzle.

Use it when you need to move stacked items with size constraints recursively.

The key is breaking the problem into moving smaller stacks using recursion.

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