题解 | #N皇后问题#

//设置全局变量，记录N皇后的摆放个数
int count=0;
//判断当前位置是否满足条件，不同行，不同列也不在同一条斜线上
//注意，这里的参数需要已经保存的路径path，以及当前的行列
bool isOK(vector<int> &path,int row,int col){
    //遍历之前的行，判断每行里面是否有和当前位置冲突的皇后存在，
    //如果有，则当前位置不能放置皇后，返回false
    for(int i=0;i<row;i++){
        //这里只需要判断不同列的要求，因为当前行还没有放置元素
        //而且递归回溯调用确保每行只选取一个皇后
        //此外需要判断两条斜对角线上是否存在皇后
        //两条对角线上的元素分别和相等，以及差值相等，据此可以判断对角线元素
        if(col==path[i]||i+path[i]==row+col||i-path[i]==row-col)
            return false;
    }
    //当循环结束依然没有返回时，说明之前行的皇后与当前位置不冲突，返回true
    return true;
}
//递归回溯操作，每次一行（一层，深度+1）
//此时的参数，需要传递已经保存的行列位置
//以及网格的大小和当前行，用于递归的跳出，并进行下一次递归
//这里的row和组合里的start作用挺相似的，不对
//感觉这里的row是可以省略的，和排列问题里的deepth是相似的
//row可以使用path.size()代替，
void dfs(vector<int> &path,int n){
    //递归终止条件，当深度到最后一行时，说明此时完成了一次摆放方式
    //计数+1，直接返回，也可以使用path的大小判断
    if(path.size()==n){
        count++;
        return ;
    }
    //for循环遍历path.size()行的列元素，
    //也就是在path.size()行选取有效的位置
    for(int i=0;i<n;i++){
        //判断当前位置（path.size(),i）是否为有效位置
        //如果不是则选择下一列继续测试，直到找到有效位置
        //如果全部位置都不合适，就不会进行下一层的搜索，直接返回上一层继续循环
        //这里循环结束也能跳出递归
        if(!isOK(path,path.size(),i)){
            continue;                
        }
        //将找到的合适位置存储起来，其中下标表示行数，值表示列数
        path.push_back(i);
        //递归进入下一次
        dfs(path,n);
        //回溯操作
        path.pop_back();
    }
}
int Nqueen(int n) {
    //这个变量用于存储每行中选取的列数值
    //形象点描述就是每层选的数值
    vector<int> path;
    //调用递归函数
    dfs(path, n);
    //返回结果
    return count;
}