?
对回溯法理论不清楚的学生，可可以先看这个视频:
n 如何研究皇后的问题？ n 女王放在那里 n×n 在棋盘上，皇后不能互相交往***。
上图为 8 一种解决皇后问题的方法。
给定一个整数 n，返回所有不同的 n 解决皇后问题。
每个解决方案都包含一个清晰的解决方案 n 女王问题的棋子放置方案，方案 'Q' 和 '.' 分别代表皇后和空位。
示例: 输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题有两种不同的解决方案。
提示：
女王是国际象棋中的棋子，这意味着国王的妻子。女王只做一件事，那就是吃子。当她遇到可以吃的棋子时，她迅速冲上去吃。当然，她可以在水平、垂直和倾斜上走一到七步。（引用自我 百度百科 - 皇后 )
思路
我们都知道n皇后的问题是回溯算法解决的经典问题，但在解决了更多的组合、切割、子集和排列问题后，我们会有点不知所措。
首先，让我们来看看皇后的约束：
不能同行
不能同列
不能同斜线
确定约束条件后，看看如何搜索女王的位置。事实上，搜索女王的位置可以抽象成一棵树。
下面我用一个3 * 3 棋牌将搜索过程抽象成一棵树，如图所示:
51.N皇后
从图中可以看出，二维矩阵中矩阵的高度是树的高度，矩阵的宽度是树结构中每个节点的宽度。
然后我们用皇后的约束来回搜索这棵树，「只要你搜索树的叶节点，你就会找到女王的合理位置」。
回溯三部曲
根据我总结的以下回溯模板，我们将依次分析：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集中元素(树中节点儿童数量为集合大小) {
处理节点;
backtracking(路径，选列表)； // 递归
回溯，撤销处理结果
}
}
递归函数参数
我仍然定义全局变量二维数组result记录最终结果。
参数n是棋牌的大小，然后用row记录棋盘的第一层。
代码如下：
vector> result;
void backtracking(int n, int row, vector& chessboard) {
递归终止条件
以下树形结构：
可见，当递归到棋盘底部(即叶节点)时，可以收集结果并返回。
代码如下：
if (row == n) {
result.push_back(chessboard);
return;
}
单层搜索的逻辑
递归深度是row控制棋盘，每层for循环的col控制棋盘列，一行一行，确定皇后的位置。
每次都要从新一行的起点开始搜索，所以都是从0开始。
代码如下：
for (int col = 0; col < n; col ) {
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row 1, chessboard);
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
验证棋牌是否合法
按以下标准去重：
不能同行
不能同列
不能同斜线 (45度和135度角)
代码如下：
bool isValid(int row, int col, vector& chessboard, int n) {
int count = 0;
// 检查列
for (int i = 0; i < row; i ) { // 这是剪枝
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查 45度角是否有皇后？
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查 135度角是否为皇后？
for(int i = row - 1, j = col 1; i >= 0 && j < n; i--, j ) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
在这个代码中，细心的学生可以发现为什么他们没有在同同龄人？
因为在单层搜索的过程中，只会选择每一层递归for循环(也就是同行)中的一个元素，不用重。
按此模板写下以下代码并不难：
**C 代码**
class Solution {
private:
vector> result;
// n 输入棋盘的大小
// row 是当前递归棋牌的第几行
void backtracking(int n, int row, vector& chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < n; col ) {
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row 1, chessboard);
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
}
bool isValid(int row, int col, vector& chessboard, int n) {
int count = 0;
// 检查列
for (int i = 0; i < row; i ) { // 这是剪枝
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查 45度角是否有皇后？
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查 135度角是否为皇后？
for(int i = row - 1, j = col 1; i >= 0 && j < n; i--, j ) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
public:
vector> solveNQueens(int n) {
result.clear();
std::vector<:string> chessboard(n, std::string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};
可以看出，除了验证棋盘合法性的代码，省下来部分就是按照回溯法模板来的。
**总结**
本题是我们解决棋盘问题的第一道题目。
如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。
**「这里我明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了」**。
大家可以在仔细体会体会！
**就酱，如果感觉「代码随想录」干货满满，就分享给身边的朋友同学吧，他们可能也需要！**
打算从头开始打卡的录友，可以在「算法汇总」这里找到历史文章，很多录友都在从头打卡，你并不孤单！
