N Queens Problem in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of N Queens Board Representation

What is the printed board state after placing queens for N=4 in the given Rust code?

DSA Rust

fn print_board(board: &Vec<Vec<char>>) {
    for row in board {
        for &cell in row {
            print!("{} ", cell);
        }
        println!();
    }
}

fn main() {
    let board = vec![
        vec!['.', 'Q', '.', '.'],
        vec!['.', '.', '.', 'Q'],
        vec!['Q', '.', '.', '.'],
        vec!['.', '.', 'Q', '.'],
    ];
    print_board(&board);
}

A

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

B

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

C

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

D

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

💡 Hint

Look carefully at the positions of 'Q' in each row vector.

The board is printed row by row, each cell separated by a space. The given board matches option A exactly.

🧠 Conceptual

intermediate

Number of Solutions for N=1 and N=2

How many distinct solutions exist for the N Queens problem when N=1 and N=2 respectively?

A N=1: 1 solution, N=2: 0 solutions

B N=1: 0 solutions, N=2: 1 solution

C N=1: 1 solution, N=2: 1 solution

D N=1: 0 solutions, N=2: 0 solutions

💡 Hint

Try placing queens on a 1x1 and 2x2 board and see if they can avoid attacking each other.

For N=1, placing one queen on the single cell is a valid solution. For N=2, no arrangement exists where two queens do not attack each other.

🔧 Debug

advanced

Identify the Error in the Rust Backtracking Function

What error will this Rust function cause when solving N Queens for N=4? fn is_safe(board: &Vec>, row: usize, col: usize) -> bool { for i in 0..col { if board[row][i] == 'Q' { 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] == 'Q' { return false; } i -= 1; j -= 1; } let mut i2 = row as i32; let mut j2 = col as i32; while i2 < board.len() as i32 && j2 >= 0 { if board[i2 as usize][j2 as usize] == 'Q' { return false; } i2 += 1; j2 -= 1; } true }

A Index out of bounds panic when i or j goes negative

B Compilation error due to mutable variable redeclaration

C Infinite loop due to i and j not updating

D Logical error: does not check column for queens

💡 Hint

Look at how variables i and j are declared twice with let mut in the same scope.

In Rust, redeclaring variables with let mut in the same scope causes a compilation error. The second let mut i and j redeclaration is invalid.

🚀 Application

advanced

Count Solutions for N=5 Using Backtracking

What is the total number of distinct solutions for the N Queens problem when N=5?

A 5

B 12

C 8

D 10

💡 Hint

Try to recall or compute the number of solutions for N=5 from known results.

The known number of distinct solutions for N=5 is 10.

🧠 Conceptual

expert

Time Complexity of N Queens Backtracking Algorithm

What is the approximate time complexity of the backtracking algorithm for solving the N Queens problem?

A O(N^2)

B O(2^N)

C O(N!)

D O(N^N)

💡 Hint

Consider how many ways queens can be placed row by row without conflicts.

The backtracking algorithm tries to place queens row by row, pruning invalid positions. The worst-case complexity is roughly factorial in N, O(N!).

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