The N-Queens Problem

N-Queens (LeetCode 51)

Place $N$ queens on an $N \times N$ chessboard such that no two queens threaten each other. Return all possible arrangements.

Approach 1: Boolean Array Tracking (Easier to Understand)

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n]; // queens[i] = j means row i queen is at column j
    Arrays.fill(queens, -1);
    
    boolean[] cols = new boolean[n];
    boolean[] diag1 = new boolean[2 * n]; // Main diagonal: (row - col + n) is constant
    boolean[] diag2 = new boolean[2 * n]; // Anti-diagonal: (row + col) is constant
    
    backtrack(0, n, queens, cols, diag1, diag2, res);
    return res;
}

private void backtrack(int row, int n, int[] queens, 
                         boolean[] cols, boolean[] diag1, boolean[] diag2, 
                         List<List<String>> res) {
    if (row == n) {
        res.add(buildBoard(queens, n));
        return;
    }
    
    for (int col = 0; col < n; col++) {
        int d1 = row - col + n;
        int d2 = row + col;
        if (cols[col] || diag1[d1] || diag2[d2]) continue;
        
        queens[row] = col;
        cols[col] = diag1[d1] = diag2[d2] = true;
        backtrack(row + 1, n, queens, cols, diag1, diag2, res);
        cols[col] = diag1[d1] = diag2[d2] = false; // Undo (Backtrack)
    }
}

Approach 2: Bit Manipulation (High Efficiency)

Instead of boolean arrays, use three integers to track occupied zones. Bitwise shifting naturally propagates the diagonal constraints.

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];
    int limit = (1 << n) - 1; // Bitmask with N ones
    backtrackBit(0, 0, 0, 0, limit, n, queens, res);
    return res;
}

private void backtrackBit(int row, int cols, int d1, int d2, 
                            int limit, int n, int[] queens, List<List<String>> res) {
    if (row == n) {
        res.add(buildBoard(queens, n));
        return;
    }
    
    // Mask for currently available columns
    int available = limit & ~(cols | d1 | d2);
    while (available != 0) {
        // Extract the lowest set bit (pick the leftmost available column)
        int pos = available & (-available); 
        available &= (available - 1); // Remove the picked position
        
        int col = Integer.numberOfTrailingZeros(pos);
        queens[row] = col;
        
        backtrackBit(row + 1, 
                     cols | pos, 
                     (d1 | pos) << 1, // Propagate anti-diagonal constraint
                     (d2 | pos) >> 1, // Propagate diagonal constraint
                     limit, n, queens, res);
    }
}

Complexity: Overly $O(N!)$ time. The bitwise version is significantly faster due to reduced constant overhead.

N-Queens II (LeetCode 52)

When only the count of solutions is required, the bitwise approach is extremely efficient.

public int totalNQueens(int n) {
    int limit = (1 << n) - 1;
    return dfs(0, 0, 0, limit);
}

private int dfs(int cols, int d1, int d2, int limit) {
    if (cols == limit) return 1;
    
    int count = 0;
    int available = limit & ~(cols | d1 | d2);
    while (available != 0) {
        int pos = available & (-available);
        available -= pos;
        count += dfs(cols | pos, (d1 | pos) << 1, (d2 | pos) >> 1, limit);
    }
    return count;
}

Conflict Detection Reference