N Queens Problem in DSA Rust - Time & Space Complexity

Time Complexity: N Queens Problem

O(n!)

Understanding Time Complexity

We want to understand how the time needed to solve the N Queens problem grows as the board size increases.

Specifically, how does the number of steps change when we try to place queens on larger boards?

Scenario Under Consideration

Analyze the time complexity of the following Rust code snippet.

fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
    fn backtrack(row: usize, n: usize, cols: &mut Vec<bool>, diag1: &mut Vec<bool>, diag2: &mut Vec<bool>, board: &mut Vec<String>, solutions: &mut Vec<Vec<String>>) {
        if row == n {
            solutions.push(board.clone());
            return;
        }
        for col in 0..n {
            let d1 = row + col;
            let d2 = n - 1 + row - col;
            if !cols[col] && !diag1[d1] && !diag2[d2] {
                cols[col] = true;
                diag1[d1] = true;
                diag2[d2] = true;
                board[row].replace_range(col..col+1, "Q");
                backtrack(row + 1, n, cols, diag1, diag2, board, solutions);
                board[row].replace_range(col..col+1, ".");
                cols[col] = false;
                diag1[d1] = false;
                diag2[d2] = false;
            }
        }
    }

    let mut solutions = Vec::new();
    let mut board = vec![".".repeat(n); n];
    let mut cols = vec![false; n];
    let mut diag1 = vec![false; 2 * n - 1];
    let mut diag2 = vec![false; 2 * n - 1];
    backtrack(0, n, &mut cols, &mut diag1, &mut diag2, &mut board, &mut solutions);
    solutions
}

This code tries to place queens row by row, checking columns and diagonals to avoid attacks, using backtracking.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive backtracking tries placing a queen in each column of the current row.
• How many times: For each row, it tries up to n columns, and recurses for the next row, leading to many combinations.

How Execution Grows With Input

As the board size n grows, the number of ways to place queens grows very fast because we try many column choices for each row.

Input Size (n)	Approx. Operations
4	~40 tries
8	~10,000 tries
12	Millions of tries

Pattern observation: The number of tries grows roughly like n factorial (n!), which means it grows very fast as n increases.

Final Time Complexity

Time Complexity: O(n!)

This means the time needed grows very fast, roughly like the number of ways to arrange n queens on the board without attacking each other.

Common Mistake

[X] Wrong: "The time grows like n squared because we just check rows and columns."

[OK] Correct: Actually, the algorithm tries many combinations by placing queens row by row, which leads to factorial growth, not just checking pairs.

Interview Connect

Understanding this problem's time complexity helps you explain why some problems need smart pruning or heuristics to solve efficiently.

Self-Check

"What if we added memoization to remember invalid board states? How would the time complexity change?"

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