题解 | #N皇后问题#

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int r[20];// 第 x 行是否已经有皇后
int d1[40];// 主对角线是否有皇后,同一条主对角线满足：x-y 相等
int d2[40];// 副对角线是否有皇后,同一条副对角线满足：x+y 相等
// dfs(y)表示正在放第几列
void dfs(int y){
    if(y>n){
        ans++;
        return;
    }
    // 枚举这一列放哪一行
    for(int x=1;x<=n;x++){
        // 同行 or 对角线冲突
        if(r[x]||d1[x-y+n]||d2[x+y])
            continue;
        // 放皇后
        r[x]=1;
        d1[x-y+n]=1;
        d2[x+y]=1;
        dfs(y+1);// 放下一列
        // 回溯：撤销当前皇后
        r[x]=0;
        d1[x-y+n]=0;
        d2[x+y]=0;
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}