N皇后问题

#include<bits/stdc++.h>
using namespace std;
const int maxn=10;
int a[maxn];//a[i]表示第i行上的皇后放于a[i]列上，假设a[3]=7:放在第3行第7列上
int cnt=0,n;
bool check(int x,int y){
    for(int i=1;i<=x;i++){
        if(a[i]==y){//如果该列已经放置过皇后，就false
            return false;
        }
        if(i+a[i]==x+y){//上对角线,和相等
            return false;
        }
        if(i-a[i]==x-y){//下对角线，差相等
            return false;
        }
    }
    return true;
}
void dfs(int row){
    if(row==n+1){
        cnt++;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(check(row,i)){
            a[row]=i;
            dfs(row+1);//递归到头，遍历了一遍，找到了一个解
            a[row]=0;//回收，便于找下一组解
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<cnt<<endl;
    return 0;
}

//输入：8
//输出：92