1752 - N皇后问题 checker [3*]
时间限制 : 1 秒
内存限制 : 128 MB
在一个N*N的国际棋盘上，放置N个皇后，使她们相互之间不能进攻（任意两皇后不能位置同一行、同一列、同一斜线）。
因为每行只有一个皇后，我们可以用一行N个数值来表示N*N棋盘上皇后位置。
结果中第i列的数值j表示棋盘上第[i,j]位置上有一个皇后。
2 4 6 1 3 5
表示棋盘上第[1,2]、[2,4]、[3,6]、[4,1]、[5,3]、[6,5]位置上有一个皇后。
<b><span>Input</span> </b>
<span> N <br />
（6≤N≤13）
<b><span>Output</span> </b>
<span> 前三行为先得到的三组解， <br />
每组解为N个数，之间用空格隔开。
最后一行为总解数。
<b><span>Sample Input</span> </b>
6
<b><span>Sample Output</span> </b>
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
<b><span>Hint</span> </b>
<span> 对行、列、\斜 、/斜进行编号，然后用下标标记法直接查找判重</span>
题目输入
题目输出
输入/输出样例
输入格式
输出格式
C语言解答
#include "stdio.h" int a[13]; int b[13]={0},c[26]={0},d[26]={0}; int n,flag=0,s=0; void F(int t) { int i; if(t==n) { flag++; s++; if(flag<=3) { for(i=0;i<n-1;i++) printf("%d ",a[i]+1); printf("%d\n",a[n-1]+1); } } else { for(a[t]=0;a[t]<n;a[t]++) { if(b[a[t]]==0&&c[n-a[t]+t]==0&&d[a[t]+t]==0) { b[a[t]]=1; c[n-a[t]+t]=1; d[a[t]+t]=1; F(t+1); b[a[t]]=0; c[n-a[t]+t]=0; d[a[t]+t]=0; } } } } int main() { scanf("%d",&n); for(a[0]=0;a[0]<n;a[0]++) { b[a[0]]=1; c[n-a[0]]=1; d[a[0]]=1; F(1); b[a[0]]=0; c[n-a[0]]=0; d[a[0]]=0; } printf("%d\n",s); return 0; }
C++解答
#include <iostream> #include <cmath> #include <cstring> using namespace std; int n,k=1,x=0; int s[15],a[15],b[30],c[30]; bool check(int h) { if (a[s[h]]==1 || b[h-s[h]+n]==1 || c[h+s[h]]==1) return 0; else return 1; } int clear() { for (int i=1;i<=15;i++) a[i]=0; for (int i=1;i<=30;i++) b[i]=0; for (int i=1;i<=30;i++) c[i]=0; } int main() { cin>>n; s[k]=1; while (k>0) { while (!check(k) && s[k]<=n) s[k]++; if (s[k]<=n){a[s[k]]=1; b[k-s[k]+n]=1; c[k+s[k]]=1; k++; s[k]=1;} else{k--; a[s[k]]=0; b[k-s[k]+n]=0; c[k+s[k]]=0; s[k]++;} if (k==n+1) {x+=1; if (x<=3) { for (int i=1;i<=n-1;i++) cout<<s[i]<<" "; cout<<s[n]; cout<<endl; } k--;a[s[k]]=0; b[k-s[k]+n]=0; c[k+s[k]]=0; s[k]++; } } cout<<x<<endl; // system ("pause"); return 0; }