N Queens Problem in DSA Rust

Mental Model

Place N queens on an NxN chessboard so that no two queens attack each other. We try positions row by row, backtracking when conflicts arise.

Analogy: Imagine seating N guests at a square table with N seats per side, where no guest can sit where they can see another guest directly across or diagonally. You try seating one guest at a time, and if a conflict happens, you move them to a different seat or backtrack to change previous seats.

Board (4x4 example):
. . . .
. . . .
. . . .
. . . .

'.' means empty cell
'Q' means queen placed

Initial empty board:
. . . .
. . . .
. . . .
. . . .

Dry Run Walkthrough

Input: N=4, place 4 queens on 4x4 board

Goal: Find one valid arrangement where 4 queens do not attack each other

Step 1: Place queen at row 0, column 0

Q . . .
. . . .
. . . .
. . . .

Why: Start placing first queen in first row, first column

Step 2: Try placing queen at row 1, column 0 -- conflict with queen at (0,0), so skip

Q . . .
. . . .
. . . .
. . . .

Why: Queens cannot share same column

Step 3: Place queen at row 1, column 1 -- conflict diagonally with (0,0), skip

Q . . .
. . . .
. . . .
. . . .

Why: Queens cannot attack diagonally

Step 4: Place queen at row 1, column 2 -- no conflict, place queen

Q . . .
. . Q .
. . . .
. . . .

Why: Safe position found for second queen

Step 5: Try placing queen at row 2, column 0 -- conflict with (0,0), skip

Q . . .
. . Q .
. . . .
. . . .

Why: Same column conflict

Step 6: Try placing queen at row 2, column 1 -- conflict diagonally with (1,2), skip

Q . . .
. . Q .
. . . .
. . . .

Why: Diagonal conflict

Step 7: Place queen at row 2, column 3 -- no conflict, place queen

Q . . .
. . Q .
. . . Q
. . . .

Why: Safe position found for third queen

Step 8: Try placing queen at row 3, column 0 -- conflict with (0,0), skip

Q . . .
. . Q .
. . . Q
. . . .

Why: Same column conflict

Step 9: Try placing queen at row 3, column 1 -- no conflict, place queen

Q . . .
. . Q .
. . . Q
. Q . .

Why: Safe position found for fourth queen

Result:

Q . . .
. . Q .
. . . Q
. Q . .

One valid solution found

Annotated Code

DSA Rust

fn is_safe(board: &Vec<Vec<char>>, row: usize, col: usize, n: usize) -> bool {
    // Check column for conflicts
    for i in 0..row {
        if board[i][col] == 'Q' {
            return false;
        }
    }
    // Check upper left diagonal
    let mut i = row as i32 - 1;
    let mut j = col as i32 - 1;
    while i >= 0 && j >= 0 {
        if board[i as usize][j as usize] == 'Q' {
            return false;
        }
        i -= 1;
        j -= 1;
    }
    // Check upper right diagonal
    let mut i = row as i32 - 1;
    let mut j = col as i32 + 1;
    while i >= 0 && j < n as i32 {
        if board[i as usize][j as usize] == 'Q' {
            return false;
        }
        i -= 1;
        j += 1;
    }
    true
}

fn solve_n_queens_util(board: &mut Vec<Vec<char>>, row: usize, n: usize) -> bool {
    if row == n {
        return true; // All queens placed
    }
    for col in 0..n {
        if is_safe(board, row, col, n) {
            board[row][col] = 'Q'; // Place queen
            if solve_n_queens_util(board, row + 1, n) {
                return true; // Found valid placement
            }
            board[row][col] = '.'; // Backtrack
        }
    }
    false
}

fn print_board(board: &Vec<Vec<char>>, n: usize) {
    for i in 0..n {
        for j in 0..n {
            print!("{} ", board[i][j]);
        }
        println!();
    }
}

fn main() {
    let n = 4;
    let mut board = vec![vec!['.'; n]; n];
    if solve_n_queens_util(&mut board, 0, n) {
        print_board(&board, n);
    } else {
        println!("No solution found");
    }
}

for col in 0..n {

try placing queen in each column of current row

if is_safe(board, row, col, n) {

check if placing queen here causes no conflicts

board[row][col] = 'Q';

place queen at safe position

if solve_n_queens_util(board, row + 1, n) {

recurse to place queen in next row

board[row][col] = '.';

backtrack by removing queen if next placement fails

Output

Q . . . 

. . Q . 

. . . Q 

. Q . . 

Complexity Analysis

Time: O(N!) because each row tries N columns and backtracks, pruning invalid branches

Space: O(N^2) for the board storage and O(N) recursion stack for rows

vs Alternative: Brute force tries all N^N placements, but backtracking reduces this drastically by pruning invalid partial solutions

Edge Cases

N=1 (smallest board)

Places single queen successfully without conflicts

DSA Rust

if row == n { return true; }

N=2 or N=3 (no solutions exist)

Backtracking tries all placements and returns no solution

DSA Rust

if solve_n_queens_util(board, row + 1, n) { return true; }

Empty board initialization

Board is initialized with '.' indicating empty cells

DSA Rust

let mut board = vec![vec!['.'; n]; n];

When to Use This Pattern

When you see a problem asking to place items on a grid with constraints and no conflicts, use backtracking to try positions row by row and backtrack on conflicts.

Common Mistakes

Mistake: Not checking all three directions (column, upper left diagonal, upper right diagonal) for conflicts
Fix: Add checks for column and both diagonals before placing a queen

Mistake: Not backtracking properly by resetting the cell after failed recursive calls
Fix: Reset the board cell to '.' after recursive call returns false

Summary

Places N queens on an NxN board so no two queens attack each other using backtracking.

Use when you need to find valid arrangements under constraints with pruning to avoid brute force.

Try placing queens row by row, check conflicts, and backtrack when stuck.

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