题解 | #N皇后问题#

class Solution {
public:
    int Nqueen(int n) {
        //columnindex为表示八皇后摆法的数组
        //columnindex的数组下标代表第几列
        //columnindex[i]=j，代表第i列的第j行摆下一枚皇后
        //由于是n皇后问题，我们所需的合法样例中，n*n的棋盘必然恰好摆下n个皇后，且行列不重合
        //因此，只要得到columnindex的全排列，再校验每个结果是否合法（存在斜线冲突）
        vector<int> columnindex;
        columnindex.resize(n);
        //初始化columnindex
        for(int i=0;i<n;i++){
            columnindex[i]=i;
        }
        vector<vector<int>> res;
        permutation(columnindex,0,res,n);
	    //本题目不要求输出n皇后的具体排布，故只输出size（）即可，事实上算法获得了所有具体的排布方式
        return res.size();     
    }
    //输出【无重复】元素字符串的全排列，并使用check函数审查是否是合格n皇后
    void permutation(vector<int> array,int index,vector<vector<int>>& res,int n){
        if(index==n){
            //检查是否是合规的皇后摆法（即检查对角线）
            if(check(array,n)){
                res.push_back(array);
            }
            return;
        }
        for(int i=index;i<n;i++){
            swap(array[i],array[index]);
            permutation(array,index+1,res,n);
            swap(array[i],array[index]);
        }
    }
    bool check(vector<int> array,int n){
        //对于每个(行坐标，列坐标) (array[i],i)
        for(int i=0;i<n;i++){
            //检查其与(array[j],j)是否在一条斜线上，两种情况，  
            for(int j=i+1;j<n;j++){
                if((array[i]-array[j])==(i-j)){     //1 平行对角线的斜线
                    return false;
                }else if((array[i]-array[j])==(j-i)){//2 垂直对角线的斜线
                    return false;
                }
            }
        }
        return true;
    }
};