题目描述:
一个如下的6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
请输出前 3 个解。最后一行是解的总个数。
#include<iostream>
using namespace std;
int n;
int ans[15][2];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int count,sum;
void dfs(int a=1,int b=1){
for(int i=1;i<=count;i++){
if(a==ans[i][0]||b==ans[i][1])
return;
int k=1.0*(ans[i][1]-b)/(ans[i][0]-a);
if(k==1||k==-1)
return;
}
count++;
ans[count][0]=a;
ans[count][1]=b;
if(count==n){
for(int i=1;i<=n;i++)
cout<<ans[i][1]<<" ";
sum++;
return;
}
for(int i=0;i<4;i++){
a+=dir[i][0];
b+=dir[i][1];
if(a>=1&&a<=n&&b>=1&&b<=n){
dfs(a,b);
a-=dir[i][0];
b-=dir[i][1];
}
}
}
int main(){
cin>>n;
dfs();
cout<<sum;
return 0;
}