侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS, 回溯】N皇后 II

GabrielxD
2022-06-08 / 0 评论 / 0 点赞 / 43 阅读 / 1,024 字 / 正在检测是否收录...

题目

52. N皇后 II


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

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

image-20220605182549472

示例 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);
        }
    }
}

基于集合的回溯

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

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

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

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

image-20220608051058309

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

image-20220608051126173

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

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);
        }
    }
}
0

评论区