1062 Advanced

1062-n-queens — N-Queens

Functional Programming

Tutorial

The Problem

The N-queens problem asks how to place N chess queens on an N×N board so that no two queens attack each other — no shared row, column, or diagonal. It is the classic benchmark for backtracking algorithms and constraint satisfaction solvers.

For N=8, there are 92 solutions. For N=14, there are 365,596. The problem scales exponentially with N, making efficient pruning critical. The solution demonstrates how constraint propagation (recording which columns and diagonals are occupied) can dramatically reduce the search space.

🎯 Learning Outcomes

• Implement backtracking with constraint propagation using boolean arrays

• Use column and diagonal constraint vectors to prune the search tree

• Count solutions and collect all valid board configurations

• Understand the O(N!) worst case and why pruning reduces practical run time

• Connect to constraint satisfaction programming (CSP) and SAT solvers

Code Example

#![allow(clippy::all)]
// 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)
}

#[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"

Key Differences

Mutation model: Rust's &mut arrays are passed explicitly; OCaml's mutable arrays are implicitly shared across recursive calls.

Solutions collection: Rust uses results: &mut Vec<Vec<usize>>; OCaml uses a ref to a list — both accumulate without returning from each recursive call.

**board.clone()**: Rust must explicitly clone the board when adding to solutions (.clone()); OCaml uses Array.copy board.

Bitmask optimization: A more optimized version uses bitmasks (three integers) instead of three arrays — both languages support this but Rust's u32 bit operations are slightly more concise.

OCaml Approach

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
  let diag2 = Array.make (2*n-1) false in
  let board = Array.make n 0 in
  let rec place row =
    if row = n then solutions := Array.copy board :: !solutions
    else
      for col = 0 to n - 1 do
        let d1 = row + n - 1 - col and 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;
  !solutions

Structurally identical. The constraint array indexing is the same in both languages.

Full Source

#![allow(clippy::all)]
// 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)
}

#[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"

✓ Tests Rust test suite

#[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);
    }
}

Deep 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)

Exercises

Implement the bitmask optimization using three u32 values instead of three Vec<bool> arrays.

Parallelize the solver using rayon::par_iter over the first row's column choices.

Write a validator is_valid_placement(queens: &[usize]) -> bool that checks a given placement without solving.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust