经 典 题

思路

我们用 $a[i]$ 表示第 $i$ 行是哪个棋子，$f1[i]$ 表示第 $i$ 列是否有棋子。

难点就在于判断对角线上，我们可以发现由左上到右下的对角线满足行号-列号都是定值，右上到左下的对角线满足行号+列号都是定值。那么我们就可以利用这一点来判断，第 $i$ 行 $j$ 列的棋子处于 $i-j$ 和 $i+j$ 这两条对角线上。但需要注意，$i-j$ 可能出现负值，需要 $+n$ 来避免，$i+j$ 也有可能 $>n$，所以这两个数组都要开成 $2\times N$ 的。

由于我们枚举棋子的排列就是按照字典序枚举的，所以输出得到的前三个答案即可。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=15;
ll n,a[N],ans;
bool f1[N],f2[N*2],f3[N*2];
void dfs(ll x){
    if(x==n+1){
        ans++;
        if(ans<=3)
            for(ll i=1;i<=n;i++)
                printf("%lld%c",a[i],i==n?'\n':' ');
        return;
    }
    for(ll i=1;i<=n;i++)
        if(!f1[i]&&!f2[x-i+n]&&!f3[x+i]){
            a[x]=i,f1[i]=f2[x-i+n]=f3[x+i]=1;
            dfs(x+1);
            f1[i]=f2[x-i+n]=f3[x+i]=0;
        }
}
int main(){
    scanf("%lld",&n);
    dfs(1);
    printf("%lld",ans);
    return 0;
}