Stage 2: Recursive Thinking·Backtracking

Hard#517 min readBacktrackingConstraint PropagationBitmaskLeetCode

N-Queens

Row-by-row placement with column / diagonal sets

Row-by-row placement with column/diagonal constraint checking. Classic.

Published Apr 16, 2026

Problem

Place n queens on an n × n chessboard so that no two attack each other. Return all distinct board configurations, where each board is represented as a list of strings with 'Q' for a queen and '.' for an empty square.

Input

n = 4

Output

[[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]

Input

n = 1

Output

[["Q"]]

Intuition

A queen placed in row r attacks its column and its two diagonals. The key insight: we only ever place one queen per row, so rather than search every cell, we recurse over rows and, at each row, pick a column that doesn't conflict with any queen placed so far.

Conflicts are easy to detect with three sets:

cols — columns already occupied.
diag1 — the r - c value (constant along ↘ diagonals).
diag2 — the r + c value (constant along ↙ diagonals).

A candidate (r, c) is legal iff c ∉ cols && (r - c) ∉ diag1 && (r + c) ∉ diag2. Place, recurse to the next row, un-place.

The bitmask variant replaces the three sets with three integers and uses bit operations instead of hash-set ops. Same algorithm, better constants.

Interactive concept

N-Queens Constraint Layers

Place one queen per row while three sets reject unsafe columns and diagonals.

Place row by row

Once a queen is placed in a row, the recursive call owns the next row.

row1

Approach

Row-by-row with conflict sets

TimeO(n!)

SpaceO(n)

Recommended

Clear and easy to reason about. cols, diag1, diag2 are hash sets; the path is the column chosen for each row. On base case row == n, render the board strings from the queens vector.

use std::collections::HashSet;

impl Solution {
    pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
        let n = n as usize;
        let mut out = Vec::new();
        let mut queens = vec![0usize; n];
        let mut cols: HashSet<i32> = HashSet::new();
        let mut d1: HashSet<i32> = HashSet::new();
        let mut d2: HashSet<i32> = HashSet::new();
        fn dfs(
            row: usize,
            n: usize,
            queens: &mut [usize],
            cols: &mut HashSet<i32>,
            d1: &mut HashSet<i32>,
            d2: &mut HashSet<i32>,
            out: &mut Vec<Vec<String>>,
        ) {
            if row == n {
                let mut board = Vec::with_capacity(n);
                for &c in queens.iter() {
                    let mut s = vec!['.'; n];
                    s[c] = 'Q';
                    board.push(s.into_iter().collect());
                }
                out.push(board);
                return;
            }
            for c in 0..n {
                let ci = c as i32;
                let ri = row as i32;
                if cols.contains(&ci) || d1.contains(&(ri - ci)) || d2.contains(&(ri + ci)) {
                    continue;
                }
                queens[row] = c;
                cols.insert(ci);
                d1.insert(ri - ci);
                d2.insert(ri + ci);
                dfs(row + 1, n, queens, cols, d1, d2, out);
                cols.remove(&ci);
                d1.remove(&(ri - ci));
                d2.remove(&(ri + ci));
            }
        }
        dfs(0, n, &mut queens, &mut cols, &mut d1, &mut d2, &mut out);
        out
    }
}

Rust · runnable

function solveNQueens(n: number): string[][] {
  const out: string[][] = [];
  const queens: number[] = new Array(n).fill(-1);
  const cols = new Set<number>();
  const d1 = new Set<number>();
  const d2 = new Set<number>();
  const dfs = (row: number): void => {
    if (row === n) {
      const board: string[] = [];
      for (const c of queens) {
        board.push('.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1));
      }
      out.push(board);
      return;
    }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || d1.has(row - c) || d2.has(row + c)) continue;
      queens[row]= c;
      cols.add(c);
      d1.add(row - c);
      d2.add(row + c);
      dfs(row + 1);
      cols.delete(c);
      d1.delete(row - c);
      d2.delete(row + c);
    }
  };
  dfs(0);
  return out;
}

TypeScript · runnable

Bitmask

TimeO(n!)

SpaceO(n)

Replace the three sets with three integers whose bits indicate occupied columns / diagonals. Set available = ~(cols | d1 | d2) & ((1 << n) - 1); iterate the set bits with lowbit = available & -available. Saves the hash-set overhead.

Works cleanly up to n ≤ 30 (fits in u32); go to u64 for n ≤ 63. This is the standard high-performance template used in competitive solutions.

impl Solution {
    pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
        let n = n as u32;
        let mut out = Vec::new();
        let mut queens = vec![0u32; n as usize];
        fn dfs(
            row: u32,
            n: u32,
            cols: u32,
            d1: u32,
            d2: u32,
            queens: &mut [u32],
            out: &mut Vec<Vec<String>>,
        ) {
            if row == n {
                let board: Vec<String> = queens
                    .iter()
                    .map(|&c| {
                        let mut s = vec!['.'; n as usize];
                        s[c as usize] = 'Q';
                        s.into_iter().collect()
                    })
                    .collect();
                out.push(board);
                return;
            }
            let mut available = !(cols | d1 | d2) & ((1u32 << n) - 1);
            while available = 0 {
                let bit= available & available.wrapping_neg();
                available = bit;
                let c= bit.trailing_zeros();
                queens[row as usize]= c;
                dfs(row + 1, n, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, queens, out);
            }
        }
        dfs(0, n, 0, 0, 0, &mut queens, &mut out);
        out
    }
}

Rust · runnable

function solveNQueens(n: number): string[][] {
  const out: string[][] = [];
  const queens: number[] = new Array(n).fill(0);
  const dfs = (row: number, cols: number, d1: number, d2: number): void => {
    if (row === n) {
      const board: string[] = [];
      for (const c of queens) {
        board.push('.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1));
      }
      out.push(board);
      return;
    }
    let available = ~(cols | d1 | d2) & ((1 << n) - 1);
    while (available !== 0) {
      const bit = available & -available;
      available ^= bit;
      const c = Math.log2(bit) | 0;
      queens[row] = c;
      dfs(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
    }
  };
  dfs(0, 0, 0, 0);
  return out;
}

TypeScript · runnable

Trace

For n = 4, the recursion discovers the first solution [1, 3, 0, 2] (queens at cols 1, 3, 0, 2 for rows 0, 1, 2, 3):

Backtracking#51

N-Queens walkthrough

n = 4

Step 1 of 30%

0	.	Q	.	.
1	.	.	.	.
2	.	.	.	.
3	.	.	.	.

cols

{1}

diag1

{-1}

diag2

{1}

Start with a column that leaves future diagonals open.

Choose row 0, column 1

Decision

Mark col 1, diag r-c = -1, diag r+c = 1.

Update

The search descends to row 1.

Why it works

The sets make safety checks O(1).

Rendered board:

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

Edge cases

n = 1 — one solution, ["Q"].
n = 2 or n = 3 — no solutions; the algorithm returns [].
Large n — the solution count grows slower than n! but still explodes (n=13 has 73,712 solutions). The bitmask variant is noticeably faster for n ≥ 8.

Takeaway

Domain-specific conflict checks are the heart of constraint-satisfaction backtracking. The three-set trick (cols / r-c / r+c) turns an otherwise O(n²) attack-check into O(1). Whenever a problem's constraints can be encoded as a small number of integer invariants, you can usually get an O(1) feasibility test — and that is typically the difference between a TLE and an AC.