八皇后问题（回溯法）

题意：在棋盘上放置8个皇后，使得它们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，要求找出所有解。

这是最经典的回溯例题了。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n = 8;
 5 int count = 0;
 6 int c[10];
 7 int ok;
 8 
 9 void search(int cur)
10 {
11     if (cur == n)   //递归边界
12     {
13         if (::count) cout << endl << endl;
14         ::count++;
15         for (int i = 0; i < n; i++)
16         {
17             for (int j = 0; j < 8; j++)
18             {
19                 if (c[i] == j) cout << "1 ";
20                 else cout << "0 ";
21             }
22             cout << endl;
23         }
24     }
25     else 
26     {
27         for (int i = 0; i < n; i++)
28         {
29             ok = 1;
30             c[cur] = i;   //尝试把第cur行的皇后放在第i列
31             for (int j = 0; j < cur; j++)
32             {
33                 if (c[cur] == c[j] || cur - c[cur] == j - c[j] || cur + c[cur] == j + c[j]) //检查列和对角线
34                 {
35                     ok = 0;
36                     break;
37                 }
38             }
39                 if (ok)  search(cur + 1); //如果合法，继续递归
40         }
41     }
42 }
43 
44 int main()
45 {
46     search(0);
47     cout << "共有" << ::count << "种解法" << endl;
48     return 0;
49 }