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
这道题有一个难点就是不允许皇后处在与棋盘边框成45角的斜线这一条件，看了别的大神的博客才发现，每一点都会处在一条斜线上，需要做的就是判断那一条斜线上是否已经存在皇后即可。
接下来枚举每一行的位置，每次都与之前所放置过的位置判断，直到找到最优位置。
额，这道题虽然用了递归的方法和DFS的名字，不过真正使用的却是回溯而已.
#include"iostream"
#include"cstring"
using namespace std;
int n;
int temp;
int a[11];
void DFS(int step)
{
if(step==n+1)
{
temp++;
return;
}
int flag;
for(int i=1;i<=n;i++)
{
a[step]=i;
flag=0;
for(int j=1;j<step;j++)
{
if(a[j]==i||i-step==a[j]-j||i+step==a[j]+j)
{
flag=1;
break;
}
}
if(flag==0) {DFS(step+1);}
}
}
int main()
{
int ans[11];
for(n=1;n<=10;n++)
{
temp=0;
memset(a,0,sizeof(a));
DFS(1);
ans[n]=temp;
}
int m;
while(cin>>m&&m)
cout<<ans[m]<<endl;
return 0;
}
翻了翻紫书，发现有DFS的解题方法，相较回溯而言，效率高了一些
回溯：46ms
DFS：31ms
#include"iostream"
#include"cstring"
using namespace std;
int n;
int temp;
int book[110][110];
void DFS(int step)
{
if(step==n+1)
{
temp++;
return;
}
for(int i=1;i<=n;i++)
{
if(!book[0][i]&&!book[1][step+i]&&!book[2][step-i+n])
{
//a[step]=i;
book[0][i]=book[1][step+i]=book[2][step-i+n]=1;
DFS(step+1);
book[0][i]=book[1][step+i]=book[2][step-i+n]=0;
}
}
}
int main()
{
int ans[11];
for(n=1;n<=10;n++)
{
temp=0;
memset(book,0,sizeof(book));
DFS(1);
ans[n]=temp;
}
int m;
while(cin>>m&&m)
cout<<ans[m]<<endl;
return 0;
}