Problem Statement

Place N queens on an N×N chessboard such that no two queens threaten each other — i.e., no two share the same row, column, or diagoanl.

1. Basic Backtracking

A straightforward recursive backtracking approach places one queen per row and validates column and diagonal constraints before proceeding.

int countNQueens(int n) {
    if (n == 1) return 1;
    std::vector<int> board(n + 1, 0);
    int solutions = 0;

    auto isValid = [&](int row, int col) -> bool {
        for (int r = 1; r < row; ++r) {
            int c = board[r];
            if (c == col || std::abs(c - col) == std::abs(r - row)) {
                return false;
            }
        }
        return true;
    };

    std::function<void(int)> backtrack = [&](int row) {
        if (row > n) {
            ++solutions;
            return;
        }
        for (int col = 1; col <= n; ++col) {
            if (isValid(row, col)) {
                board[row] = col;
                backtrack(row + 1);
                board[row] = 0;
            }
        }
    };

    backtrack(1);
    return solutions;
}

Time complexity: O(N^N) in worst case. Space: O(N).

2. Horizontal Symmetry Pruning

Exploit left-right symmetry: for even N, restrict the first queen to columns 1 through N/2; for odd N, restrict to columns 1 through (N+1)/2, and when placing at the center column, constrain the second queen to the left half to avoid double-counting symmetric solutions.

int countWithSymmetry(int n) {
    if (n == 1) return 1;
    std::vector<int> board(n + 1, 0);
    int solutions = 0;
    const int mid = (n + 1) / 2;
    const bool isOdd = n % 2 == 1;

    auto isValid = [&](int row, int col) -> bool {
        for (int r = 1; r < row; ++r) {
            int c = board[r];
            if (c == col || std::abs(c - col) == std::abs(r - row)) {
                return false;
            }
        }
        return true;
    };

    std::function<void(int, int)> backtrack = [&](int row, int maxCol) {
        if (row > n) {
            ++solutions;
            return;
        }
        int upperBound = (row == 1) ? mid : n;
        if (row == 2 && isOdd && board[1] == mid) {
            upperBound = mid;
        }
        for (int col = 1; col <= upperBound; ++col) {
            if (isValid(row, col)) {
                board[row] = col;
                backtrack(row + 1, n);
                board[row] = 0;
            }
        }
    };

    backtrack(1, mid);
    return (n % 2 == 0) ? solutions * 2 : solutions * 2 - countCenterFixed(n);
}

3. Conflict Tracking via Boolean Arrays

Replace repeated validity checks with three boolean arrays tracking ocucpied columns and both diagonals (indexed as row - col and row + col). Eliminates O(N) scan per placement.

int countWithArrays(int n) {
    std::vector<bool> colUsed(n + 1, false);
    std::vector<bool> diag1Used(2 * n + 1, false); // row - col + n
    std::vector<bool> diag2Used(2 * n + 1, false); // row + col
    int solutions = 0;

    std::function<void(int)> backtrack = [&](int row) {
        if (row > n) {
            ++solutions;
            return;
        }
        for (int col = 1; col <= n; ++col) {
            int d1 = row - col + n, d2 = row + col;
            if (!colUsed[col] && !diag1Used[d1] && !diag2Used[d2]) {
                colUsed[col] = diag1Used[d1] = diag2Used[d2] = true;
                backtrack(row + 1);
                colUsed[col] = diag1Used[d1] = diag2Used[d2] = false;
            }
        }
    };

    backtrack(1);
    return solutions;
}

4. Bitmask-Based Diagonal Encoding

Represent column and diagonal occupancy using integers: cols, diag1, diag2. Shift and mask operations replace array lookups. Enables compact state propagation.

int countWithBitmasks(int n) {
    int solutions = 0;
    const int full = (1 << n) - 1;

    std::function<void(int, int, int, int)> backtrack = 
        [&](int row, int cols, int diag1, int diag2) {
        if (cols == full) {
            ++solutions;
            return;
        }
        int available = full & ~(cols | diag1 | diag2);
        while (available) {
            int pos = available & -available; // lowest set bit
            available ^= pos;
            int newCols = cols | pos;
            int newDiag1 = (diag1 | pos) << 1;
            int newDiag2 = (diag2 | pos) >> 1;
            backtrack(row + 1, newCols, newDiag1, newDiag2);
        }
    };

    backtrack(1, 0, 0, 0);
    return solutions;
}

5. Full Bitwise Optimization (Iterative State Packing)

Merge all three constraints into a single recursive call with precomputed bit masks. Use compiler-friendly bit logic and eliminate recursion overhead where possible (though still recursive here for clarity).

int countOptimizedBits(int n) {
    if (n == 0) return 1;
    int solutions = 0;
    const int mask = (1 << n) - 1;

    std::function<void(int, int, int, int)> search = 
        [&](int row, int cols, int ldiag, int rdiag) {
        if (cols == mask) {
            ++solutions;
            return;
        }
        int free = mask & ~(cols | ldiag | rdiag);
        while (free) {
            int bit = free & -free;
            free ^= bit;
            search(row + 1,
                   cols | bit,
                   (ldiag | bit) << 1,
                   (rdiag | bit) >> 1);
        }
    };

    search(0, 0, 0, 0);
    return solutions;
}