N Queens Problem in DSA Rust - Build from Scratch

N Queens Problem

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

The N Queens problem is a classic example of constraint satisfaction problems used in AI and puzzle solving.

💼 Career

Understanding backtracking and safe placement checks is useful in algorithm design, game development, and solving complex search problems.

1

Create the board vector

Create a mutable vector called board of length 4 with all values set to None. This vector will hold the column positions of queens for each row.

DSA Rust

# Create a mutable vector called board with 4 None values
# Your code here

Hint

Use vec![None; 4] to create a vector with 4 empty spots for queens.

2

Add board size variable

Create a variable called n and set it to 4 to represent the size of the chessboard.

DSA Rust

let mut board: Vec> = vec![None; 4];
// Create a variable n and set it to 4
# Your code here

Hint

Just write let n = 4; below the board vector.

3

Write the safe placement check function

Write a function called is_safe that takes board: &Vec>, row: usize, and col: usize and returns bool. It should return true if placing a queen at (row, col) does not conflict with previously placed queens.

DSA Rust

let mut board: Vec> = vec![None; 4];
let n = 4;

// Write is_safe function to check if queen can be placed safely
# Your code here

Hint

Check columns and diagonals by comparing current position with all previous rows' queen positions.

4

Implement backtracking and print the board

Write a recursive function called solve that takes board: &mut Vec> and row: usize. It tries to place queens row by row using is_safe. When all queens are placed, print the board with 'Q' for queens and '.' for empty spaces. Call solve(&mut board, 0) in main.

DSA Rust

let mut board: Vec> = vec![None; 4];
let n = 4;

fn is_safe(board: &Vec>, row: usize, col: usize) -> bool {
    for prev_row in 0..row {
        if let Some(prev_col) = board[prev_row] {
            if prev_col == col ||
               prev_col + prev_row == col + row ||
               prev_col + row == col + prev_row {
                return false;
            }
        }
    }
    true
}

// Write solve function and call it in main
# Your code here

Hint

Use recursion to try each column in the current row. If safe, place queen and move to next row. If stuck, backtrack.

Print the board when all queens are placed.

Practice

1. What is the main goal of the N Queens Problem?

easy

A. Place queens only on the diagonal cells

B. Place N queens on an NxN chessboard so that no two queens attack each other

C. Move queens to the center of the board

D. Count the total number of queens on a chessboard

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing N queens on an NxN board so that no two queens threaten each other.

2. Step 2: Identify the correct goal

   Only Place N queens on an NxN chessboard so that no two queens attack each other correctly states this goal, while others describe unrelated tasks.

3. Final Answer:

   Place N queens on an NxN chessboard so that no two queens attack each other -> Option B

4. Quick Check:

   N Queens Problem = Place queens safely [OK]

Hint: Remember: no two queens can share row, column, or diagonal [OK]

Common Mistakes:

• Thinking queens can attack if placed on same diagonal only
• Confusing the problem with counting queens
• Assuming queens can share rows or columns

2. Which Rust syntax correctly declares a 2D vector to represent an NxN chessboard initialized with zeros?

easy

A. let board = vec![vec![0; n]; n];

B. let board = vec![0; n][vec![0; n]];

C. let board = vec![vec![n; 0]; n];

D. let board = vec![vec![0, n]; n];

Solution

1. Step 1: Understand Rust vector initialization

   To create a 2D vector with n rows and n columns filled with 0, use vec![vec![0; n]; n].

2. Step 2: Check each option

   let board = vec![vec![0; n]; n]; matches correct syntax; others have syntax errors or wrong order.

3. Final Answer:

   let board = vec![vec![0; n]; n]; -> Option A

4. Quick Check:

   2D vector init = vec![vec![0; n]; n] [OK]

Hint: Use vec![vec![value; cols]; rows] for 2D vectors [OK]

Common Mistakes:

• Using incorrect order of brackets
• Mixing values and sizes in vec! macro
• Trying to initialize with vec![0; n][vec![0; n]] which is invalid

3. What will be the output of the following Rust code snippet for n = 4?

fn is_safe(board: &Vec, row: usize, col: usize, n: usize) -> bool {
    for i in 0..col {
        if board[row][i] == 1 {
            return false;
        }
    }
    let mut i = row as i32;
    let mut j = col as i32;
    while i >= 0 && j >= 0 {
        if board[i as usize][j as usize] == 1 {
            return false;
        }
        i -= 1;
        j -= 1;
    }
    let mut i = row as i32;
    let mut j = col as i32;
    while i < n as i32 && j >= 0 {
        if board[i as usize][j as usize] == 1 {
            return false;
        }
        i += 1;
        j -= 1;
    }
    true
}

fn main() {
    let n = 4;
    let mut board = vec![vec![0; n]; n];
    board[1][0] = 1;
    println!("{}", is_safe(&board, 2, 1, n));
}

medium

A. true

B. Compilation error

C. Runtime panic

D. false

Solution

1. Step 1: Analyze the board and is_safe call

   Board has a queen at (1,0). We check if placing at (2,1) is safe.

2. Step 2: Check row, upper diagonal, and lower diagonal

   Row check: no queen in row 2 before col 1. Upper diagonal: (1,0) has queen, so is_safe returns false.

3. Final Answer:

   false -> Option D

4. Quick Check:

   Queen attacks on upper diagonal = false [OK]

Hint: Check all three directions: row, upper and lower diagonals [OK]

Common Mistakes:

• Ignoring diagonal checks
• Confusing row and column indices
• Assuming safe when queen is on diagonal

4. Identify the bug in this Rust function snippet for placing queens and suggest the fix:

fn solve_n_queens(board: &mut Vec, col: usize, n: usize) -> bool {
    if col >= n {
        return true;
    }
    for i in 0..n {
        if is_safe(board, i, col, n) {
            board[i][col] = 1;
            if solve_n_queens(board, col + 1, n) {
                return true;
            }
            board[i][col] = 0;
        }
    }
    false
}

medium

A. No bug; function is correct

B. Backtracking step resets board[i][col] incorrectly

C. Function should return false instead of true when col >= n

D. Missing base case for col == n

Solution

1. Step 1: Check base case correctness

   Base case returns true when col >= n, meaning all queens placed successfully.

2. Step 2: Verify backtracking logic

   Backtracking resets board[i][col] to 0 if deeper call fails, which is correct.

3. Final Answer:

   No bug; function is correct -> Option A

4. Quick Check:

   Backtracking logic and base case are correct [OK]

Hint: Backtracking resets state after failed recursive call [OK]

Common Mistakes:

• Removing or changing base case incorrectly
• Not resetting board cell during backtracking
• Returning wrong boolean values

5. Given the partial Rust code below, which modification will correctly print all distinct solutions for the N Queens Problem for n = 4?

fn solve_all(board: &mut Vec, col: usize, n: usize, solutions: &mut Vec>) {
    if col == n {
        solutions.push(board.clone());
        return;
    }
    for i in 0..n {
        if is_safe(board, i, col, n) {
            board[i][col] = 1;
            solve_all(board, col + 1, n, solutions);
            board[i][col] = 0;
        }
    }
}

fn main() {
    let n = 4;
    let mut board = vec![vec![0; n]; n];
    let mut solutions = Vec::new();
    solve_all(&mut board, 0, n, &mut solutions);
    // Which code snippet below correctly prints all solutions?
}

hard

A. for sol in solutions { println!("{}", sol); }

B. println!("{:?}", solutions);

C. for sol in &solutions { for row in sol { println!("{:?}", row); } println!("---"); }

D. for sol in &solutions { println!("{}", sol); }

Solution

1. Step 1: Understand solutions data structure

   solutions is a vector of boards, each board is Vec representing queen positions.

2. Step 2: Choose correct printing method

   for sol in &solutions { for row in sol { println!("{:?}", row); } println!("---"); } iterates over each solution and each row, printing rows clearly. Others print entire vectors directly or incorrectly.

3. Final Answer:

   for sol in &solutions { for row in sol { println!("{:?}", row); } println!("---"); } -> Option C

4. Quick Check:

   Iterate solutions and rows for clear output [OK]

Hint: Print each row of each solution separately for clarity [OK]

Common Mistakes:

• Printing entire vector at once causing unreadable output
• Not iterating by reference causing ownership errors
• Using {} instead of {:?} for vectors