【回溯算法——N皇后】

本次复习的是回溯算法中的一道经典问题——N皇后问题，对应leetcode 51.N皇后
内容来源于代码随想录

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

思路

首先要理解棋盘中的皇后的约束条件：1. 不能同行 2. 不能同列 3. 不能同斜线
回溯问题模板：

void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}

• 递归函数参数
  定义一个全局变量二维数组result记录最终收集到的结果
  定义n是棋盘大小，row记录当前遍历到棋盘的第几层
• 递归终止条件
  当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了
• 单层搜索逻辑
  递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
  每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

代码

classSolution{public: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){//检查列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;}vector<vector<string>>solveNQueens(intn){result.clear();std::vector<std::string>chessboard(n,std::string(n,'.'));backtracking(n,0,chessboard);returnresult;}};