LeetCode 热题 100_N 皇后（62_51）
题目描述：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
题解：
解题思路：
思路一（递归（回溯））：
1、解决此问题的思路是比较明确的。在第一行选取一个位置放置皇后，再在第二行选取一个位置放置一个皇后（放置皇后时判断是否可以放置），以此类推直至最后一行。因行数和列数不确定（不确定的多重循环），从而首先考虑回溯的解法。
递归树如下：
判断此位置是否可以放置皇后，可以挨个判断当前位置的之前行、列和同一斜线上是否有皇后。（还可以使用哈希集合来分别存储不可放置的行、列和同一斜线）
2、复杂度分析：
① 时间复杂度：O(N!)，其中N是皇后数量。
② 空间复杂度：O(N)，其中N是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组，递归调用层数不会超过N，数组的长度为N。
代码实现
代码实现（思路一（递归（回溯）））：
class Solution1 {
private:
// 用于存储所有解法的答案
vector<vector<string>> ans;
// 回溯函数，用于寻找解决问题的所有方法
void backtrack(int n, int row, vector<string> &board) {
// 递归出口，当所有行都填满时，表示找到一个解
if (row == n) {
ans.emplace_back(board); // 将当前的棋盘布局加入答案中
return;
}
// 遍历当前行的每一列，尝试在每一列放置皇后
for (int col = 0; col < n; col++) {
// 检查当前位置是否安全，安全则放置皇后
if (isValid(row, col, n, board)) {
board[row][col] = 'Q'; // 放置皇后
backtrack(n, row + 1, board); // 递归处理下一行
board[row][col] = '.'; // 回溯，撤销当前选择
}
}
}
// 检查当前位置(row, col)是否安全
bool isValid(int row, int col, int n, vector<string> &board) {
// 检查当前列上是否已有皇后
for (int i = row; i >= 0; i--) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线是否已有皇后
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线是否已有皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
// 如果没有冲突，返回true
return true;
}
public:
// 主函数，用于返回所有的解法
vector<vector<string>> solveNQueens(int n) {
ans.clear(); // 清空之前的解
// 创建一个n行n列的棋盘，初始化所有位置为'.'
vector<string> board(n, string(n, '.'));
// 从第一行开始回溯搜索
backtrack(n, 0, board);
// 返回所有解法
return ans;
}
};
以思路一为例进行调试
#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
using namespace std;
class Solution1 {
private:
// 用于存储所有解法的答案
vector<vector<string>> ans;
// 回溯函数，用于寻找解决问题的所有方法
void backtrack(int n, int row, vector<string> &board) {
// 递归出口，当所有行都填满时，表示找到一个解
if (row == n) {
ans.emplace_back(board); // 将当前的棋盘布局加入答案中
return;
}
// 遍历当前行的每一列，尝试在每一列放置皇后
for (int col = 0; col < n; col++) {
// 检查当前位置是否安全，安全则放置皇后
if (isValid(row, col, n, board)) {
board[row][col] = 'Q'; // 放置皇后
backtrack(n, row + 1, board); // 递归处理下一行
board[row][col] = '.'; // 回溯，撤销当前选择
}
}
}
// 检查当前位置(row, col)是否安全
bool isValid(int row, int col, int n, vector<string> &board) {
// 检查当前列上是否已有皇后
for (int i = row; i >= 0; i--) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线是否已有皇后
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线是否已有皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
// 如果没有冲突，返回true
return true;
}
public:
// 主函数，用于返回所有的解法
vector<vector<string>> solveNQueens(int n) {
ans.clear(); // 清空之前的解
// 创建一个n行n列的棋盘，初始化所有位置为'.'
vector<string> board(n, string(n, '.'));
// 从第一行开始回溯搜索
backtrack(n, 0, board);
// 返回所有解法
return ans;
}
};
int main() {
// 创建 Solution1 类的对象 s1，用于求解 N 皇后问题
Solution1 s1;
// 调用 solveNQueens 函数求解 4 皇后问题，返回所有解的集合
vector<vector<string>> ans = s1.solveNQueens(4);
// 遍历所有的解，每个解是一个棋盘的布局
for (auto &str : ans) {
// 遍历当前棋盘布局中的每一行（每行是一个字符串）
for (auto &c : str) {
// 输出当前行的每个字符（每个字符是棋盘位置上的 '.' 或 'Q'）
cout << c << " " << endl;
}
// 每找到一个解后，输出两个换行符，以区分不同解
cout << endl << endl;
}
// 返回 0，表示程序正常结束
return 0;
}
LeetCode 热题 100_N 皇后 （62_51)原题链接
欢迎大家和我沟通交流(✿◠‿◠)