N皇后问题

 1 #include <cstdio>
 2 #include <string>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <string.h>
 6 #include <math.h>
 7 
 8 using namespace std;
 9 
10 const int maxn = 100;
11 
12 int vis[maxn];
13 int cnt = 0;
14 int n;
15 
16 bool check(int row,int col)
17 {
18     for (int i=0;i<row;i++)
19     {
20         if (vis[i] == col || abs(vis[i] - col) == abs(i-row))
21             return false;
22     }
23     return true;
24 }
25 
26 void dfs(int row)
27 {
28     if (row == n)
29     {
30         cnt++;
31         return ;
32     }
33     else
34     {
35         for (int col = 0;col<n;col++)
36         {
37             if (check(row,col))
38             {
39                 vis[row] = col;
40                 dfs(row+1);
41             }
42         }
43     }
44 }
45 
46 int main()
47 {
48     int a[11];
49     for (n=1;n<11;n++)
50     {
51         dfs(0);
52         a[n] = cnt;
53         memset(vis,0, sizeof(vis));
54         cnt = 0;
55     }
56     while (cin >> n){
57         if (n == 0)
58             return 0;
59         else
60             cout << a[n] << endl;
61     }
62     return 0;
63 }