算法（回溯）-n皇后问题

该题主要来自于力扣。算法主要使用了回溯的算法思想，该题的相关代码思路来自于代码随想录的carl哥。

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E6%80%9D%E8%B7%AF

题目描述

https://leetcode.cn/problems/n-queens/description/

题目解析：

该题主要使用了回溯法，而且，n皇后问题要求所有皇后不在同一行，同一列，同一斜线。因此我们把整个棋盘看作一个树。

在每一层不断循环，往下一行则是模拟树枝向下的过程，逐渐递归。结束该层某个元素之后，就进行回溯。

相对来说思路比较简单，主要是需要一个验证当前位置是否合法的isvalid函数。

代码解析：

class Solution {
vector<vector<string>> result;
private:
    void huisu(int n,int row,vector<string>& checkpoint){
        if(n==row){
            result.push_back(checkpoint);
            return;
        }
        for(int i=0;i<n;i++){
            if(isvalid(n,i,row,checkpoint)){//n是总行数列数，i是当前列数，row是当前行数
                checkpoint[row][i]='Q';
                huisu(n,row+1,checkpoint);
                checkpoint[row][i]='.';
            }
        }
    }
    bool isvalid(int n ,int col ,int row , vector<string> checkpoint){
        for(int i=0;i<row;i++){
            if(checkpoint[i][col]=='Q'){
                return false;
            }
        }
        //45度
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(checkpoint[i][j]=='Q'){
                return false;
            }
        }
        //135度
        for(int i=row-1, j=col+1;i>=0&&j<n;i--,j++){
            if(checkpoint[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        std::vector<std::string> checkpoint(n,std::string(n,'.'));
        result.clear();
        huisu(n,0,checkpoint);
        return result;
    }
};

注意初始化checkpoint的时候，要使用相关stl的构造函数。

整体上该题思路不是很难。