Leetcode刷题详解——N 皇后

皇后"/>

Leetcode刷题详解——N 皇后

1. 题目链接：51. N 皇后

2. 题目描述：

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

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

3. 解法（递归）：

3.1 算法思路：

首先我们在第一行放置第一个皇后，然后遍历棋盘的第二行，在可行的位置放置第二个皇后后，然后再遍历第三行，在可行的位置放置第三个皇后，以此类推，直到放置了n个皇后为止

我们需要用一个数组来记录每一行放置的皇后的列数。在每一行中，我们尝试放置了一个皇后，并检查是否和前面已经放置的皇后冲突。如果没有冲突，我们就继续递归地放置下一行的皇后，直到所有的皇后都放置完毕，然后把这个方案记录下来

在检查皇后是否冲突时，我们可以用一个数组来记录每一列是否已经放置了皇后，并检查当前要放置的皇后是否会和已经放置的皇后冲突。对于对角线，我们可以用两个数组来记录从左上角到右下角的每一条对角线上是否已经放置了皇后，以及右上角到左下角的每一条对角线上是否已经放置了皇后

对于对角线是否冲突的判断可以通过以下流程解决：

1. 从左上到右下：相同对角线的行列之差相同
2. 从右上到左下：相同对角线的行列之和相同

3.2 递归函数流程：

1. 结束条件：如果row等于n，则表示已经找到一组解法方案，此时将每个皇后的位置存储到字符串数组path中，并将path存储到ret数组中，然后返回
2. 枚举当前行的每一列，判断该列、两个对角线上是否已经有皇后：
   1. 如果有皇后，则继续枚举下一列
   2. 否则，在位置放置皇后，并将checkCol、checkDig1、checkDig2对应的位置设置为false，然后继续枚举下一列

3.3 C++算法代码：

class Solution {bool checkCol[10],checkDig1[20],checkDig2[20]; // 用于检查列、对角线1和对角线2是否被皇后占据的数组vector<vector<string>> ret; // 存储所有解的二维向量vector<string> path; // 当前解的路径int n; // 棋盘大小
public:vector<vector<string>> solveNQueens(int _n) {n=_n; // 初始化棋盘大小path.resize(n); // 初始化路径for(int i=0;i<n;i++) // 初始化路径为全'.'{path[i].append(n,'.');}dfs(0); // 从第0行开始搜索return ret; // 返回所有解}void dfs(int row) // 深度优先搜索函数，row表示当前搜索到的行数{if(row==n) // 如果已经搜索到最后一行，说明找到了一个解{ret.push_back(path); // 将当前解添加到结果中return;}for(int col=0;col<n;col++) // 遍历当前行的每个位置{if(!checkCol[col]&&!checkDig1[row-col+n]&&!checkDig2[row+col]) // 如果该位置没有被皇后占据且不在任何一条对角线上{path[row][col]='Q'; // 放置皇后checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=true; // 标记该位置已被皇后占据dfs(row+1); // 继续搜索下一行path[row][col]='.'; // 回溯，移除皇后checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=false; // 标记该位置未被皇后占据}}}
};