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

LeetCode 热题 100_N 皇后 （62_51） 题目描述：输入输出样例：题解：解题思路：思路一（递归（回溯））： 代码实现代码实现（思路一（递归（回溯）））：以思路一为例进行调试 （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)原题链接 欢迎大家和我沟通交流(✿◠‿◠)