N 皇后问题

N 皇后（LeetCode 51）

在 N×N 棋盘放 N 个皇后，使互不攻击，返回所有具体方案。

解法一：布尔数组标记（易理解）

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];   // queens[i] = j  表示第i行皇后在第j列
    Arrays.fill(queens, -1);
    boolean[] cols = new boolean[n];
    boolean[] diag1 = new boolean[2 * n];   // (i-j+n) 主对角线
    boolean[] diag2 = new boolean[2 * n];   // (i+j)   副对角线
    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, 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;
    }
}

private List<String> buildBoard(int[] queens, int n) {
    List<String> board = new ArrayList<>();
    for (int q : queens) {
        char[] row = new char[n];
        Arrays.fill(row, '.');
        row[q] = 'Q';
        board.add(new String(row));
    }
    return board;
}

解法二：位运算优化（高效）

用三个整数的位来标记列、主对角线、副对角线是否被占用。

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];
    Arrays.fill(queens, -1);
    int limit = (1 << n) - 1;   // n位全1
    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;
    }
    int available = limit & ~(cols | d1 | d2);   // 可放置的列
    while (available != 0) {
        int pos = available & (-available);         // 最低位1（选一列）
        available &= available - 1;
        int col = Integer.numberOfTrailingZeros(pos);
        queens[row] = col;
        backtrackBit(row + 1,
                     cols | pos,
                     (d1 | pos) << 1,    // 主对角线下移一行
                     (d2 | pos) >> 1,    // 副对角线下移一行
                     limit, n, queens, res);
    }
}

时间复杂度：O(n!)，位运算版本常数更小。

N 皇后 II（LeetCode 52）

只返回方案数，不需要具体方案，位运算版本直接计数：

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

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

技巧总结