LeetCode 热题 100_N 皇后（62_51_困难_C++）(递归（回溯））

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;}// 如果没有冲突，返回truereturn 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;}// 如果没有冲突，返回truereturn 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;
}