HDU 2553 N皇后问题（dfs）

N皇后问题

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

Sample Output

题目简单翻译：

算了吧，中文。。。。难道要我翻译成英文不成。

解题思路：深度优先搜索（dfs）

一行一行的往下搜索，如果两点(x1,y1),(x2,y2)在同一条斜线上，那么x1+y1=x2+y2或者x1-y1=x2-y2;所以我们只要判断四个条件，就能判断两个点是否能互相攻击.

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 int ans[12],n,vis[4][40];
 6 int sum;
 7 bool check(int x,int n)//检查(x,n)这个点是否能被攻击到
 8 {
 9     return vis[0][x]==0&&vis[1][n]==0&&vis[2][x+n]==0&&vis[3][20+x-n]==0;
10 }
11 void set_value(int x,int n,int value)
12 {
13     vis[0][x]=vis[1][n]=vis[2][x+n]=vis[3][20+x-n]=value;
14 }
15 void dfs(int x)
16 {
17     if(x>=n)//如果已经填上了n个点，那么结果加一
18     {
19         sum++;
20         return;
21     }
22     for(int i=0;i<n;i++)
23         if(check(x,i))
24         {
25             set_value(x,i,1);
26             dfs(x+1);
27             set_value(x,i,0);
28         }
29 }
30 int solve(int a)
31 {
32     sum=0;
33     memset(vis,0,sizeof vis);
34     dfs(0);
35     return sum;
36 }
37 
38 int main()
39 {
40     memset(ans,0x3f,sizeof ans);
41     while(scanf("%d",&n)!=EOF&&n)
42     {
43         if(ans[n]==inf) ans[n]=solve(n);
44         printf("%d
",ans[n]);
45     }
46     return 0;
47 }

N皇后问题