题目描述
检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
输入输出格式
输入格式:
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式:
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
输入输出样例
输出样例#1:
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int n,total; 5 int a[20],b[20],c[20],d[20]; 6 //分别表示某一行皇后的位置和标识列,对角线(从左下到右上),对角线(从左上到右下) 7 void print(){ 8 //cout<<"asdfasdf "; 9 if(total<=2){ 10 for(int k=1;k<=n;k++) 11 cout<<a[k]<<" "; 12 cout<<endl; 13 } 14 total++; 15 } 16 void queen(int i){ 17 if(i>n) { 18 print(); 19 return ; 20 } 21 for(int j=1;j<=n;j++)//尝试可能的位置 22 { 23 if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领,执行以下程序 24 { 25 a[i]=j;//标记i排是第j个 26 b[j]=1;//宣布占领纵列 27 c[i+j]=1; 28 d[i-j+n]=1; 29 //宣布占领两条对角线 30 queen(i+1);//进一步搜索,下一个皇后 31 b[j]=0; 32 c[i+j]=0; 33 d[i-j+n]=0; 34 //(回到上一步)清除标记 35 } 36 } 37 } 38 int main(){ 39 cin>>n; 40 queen(1); 41 cout<<total<<endl; 42 return 0; 43 }