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

1 8 5 0

Sample Output

1 92 10

思路：
就是考虑皇后放置的位置，对于每一行，我们需要枚举每个可以放置皇后的位置，
而且需要判断当前位置（第i行）是否满足条件，即判断这个位置是否与放置好的前i-1行的皇后的位置相冲突，
如果冲突，说明这个位置不合适；否则的话，就可以枚举下一行皇后的位置，直至第n行。

 1 #include<stdio.h>
 2 #include<string.h> 
 3 int n,tmp;
 4 int map[11];
 5 void DFS(int k)
 6 {
 7    int i,j,flag;
 8    if(k==n+1)
 9     {
10       tmp++;
11       return;
12     }
13     else
14      {
15        for(i=1;i<=n;++i)
16         {
17            map[k]=i;             flag=1;
18            for(j=1;j<k;++j)
19             {
20               if(map[j]==i||i-k==map[j]-j||i+k==map[j]+j)   
21                 {
22                    flag=0;
23                    break;
24                  }
25              }
26            if(flag)
27                 DFS(k+1);
28         }
29      }
30  }
31  
32 int main()
33 {
34    int m;
35    int ans[11];
36    for(n=1;n<=10;++n)
37     {
38        tmp=0;
39        DFS(1);
40        ans[n]=tmp;
41     }
42     while(scanf("%d",&m),m)
43     {
44        printf("%d\n",ans[m]);
45     }
46    return 0;
47 }