N皇后问题
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
Sample Output
1
92
10
题目简单翻译：
算了吧，中文。。。。难道要我翻译成英文不成。
解题思路：深度优先搜索（dfs）
一行一行的往下搜索，如果两点(x1,y1),(x2,y2)在同一条斜线上，那么x1+y1=x2+y2或者x1-y1=x2-y2;所以我们只要判断四个条件，就能判断两个点是否能互相攻击.
代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int ans[],n,vis[][];
int sum;
bool check(int x,int n)//检查(x,n)这个点是否能被攻击到
{
return vis[][x]==&&vis[][n]==&&vis[][x+n]==&&vis[][+x-n]==;
}
void set_value(int x,int n,int value)
{
vis[][x]=vis[][n]=vis[][x+n]=vis[][+x-n]=value;
}
void dfs(int x)
{
if(x>=n)//如果已经填上了n个点，那么结果加一
{
sum++;
return;
}
for(int i=;i<n;i++)
if(check(x,i))
{
set_value(x,i,);
dfs(x+);
set_value(x,i,);
}
}
int solve(int a)
{
sum=;
memset(vis,,sizeof vis);
dfs();
return sum;
} int main()
{
memset(ans,0x3f,sizeof ans);
while(scanf("%d",&n)!=EOF&&n)
{
if(ans[n]==inf) ans[n]=solve(n);
printf("%d\n",ans[n]);
}
return ;
}
N皇后问题