Tower of Hanoi Problem in DSA Rust - Build from Scratch

Tower of Hanoi Problem

📖 Scenario: Imagine you have three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest at the top, making a conical shape.Your task is to move the entire stack to another rod, obeying the following simple rules:Only one disk can be moved at a time.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.No disk may be placed on top of a smaller disk.

🎯 Goal: You will write a Rust program that prints the steps to solve the Tower of Hanoi problem for 3 disks. The program will show which disk moves from which rod to which rod, step by step.

📋 What You'll Learn

Create a variable to hold the number of disks (3).

Create a function called tower_of_hanoi that takes the number of disks and names of source, auxiliary, and destination rods.

Use recursion inside tower_of_hanoi to print the moves.

Print the moves in the format: Move disk X from rod Y to rod Z.

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion, a key concept in programming and problem solving.

💼 Career

Recursion is used in many software engineering tasks like parsing, searching, and algorithm design.

1

Set up the number of disks

Create a variable called num_disks and set it to 3.

DSA Rust

# Create a variable called num_disks and set it to 3
# Your code here

Hint

Use let num_disks = 3; inside the main function.

2

Define the Tower of Hanoi function

Define a function called tower_of_hanoi that takes four parameters: n: u32, source: &str, auxiliary: &str, and destination: &str. The function should have no return value.

DSA Rust

fn main() {
    let num_disks = 3u32;
}

// Define the tower_of_hanoi function here
// Your code here

Hint

Write the function signature exactly as fn tower_of_hanoi(n: u32, source: &str, auxiliary: &str, destination: &str).

3

Implement the recursive logic

Inside the tower_of_hanoi function, write the recursive logic: if n == 1, print Move disk 1 from rod {source} to rod {destination}. Otherwise, call tower_of_hanoi(n - 1, source, auxiliary, destination), then print Move disk {n} from rod {source} to rod {destination}, then call tower_of_hanoi(n - 1, auxiliary, source, destination).

DSA Rust

fn main() {
    let num_disks = 3u32;
}

fn tower_of_hanoi(n: u32, source: &str, auxiliary: &str, destination: &str) {
    // Add recursive logic here
    // Your code here
}

Hint

Use if n == 1 to print the move directly. Otherwise, use recursion to move disks step by step.

4

Call the function and print the moves

Inside the main function, call tower_of_hanoi(num_disks, "A", "B", "C") to print the steps to move disks from rod A to rod C using rod B as auxiliary.

DSA Rust

fn main() {
    let num_disks = 3u32;
    // Call tower_of_hanoi here
    // Your code here
}

fn tower_of_hanoi(n: u32, source: &str, auxiliary: &str, destination: &str) {
    if n == 1 {
        println!("Move disk 1 from rod {} to rod {}", source, destination);
    } else {
        tower_of_hanoi(n - 1, source, auxiliary, destination);
        println!("Move disk {} from rod {} to rod {}", n, source, destination);
        tower_of_hanoi(n - 1, auxiliary, source, destination);
    }
}

Hint

Call tower_of_hanoi(num_disks, "A", "B", "C") inside main to start printing the moves.

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