1062: N-Queens

Difficulty: Advanced Category: Backtracking Concept: Place N queens on an N×N chessboard so no two attack each other Key Insight: Three constraint arrays (columns, main diagonals, anti-diagonals) enable O(1) conflict checking. The bitmask variant packs all three constraints into integers for the fastest solution.

// 1062: N-Queens — Backtracking

// Approach 1: Backtracking with boolean arrays for columns/diagonals
fn solve_n_queens(n: usize) -> Vec<Vec<usize>> {
    let mut solutions = Vec::new();
    let mut cols = vec![false; n];
    let mut diag1 = vec![false; 2 * n - 1]; // row - col + n - 1
    let mut diag2 = vec![false; 2 * n - 1]; // row + col
    let mut board = vec![0usize; n];

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

    place(0, n, &mut board, &mut cols, &mut diag1, &mut diag2, &mut solutions);
    solutions
}

// Approach 2: Functional style with Vec accumulation
fn solve_n_queens_func(n: usize) -> Vec<Vec<usize>> {
    fn is_safe(queens: &[usize], col: usize) -> bool {
        let row = queens.len();
        queens.iter().enumerate().all(|(i, &c)| {
            c != col && (row as i32 - i as i32).unsigned_abs() as usize != (col as i32 - c as i32).unsigned_abs() as usize
        })
    }

    fn solve(queens: &mut Vec<usize>, row: usize, n: usize, results: &mut Vec<Vec<usize>>) {
        if row == n {
            results.push(queens.clone());
            return;
        }
        for col in 0..n {
            if is_safe(queens, col) {
                queens.push(col);
                solve(queens, row + 1, n, results);
                queens.pop();
            }
        }
    }

    let mut results = Vec::new();
    let mut queens = Vec::new();
    solve(&mut queens, 0, n, &mut results);
    results
}

// Approach 3: Bitmask-based (fastest)
fn solve_n_queens_bits(n: usize) -> usize {
    fn count(row: usize, n: usize, cols: u32, diag1: u32, diag2: u32) -> usize {
        if row == n { return 1; }
        let mut total = 0;
        let available = ((1u32 << n) - 1) & !(cols | diag1 | diag2);
        let mut bits = available;
        while bits > 0 {
            let bit = bits & bits.wrapping_neg(); // lowest set bit
            total += count(row + 1, n, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1);
            bits &= bits - 1;
        }
        total
    }
    count(0, n, 0, 0, 0)
}

fn main() {
    let solutions = solve_n_queens(8);
    println!("8-Queens: {} solutions", solutions.len());
    println!("8-Queens (bits): {} solutions", solve_n_queens_bits(8));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_n_queens_4() {
        assert_eq!(solve_n_queens(4).len(), 2);
    }

    #[test]
    fn test_n_queens_8() {
        assert_eq!(solve_n_queens(8).len(), 92);
    }

    #[test]
    fn test_n_queens_func() {
        assert_eq!(solve_n_queens_func(4).len(), 2);
        assert_eq!(solve_n_queens_func(8).len(), 92);
    }

    #[test]
    fn test_n_queens_bits() {
        assert_eq!(solve_n_queens_bits(4), 2);
        assert_eq!(solve_n_queens_bits(8), 92);
    }
}

(* 1062: N-Queens — Backtracking *)

(* Approach 1: Backtracking with column/diagonal tracking *)
let solve_n_queens n =
  let solutions = ref [] in
  let cols = Array.make n false in
  let diag1 = Array.make (2 * n - 1) false in  (* row - col + n - 1 *)
  let diag2 = Array.make (2 * n - 1) false in  (* row + col *)
  let board = Array.make n 0 in  (* board.(row) = col of queen *)
  let rec place row =
    if row = n then
      solutions := Array.to_list board :: !solutions
    else
      for col = 0 to n - 1 do
        let d1 = row - col + n - 1 in
        let d2 = row + col in
        if not cols.(col) && not diag1.(d1) && not diag2.(d2) then begin
          board.(row) <- col;
          cols.(col) <- true;
          diag1.(d1) <- true;
          diag2.(d2) <- true;
          place (row + 1);
          cols.(col) <- false;
          diag1.(d1) <- false;
          diag2.(d2) <- false
        end
      done
  in
  place 0;
  List.rev !solutions

(* Approach 2: Functional with list accumulation *)
let solve_n_queens_func n =
  let is_safe queens col =
    let row = List.length queens in
    List.mapi (fun i c ->
      c <> col && abs (row - i) <> abs (col - c)
    ) queens
    |> List.for_all Fun.id
  in
  let rec solve queens row =
    if row = n then [List.rev queens]
    else
      List.init n Fun.id
      |> List.filter (is_safe queens)
      |> List.concat_map (fun col -> solve (col :: queens) (row + 1))
  in
  solve [] 0

let () =
  let solutions = solve_n_queens 4 in
  assert (List.length solutions = 2);

  let solutions8 = solve_n_queens 8 in
  assert (List.length solutions8 = 92);

  let func_solutions = solve_n_queens_func 4 in
  assert (List.length func_solutions = 2);

  let func8 = solve_n_queens_func 8 in
  assert (List.length func8 = 92);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

N-Queens — Comparison

Core Insight

N-Queens is the classic backtracking problem. Three arrays track column and diagonal conflicts for O(1) safety checks. The bitmask approach (Rust only) compresses these into integers for maximum performance.

OCaml Approach

Boolean arrays for column/diagonal tracking
`List.mapi` + `List.for_all` for functional safety check
`List.concat_map` for generating all valid continuations
Accumulation via `ref` list or pure list return

Rust Approach

`Vec<bool>` for column/diagonal tracking
Inner `fn` with many `&mut` parameters (borrow checker requires explicit passing)
Bitmask variant using bit manipulation (`wrapping_neg`, `& (bits-1)`)
`clone()` for saving board state to solutions

Comparison Table

Aspect	OCaml	Rust
Safety check	`List.mapi` + `List.for_all`	`.iter().enumerate().all()`
Solution storage	`ref` list, prepend + `List.rev`	`Vec::push` + `clone()`
Functional style	`List.concat_map` for branching	Recursive with `push`/`pop`
Bitmask variant	Not shown (less idiomatic)	`u32` bit manipulation — fastest
Parameter passing	Closures capture mutable state	Explicit `&mut` params (borrow checker)