N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5563 Accepted Submission(s): 2518
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1 8 5 0
Sample Output
1 92 10
思路：
给棋盘的行和列都编上1到N的号码，皇后也给编上1到N的号码。
由于一个皇后应在不同的行上，为不失一般性，可以假定第i个皇后将放在第i行上的某列。
因此N皇后问题的解空间可以用一个N元组（X1，X2，.....Xn）来表示，其中Xi是放置皇后i所在的列号。
这意味着所有的解都是N元组（1，2，3，.......，N）的置换。解空间大小为N！。
其次我们看约束条件：因为解空间已经给我们排除了不在同一行（因为每个皇后分别已经对应不同的行号）的约束条件。
我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号，所以如果存在X（k）=X（i）那么肯定存在第k个皇后和第i个皇后同列。所以不同列的判段条件是X（k）！=X（i），1<k<i 。又因为同一斜线的特征是要么行号和列号之和不变（右高左低）要么是行号和列号只差相等（左高右低），所以同斜线的判断条件是 i+X（i）= k+X（k) 或 i-X(i) =k-X(k),两式合并得 |X(i)-X(k)|=|i-k|
第一次递归代码：超时
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int sum,x[11];
bool place(int k)
{
//int i;
//printf("k=%d\n",k);
//for(i=1;i<=n;i++) printf("%d ",x[i]);
// printf("\n");
int j;
for(j=1;j<k;j++)
{
if(abs(j-k)==abs(x[j]-x[k]) || x[j]==x[k] ) return false; //在同一斜线或同一列
}
return true;
}
void backtrack(int t,int n)
{
int i;
// printf("t=%d,n=%d\n",t,n);
// for(i=1;i<=n;i++) printf("%d ",x[i]);
// printf("\n");
if(t>n) {
sum++;
// printf("sum=%d\n",sum);
}
else
{
for(i=1;i<=n;i++)
{
x[t]=i;
// printf("%d\n",place(t,x));
if(place(t)) backtrack(t+1,n);
}
}
}
int main()
{
int n,i;
while(scanf("%d",&n),n)
{
sum = 0;
for(i=1;i<=n;i++) x[i]=0;
backtrack(1,n);
printf("%d\n",sum);
}
return 0;
}
第二次AC 简单打表，因为是N《= 10 ，因此用1中代码，将N等于1 to10都计算出来，放在一维数组
#include <stdio.h>
int main()
{
int a[11]={0,1,0,0,2,10,4,40,92,352,724};
int n,i;
while(scanf("%d",&n),n)
printf("%d\n",a[n]);
return 0;
}
AC代码：15MS 228KB
#include <stdio.h>
#include <math.h>
#include <iostream>
int x[11],cnt[11],n,sum;
bool flag;
void DFS(int k)//放置第k个皇后
{
int i,j,flag;
if(k>n) {//放置的皇后个数大于n时，表示一种解决方案
sum++;
return;
}
for(i=1;i<=n;i++)//将第k个皇后依次放在第1 to n列
{
flag = 1;
x[k] = i;//列値1 to n
for(j=1;j<k;j++) //依次与前1到k-1个皇后比较
{
if(x[k]==x[j]||abs(j-k)==abs(x[k]-x[j]))
{//在同一列或在同一斜线
flag = 0;
break;
}
}
if(flag) DFS(k+1);//第k个皇后与前k-1个都比交完，互不冲突再放置第k+1个皇后
}
}
int main()
{
for(n=1;n<11;n++)
{
sum =0;
DFS(1);
cnt[n] = sum;
}
while(scanf("%d",&n),n)
printf("%d\n",cnt[n]);
return 0;
}