力扣HOT100之回溯：51. N 皇后

这道题之前刷代码随想录的时候跳过了，然后今天是第一次做这个题目，感觉很难，然后去看了代码随想录对应的视频才做出来的。这里主要讲一下思路。
我们首先定义一个递归函数backtracking()，输入参数分别为int row，vector<string>& chessboard和int n，其中row表示当前正在第row行填皇后，chessboard表示棋盘，n表示棋盘的尺寸为n * n。显而易见，当row >= n时，则说明0 ~ n - 1行的皇后已经全部填完，则直接收获结果。否则进入递归主体逻辑。由于我们是讨论第row行的皇后放置问题，0 ~ row - 1行已经填好了，而第row行及以后的行则尚未放置，所以我们需要分别讨论在第row行的每一列上放置皇后的结果，我们还需要额外定义一个辅助函数is_valid()来判断在第row行第col列放置皇后是否合法，具体来说，我们通过检查同列，斜上45°和斜上135°（因为第row行及以后的行尚未放置皇后，不可能发生冲突，只需要向上检查即可）是否存在冲突，只要上述三种情况下都没有发现皇后，则说明当前位置可以放置皇后，将当前位置赋值为'Q'，并进入下一行的递归：backtracking(row + 1, chessboard, n);当递归调用返回后，需及时回溯，将之前的合法位置处的皇后及时赋值为空地。若不及时回溯，则随着循环的进行，每一行都会塞满皇后。

class Solution {
public:vector<vector<string>> result;   //记录所有符合条件的结果bool is_valid(int row, int col, vector<string>& chessboard, int n){//想在chessboard[row][col]处放置皇后（还没放），判断该位置是否合法，棋盘大小为n * n//观察同一列中有没有放置皇后for(int i = 0; i < n; 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;}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));  //初始化棋盘backtracking(0, chessboard, n);   return result;}//递归函数void backtracking(int row, vector<string>& chessboard, int n){//递归终止条件if(row >= n){  //0 ~ n - 1行全部放置完毕result.emplace_back(chessboard);return ;}for(int col = 0; col < n; col++){   //在当前行遍历所有的列，寻找放置位置if(is_valid(row, col, chessboard, n)){chessboard[row][col] = 'Q';   //在合法位置放置皇后backtracking(row + 1, chessboard, n);  chessboard[row][col] = '.';  //回溯}}}
};