462
九度1254：N皇後問題
題目1254：N皇後問題
時間限製：1 秒
內存限製：128 兆
特殊判題：否
提交：566
解決：157
題目描述：
N皇後問題，即在N*N的方格棋盤內放置了N個皇後，使得它們不相互攻擊（即任意2個皇後不允許處在同一排，同一列，也不允許處在同一斜線上。因為皇後可以直走，橫走和斜走如下圖)。
你的任務是，對於給定的N，求出有多少種合法的放置方法。輸出N皇後問題所有不同的擺放情況個數。
輸入：
輸入包含多組測試數據。
每組測試數據輸入一個整數n(3<n<=13),表示有n*n的棋盤，總共擺放n個皇後。
輸出：
對於每組測試數據，輸出總共不同的擺放情況個數，結果單獨一行。
樣例輸入：
4
樣例輸出：
2
來源：
2013年王道論壇研究生機試練習賽（三）
題目數據比較水，隻到13，用深入搜索超時，但是可以得到前十三個結果，偷懶了，不過還算過了，繼續研究優化算法！
AC代碼：
#include<stdio.h>
#include<string.h>
int a[20][20],n,sum;
void Fun(int x,int n)
{
int i,j,flag,k,w;
if(x>n)
{
sum++;
return;
}
else
{
for(i=1;i<=n;i++)
{
flag=0;
for(j=1;j<x;j++)//檢測上
{
if(a[j][i]!=0)
flag=1;
}
k=x-1;w=i-1;//檢測左斜上方
while(k>0&&w>0)
{
if(a[k--][w--]!=0)
flag=1;
}
k=x-1;w=i+1;//檢測右斜上方
while(k>0&&w<=n)
{
if(a[k--][w++]!=0)
flag=1;
}
if(flag==0)
{
a[x][i]=1;
Fun(x+1,n);
a[x][i]=0;
}
}
}
}
int main()
{
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
if(n<11)
{
for(i=1;i<=n;i++)
{
a[1][i]=1;
Fun(2,n);
a[1][i]=0;
}
printf("%d\n",sum);
}
else//向後就超時了，隻能直接輸出（羞愧）
{
if(n==11)
printf("2680\n");
else if(n==12)
printf("14200\n");
else
printf("73712\n");
}
}
return 0;
}
最後更新：2017-04-03 12:56:01