【DFS, 回溯】N皇后 II

题目

52. N皇后 II

---

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

解题

方法一：DFS 回溯

思路

因为两个皇后之间不能同行同列同斜线，所以 0~N-1 共 N 个皇后一定在 0~N-1 行上每行有一个，那么就可以递归地判断每一行的皇后在那，当每一行皇后的位置都不会互相冲突时，就得到了一组合法解。

具体思路见代码注释。

代码

class Solution {
    private int N;
    private int[] queens;
    private int ans = 0;

    public int totalNQueens(int n) {
        N = n;
        // 表示第 i 行的皇后在第 queens[i] 列
        queens = new int[N];
        // 从第 0 行开始递归
        dfs(0);
        return ans;
    }

    public void dfs(int curr) {
        // 递归出口: 如果递归到第 N 个皇后 说明 0~N-1 个皇后(共N个)已经放置好了
        // 满足一组合法解的条件 解决方案自增并结束递归
        if (curr == N) {
            ans++;
            return;
        }
        // 在 0~N-1 的每一列上尝试放下当前行的皇后
        outer: for (int col = 0; col < N; col++) {
            // 判断之前每一行放的皇后与该行是否有冲突
            queens[curr] = col;
            for (int row = 0; row < curr; row++) {
                // 如果皇后在同一列上或皇后在同一条斜线上
                if (queens[curr] == queens[row] ||
                        Math.abs(curr - row) == Math.abs(queens[curr] - queens[row]))
                    // 则当前列的皇后位置不合法 尝试放在下一列
                    continue outer;
            }
            // 如果和之前每一行放的皇后都没有冲突 就递归尝试放下一个(下一行)的皇后
            dfs(curr + 1);
        }
    }
}

基于集合的回溯

为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 cols 、 dias1 和 dias2 分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 n 列，每一列的下标范围从 0 到 n-1，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 $(0,0)$ 和 $(3,3)$ 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 $(3,0)$ 和 $(1,2)$ 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

class Solution {
    private int n;
    private int ans = 0;
    private Set<Integer> cols = new HashSet<>();
    private Set<Integer> dias1 = new HashSet<>();
    private Set<Integer> dias2 = new HashSet<>();

    public int totalNQueens(int _n) {
        n = _n;
        dfs(0);
        return ans;
    }

    public void dfs(int row) {
        if (row == n) {
            ans++;
            return;
        }
        for (int col = 0; col < n; col++) {
            int dia1 = row + col, dia2 = row - col;
            if (cols.contains(col) || dias1.contains(dia1) || dias2.contains(dia2)) continue;
            cols.add(col);
            dias1.add(dia1);
            dias2.add(dia2);
            dfs(row + 1);
            cols.remove(col);
            dias1.remove(dia1);
            dias2.remove(dia2);
        }
    }
}