N 皇后 - LeetCode 热题 62

大家好！我是曾续缘🧡

今天是《LeetCode 热题 100》系列

发车第 62 天

回溯第 8 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：

1 <= n <= 9
难度：💝💝💝

解题方法

N皇后问题的目标是在一个N×N的棋盘上放置N个皇后，使得任何一个皇后都不在同一行、同一列以及同一斜线上。

为了快速检查一个位置是否可以放置皇后，我们使用三个集合来记录哪些列和斜线上已经有皇后了。这三个集合分别是 col（列集合），slash_l（左斜线集合），slash_r（右斜线集合）。这样，我们就可以在 O(1) 的时间复杂度内检查一个位置是否与已有的皇后冲突。

行冲突：由于我们是一行一行放置皇后的，所以不存在行冲突。
列冲突：用一个集合来记录每一列是否已经放置了皇后。
斜线冲突：有两种斜线，左上到右下的斜线和右上到左下的斜线。对于左上到右下的斜线，如果两个皇后在斜线上的话，它们所在的行号与列号的差是相同的；对于右上到左下的斜线，如果两个皇后在斜线上的话，它们所在的行号与列号的和是相同的。因此，我们可以用两个集合分别记录这两种斜线上是否已经放置了皇后。

初始化棋盘：首先，我们需要一个N×N的棋盘来表示这个问题，棋盘上的每一个位置都保持为空。
放置皇后：从棋盘的第一行开始，尝试在每一列放置一个皇后。放置前，需要检查这个位置是否与已经放置的皇后冲突。
回溯：如果在当前行找不到合适的位置放置皇后，那么需要回溯到上一行，继续尝试下一列。如果在当前行找到了合适的位置，那么继续在下一行尝试放置皇后。
找到解决方案：如果成功地在最后一行放置了皇后且没有冲突，那么就找到了一个解决方案。将这个解决方案添加到答案列表中，并继续回溯寻找其他可能的解决方案。

Code

class Solution {
    List<List<String>> ans; // 存储所有解决方案的列表
    public List<List<String>> solveNQueens(int n) {
        char[][] g = new char[n][n]; // 创建棋盘
        ans = new ArrayList<List<String>>(); // 初始化答案列表
        for(char[] row : g) Arrays.fill(row, '.'); // 用 '.' 填充棋盘
        Set<Integer> col = new HashSet<Integer>(); // 列集合
        Set<Integer> slash_l = new HashSet<Integer>(); // 左斜线集合
        Set<Integer> slash_r = new HashSet<Integer>(); // 右斜线集合
        backtrack(g, 0, col, slash_l, slash_r); // 从第0行开始回溯
        return ans; // 返回所有解决方案
    }
    public void backtrack(char[][] g, int i, Set<Integer> col, Set<Integer> slash_l, Set<Integer> slash_r){
        if(i == g.length){ // 如果所有行都放置了皇后
            ans.add(charArrayToList(g)); // 将当前棋盘状态添加到答案列表
            return;
        }
        for(int j = 0; j < g.length; j++){ // 遍历当前行的所有列
            if(col.contains(j)) continue; // 如果列已有皇后，跳过
            if(slash_l.contains(i - j)) continue; // 如果左斜线已有皇后，跳过
            if(slash_r.contains(i + j)) continue; // 如果右斜线已有皇后，跳过
            g[i][j] = 'Q'; // 在当前位置放置皇后
            col.add(j); // 记录列
            slash_l.add(i - j); // 记录左斜线
            slash_r.add(i + j); // 记录右斜线
            backtrack(g, i + 1, col, slash_l, slash_r); // 递归下一行
            g[i][j] = '.'; // 撤销皇后放置
            col.remove(j); // 移除列记录
            slash_l.remove(i - j); // 移除左斜线记录
            slash_r.remove(i + j); // 移除右斜线记录
        }
    }

     public List<String> charArrayToList(char[][] charArray) {
        List<String> resultList = new ArrayList<>();
        for (char[] row : charArray) {
            resultList.add(new String(row));
        }
        return resultList;
    }
}