N-Queens and Backtracking

Place N queens on an N×N chessboard so that no two queens attack each other. This is the classic backtracking problem — it combines the permutation pattern (one queen per row) with constraint checking (columns and diagonals).

The Rules

A queen attacks along rows, columns, and both diagonals. Since we place exactly one queen per row, rows are automatically safe. We need to track:

Columns

No two queens share the same column index.

Main diagonal ( ↘ )

For a cell (r, c), the key is r − c. Constant along ↘ diagonals.

Anti diagonal ( ↙ )

For a cell (r, c), the key is r + c. Constant along ↙ diagonals.

Backtracking Solution

Place queens row by row. In each row, try every column. If the position is safe (no conflict), place the queen and recurse to the next row. If it leads to a dead end, backtrack and try the next column.

C++ — N-Queens with bitmask conflict tracking

void solve(int row, int n,
           vector<int>& cols,        // which columns have queens
           vector<int>& diag1,       // r − c  (add n-1 to offset)
           vector<int>& diag2,       // r + c
           vector<string>& board,
           vector<vector<string>>& result) {

    if (row == n) { result.push_back(board); return; }

    for (int col = 0; col < n; col++) {
        int d1 = row - col + n - 1;
        int d2 = row + col;
        if (cols[col] || diag1[d1] || diag2[d2]) continue;

        // Place queen
        board[row][col] = 'Q';
        cols[col] = diag1[d1] = diag2[d2] = 1;

        solve(row + 1, n, cols, diag1, diag2, board, result);

        // Remove queen (backtrack)
        board[row][col] = '.';
        cols[col] = diag1[d1] = diag2[d2] = 0;
    }
}

Rust — N-Queens

fn solve(row: usize, n: usize,
         cols: &mut Vec<bool>,
         diag1: &mut Vec<bool>,
         diag2: &mut Vec<bool>,
         board: &mut Vec<Vec<char>>,
         result: &mut Vec<Vec<String>>) {

    if row == n {
        result.push(board.iter().map(|r| r.iter().collect()).collect());
        return;
    }

    for col in 0..n {
        let d1 = row + n - 1 - col;  // r − c + n − 1
        let d2 = row + col;
        if cols[col] || diag1[d1] || diag2[d2] { continue; }

        board[row][col] = 'Q';
        cols[col] = true; diag1[d1] = true; diag2[d2] = true;

        solve(row + 1, n, cols, diag1, diag2, board, result);

        board[row][col] = '.';
        cols[col] = false; diag1[d1] = false; diag2[d2] = false;
    }
}

💡 O(1) conflict check

Three boolean arrays: cols[col], diag1[r−c+offset], diag2[r+c]. Checking if a square is safe is O(1). Without this, you'd scan the entire board each time — O(N) per check, multiplied by the search tree. The O(1) check is what makes N-Queens solvable for N up to ~15.

What Backtracking Looks Like

Key Takeaways

→ Place queens row by row — one per row eliminates row conflicts.
→ Track column, diagonal (r−c), and anti-diagonal (r+c) with boolean arrays.
→ If no safe square exists in a row, backtrack to the previous row and try the next column.
→ N-Queens solving ~ N! / something — feasible up to N ≈ 15 with good pruning.