N-Queens: Classic Constraint Satisfaction Backtracking

def solveNQueens(n):
    result = []
    cols = set()
    diag1 = set()   # row - col (top-left to bottom-right)
    diag2 = set()   # row + col (top-right to bottom-left)
    board = [['.' ] * n for _ in range(n)]

    def bt(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            board[row][col] = 'Q'
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            bt(row + 1)
            board[row][col] = '.'
            cols.discard(col); diag1.discard(row-col); diag2.discard(row+col)

    bt(0)
    return result

def totalNQueens(n):
    count = [0]
    cols = set(); d1 = set(); d2 = set()
    def bt(row):
        if row == n: count[0] += 1; return
        for col in range(n):
            if col in cols or (row-col) in d1 or (row+col) in d2: continue
            cols.add(col); d1.add(row-col); d2.add(row+col)
            bt(row + 1)
            cols.discard(col); d1.discard(row-col); d2.discard(row+col)
    bt(0)
    return count[0]

print(totalNQueens(8))  # 92

#include <bits/stdc++.h>
using namespace std;

int totalNQueens(int n) {
    int count = 0;
    // cols, diag1, diag2 as bitmasks
    function<void(int, int, int, int)> bt = [&](int row, int cols, int d1, int d2) {
        if (row == n) { count++; return; }
        int available = ((1 << n) - 1) & ~(cols | d1 | d2);
        while (available) {
            int bit = available & (-available);  // lowest set bit
            available &= available - 1;
            bt(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
        }
    };
    bt(0, 0, 0, 0);
    return count;
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> queens(n, -1); // queens[row] = col
    set<int> cols, d1, d2;

    function<void(int)> bt = [&](int row) {
        if (row == n) {
            vector<string> board(n, string(n, '.'));
            for (int r = 0; r < n; r++) board[r][queens[r]] = 'Q';
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.count(col) || d1.count(row-col) || d2.count(row+col)) continue;
            queens[row] = col;
            cols.insert(col); d1.insert(row-col); d2.insert(row+col);
            bt(row + 1);
            cols.erase(col); d1.erase(row-col); d2.erase(row+col);
        }
    };
    bt(0);
    return result;
}

import java.util.*;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> cols = new HashSet<>(), d1 = new HashSet<>(), d2 = new HashSet<>();
        backtrack(n, 0, queens, cols, d1, d2, result);
        return result;
    }

    void backtrack(int n, int row, int[] queens, Set<Integer> cols,
                   Set<Integer> d1, Set<Integer> d2, List<List<String>> result) {
        if (row == n) {
            List<String> board = new ArrayList<>();
            for (int r = 0; r < n; r++) {
                char[] line = new char[n];
                Arrays.fill(line, '.');
                line[queens[r]] = 'Q';
                board.add(new String(line));
            }
            result.add(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || d1.contains(row-col) || d2.contains(row+col)) continue;
            queens[row] = col;
            cols.add(col); d1.add(row-col); d2.add(row+col);
            backtrack(n, row+1, queens, cols, d1, d2, result);
            cols.remove(col); d1.remove(row-col); d2.remove(row+col);
        }
    }
}