回溯法

 1 Backtrack(int t) // 子集树
 2 {
 3     if (t > n)
 4     {
 5         output(X);
 6     }
 7     else
 8     {
 9         while (all Xt)//Xt为X[t]的合法取值
10         {
11             X[t] = Xt;
12             if (Constraint(t) and Bound(t))
13             {
14                 Backtrack(t + 1);
15             }
16         }
17     }
18 }

 1 Backtrack(int t) // 排列树
 2 {
 3     if (t > n)
 4     {
 5         output(X);
 6     }
 7     else
 8     {
 9         for (int i = t; i <= n; i++)
10         {
11             swap(X[t], X[i]);
12             if (Constraint(t) and Bound(t))
13             {
14                 Backtrack(t + 1);
15             }
16             swap(X[t], X[i]);
17         }
18     }
19 }

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 
 5 bool placetest(int k, int x[])
 6 {
 7     for (int i = 0; i < k; i++)
 8     {
 9         if (x[i] == x[k] || abs(x[i] - x[k]) == abs(i - k))
10         {
11             return false;
12         }
13     }
14     return true;
15 }
16 
17 void NQueen(int k, int n, int x[])
18 {
19     if (k < 0 || n <= 0 || x == NULL)
20     {
21         return;
22     }
23     if (k >= n)
24     {
25         for (int i = 0; i < n; i++)
26         {
27             cout << x[i] + 1 << " ";
28         }
29         cout << endl;
30     }
31     else
32     {
33         for (int i = 0; i < n; i++)
34         {
35             x[k] = i;
36             if (placetest(k, x))
37             {
38                 NQueen(k + 1, n, x);
39             }
40         }
41     }
42 }
43 
44 int main()
45 {
46     int x[8];
47     NQueen(0, 8, x);
48     return 0;
49 }