八皇后问题

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 const int M=1e4+10;
 5 
 6 int cnt=0, n=0;
 7 int seq[M] = {0};
 8 bool vis[M] = {false};
 9 
10 void Nqueens(int index)
11 {
12     if(index == n+1)
13     {
14         bool flag = true;
15         for(int i=1; i<=n; i++)
16         {
17             for(int j=i+1; j<=n; j++)
18             {
19                 if(abs(i-j) == abs(seq[i]-seq[j])){
20                     flag = false;
21                     break;
22                 }
23             }
24             if(flag == false)
25                 break;
26         }
27         if(flag == true)
28         {
29             cnt++;
30             for(int i=1; i<=n; i++)
31                 printf("%d ", seq[i]);
32             printf("\n");
33         }
34     }
35     else
36     {
37         for(int i=1; i<=n; i++)    //第i行
38         {
39             if(vis[i] == false) 　　//第i行未放置皇后
40             {
41                 bool flag = true;  //第i行放置的皇后与之前的不冲突
42                 for(int pre=1; pre<index; pre++) 　　//遍历之前的皇后，检查与第i行的皇后是否冲突
43                 {
44                     if(abs(pre-index) == abs(seq[pre]-i))  //第index列i行， 第pre列seq[pre]行
45                     {
46                         flag = false;
47                         break;      //冲突，则放弃该位置，继续选择下一列
48                     }
49                 }
50 
51                 if(flag == true)
52                 {
53                     seq[index] = i;
54                     vis[i] = true;
55 
56                     Nqueens(index+1);
57                     vis[i] = false;
58                 }
59             }
60         }
61     }
62 }
63 
64 int main()
65 {
66     scanf("%d", &n);
67 
68     Nqueens(1);
69     printf("Answer: %d\n", cnt);
70 
71     return 0;
72 }