回溯从小到大枚举每一行棋子的位置,判断棋子间是否冲突即可(一开始判断是否冲突的judge函数写成枚举新棋子和之前的棋子是否同列同斜率,在13漂亮的tle了),因每一列每一对角线都只能有一颗棋子,故可以用状态压缩优化判断函数,col为列状态,dg为主对角线状态,udg为副对角线状态。由于是从小到大搜的每种情况,所以先搜到的情况字典序一定小于后搜到的情况,故依次输出前三个情况,再输出总数。
#include<cstdio>
#include<vector>
using namespace std;
int n,cnt,col,dg,udg,pos;
int ans[15];
bool judge(int i){
if(!pos) return 1;
//printf("%d %d %d",!(col & 1<<i),!(dg & 1<<pos+i),!(udg & 1<<pos+n-i-1));
return !(col & 1<<i)&&!(dg & 1<<pos+i)&&!(udg & 1<<pos+n-i-1);
}
void backstack(){
if(pos==n){
cnt++;
if(cnt<=3){
for(int i=0;i<pos;i++) printf("%d ",ans[i]);
printf("\n");
}
return;
}
for(int i=1;i<=n;i++){
if(judge(i)) {
col ^= 1<<i;
dg ^= 1<<pos+i;
udg^=1<<pos+n-i-1;
ans[pos++]=i;
backstack();
pos--;
col ^= 1<<i;
dg ^= 1<<pos+i;
udg^=1<<pos+n-i-1;
}
}
if(!pos) return;
}
int main(){
scanf("%d",&n);
backstack();
printf("%d",cnt);
return 0;
}