通知：我将公众号文章和学习相关的资料整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在电脑上学习，可以fork到自己仓库，顺便也给个star支持一波吧！
第51题. N皇后题目链接：https://leetcode-cn.com/problems/n-queens/
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皇后
从图中，可以看出，二维矩阵中矩阵的高就是这颗树的高度，矩阵的宽就是树型结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这颗树，「只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了」。
回溯三部曲按照我总结的如下回溯模板，我们来依次分析：
voidbacktracking(参数){
if(终止条件){
存放结果;
return;
}
for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
处理节点;
backtracking(路径，选择列表);//递归
回溯，撤销处理结果
}
}
- 递归函数参数
我依然是定义全局变量二维数组result来记录最终结果。
参数n是棋牌的大小，然后用row来记录当前遍历到棋盘的第几层了。
代码如下：
vector<vector<string>>result;
voidbacktracking(intn,introw,vector<string>&chessboard){
- 递归终止条件
在如下树形结构中：
可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。
代码如下：
if(row==n){
result.push_back(chessboard);
return;
}
- 单层搜索的逻辑
递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
代码如下：
for(intcol=0;col<n;col ){
if(isValid(row,col,chessboard,n)){//验证合法就可以放
chessboard[row][col]='Q';//放置皇后
backtracking(n,row 1,chessboard);
chessboard[row][col]='.';//回溯，撤销皇后
}
}
- 验证棋牌是否合法
按照如下标准去重：
- 不能同行
- 不能同列
- 不能同斜线 （45度和135度角）
代码如下：
boolisValid(introw,intcol,vector<string>&chessboard,intn){
intcount=0;
//检查列
for(inti=0;i<row;i ){//这是一个剪枝
if(chessboard[i][col]=='Q'){
returnfalse;
}
}
//检查45度角是否有皇后
for(inti=row-1,j=col-1;i>=0&&j>=0;i--,j--){
if(chessboard[i][j]=='Q'){
returnfalse;
}
}
//检查135度角是否有皇后
for(inti=row-1,j=col 1;i>=0&&j<n;i--,j ){
if(chessboard[i][j]=='Q'){
returnfalse;
}
}
returntrue;
}
在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？
因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
那么按照这个模板不难写出如下代码：
C 代码classSolution{
private:
vector<vector<string>>result;
//n为输入的棋盘大小
//row是当前递归到棋牌的第几行了
voidbacktracking(intn,introw,vector<string>&chessboard){
if(row==n){
result.push_back(chessboard);
return;
}
for(intcol=0;col<n;col ){
if(isValid(row,col,chessboard,n)){//验证合法就可以放
chessboard[row][col]='Q';//放置皇后
backtracking(n,row 1,chessboard);
chessboard[row][col]='.';//回溯，撤销皇后
}
}
}
boolisValid(introw,intcol,vector<string>&chessboard,intn){
intcount=0;
//检查列
for(inti=0;i<row;i ){//这是一个剪枝
if(chessboard[i][col]=='Q'){
returnfalse;
}
}
//检查45度角是否有皇后
for(inti=row-1,j=col-1;i>=0&&j>=0;i--,j--){
if(chessboard[i][j]=='Q'){
returnfalse;
}
}
//检查135度角是否有皇后
for(inti=row-1,j=col 1;i>=0&&j<n;i--,j ){
if(chessboard[i][j]=='Q'){
returnfalse;
}
}
returntrue;
}
public:
vector<vector<string>>solveNQueens(intn){
result.clear();
std::vector<std::string>chessboard(n,std::string(n,'.'));
backtracking(n,0,chessboard);
returnresult;
}
};
可以看出，除了验证棋盘合法性的代码，省下来部分就是按照回溯法模板来的。
总结本题是我们解决棋盘问题的第一道题目。
如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。
「这里我明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了」。
大家可以在仔细体会体会！
就酱，如果感觉「代码随想录」干货满满，就分享给身边的朋友同学吧，他们可能也需要！
打算从头开始打卡的录友，可以在公众号「算法汇总」这里找到历史文章，很多录友都在从头打卡，你并不孤单！
就酱，一直都是干货满满，公众号里的一抹清流，值得推荐给身边的每一位同学朋友！
,
