1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAX = 1024;
 4 const char *LINE32 = "--------------------------------";
 5 const bool PRINT_DETAILS = false; 
 6 long long n, cnt = 0;// n表示皇后数量，cnt表示方案数量
 7 int vis[3][2*MAX+1];
 8 //v[0][]、v[1][]、v[2][]分别表示列、主对角线、副对角线是否存在皇后
 9 // 为0时表示无皇后，非0则表示有，且v[0][4]=2表示第四列第二行存在皇后 
10 
11 void print() {
12     cout << LINE32 << endl;
13     cout << "第" << cnt << "个方案: " << endl;
14     for (int i = 1; i <= n; i++) {
15         if (i != 1) {
16             cout << ", ";
17         }
18         cout << "(" << vis[0][i] << "," << i << ")";
19     } 
20     cout << endl;
21     for (int i = 1; i <= n; i++) {
22         for (int j = 1; j <= n; j++) {
23             if (vis[0][j] != i) {
24                 cout << 'x';
25             } else {
26                 cout << 'Q';
27             }
28         }
29         cout << endl;
30     }
31 }
32 
33 bool check(int row, int col) {// 检查是否可以在（row，col）这个坐标放置皇后
34     return !(vis[0][col] || vis[1][row-col+n] || vis[2][row+col]);
35 }
36 void place(int x, int y, int *r2c) {// 在（x，y）的位置上放置皇后 
37     vis[0][y] = x;
38     vis[1][x-y+n] = vis[2][x+y] = 1;
39     r2c[x] = y;
40 } 
41 void remove(int x, int y) {// 移除（x，y）位置上的皇后 
42     vis[0][y] = vis[1][x-y+n] = vis[2][x+y] = 0;
43 } 
44 void solve(int n) {// 与非递归实现1的不同点在于，A.使用了vis[3][]加快了判断，B.回溯的具体操作是在vis[3][]上而不是r2c[]上 
45     int r2c[n+5];// 存放各行所放位置的列数，其实类似于递归实现1和非递归实现1中使用的queen[] 
46     r2c[0] = 0;// 这里要初始化，否则最后要退出下面的循环时会数组越界，受影响的代码是63_42 
47     int row = 1, col = 1;
48     place(row, col, r2c);
49     row = 2;//在（1，1）的位置上放置一个皇后，然后进入循环，开始寻找第二行放置的位置
50     while (row > 0) {// row的值最后为0，因为所有情况都检查完时，第一行往上回溯，row值就为0
51         if (row > n) {
52             // 找到一个解，之后需要向上回溯：移除上一行的皇后，从上一行的下一列尝试放置皇后 
53             cnt++;
54             if (PRINT_DETAILS) {
55                 print();
56             } 
57             row--;// row返回上一行
58             remove(row, r2c[row]);// 移除上一行中的皇后
59             col = r2c[row]+1;// 此时的（row，col）为下一次尝试放置的位置 
60         } else if (col > n) {
61             // 当前row行中的每一个位置都尝试并放置了，回溯
62             row--;
63             remove(row, r2c[row]);
64             col = r2c[row]+1; 
65         } else if (check(row, col)) {
66             // 找到一个符合的位置
67             place(row, col, r2c);// 放置皇后 
68             row++;// 查找下一行放置的位置
69             col = 1;// 并且是从第一列开始放置 
70         } else {
71             // 这一列不符合，查找下一列 
72             col++; 
73         } 
74     } 
75 }
76 
77 int main() {
78     // input
79     cout << "输入皇后个数: "; 
80     cin >> n;
81     // compute
82     clock_t begin = clock(); 
83     solve(n); 
84     clock_t end = clock(); 
85     // output
86     cout << LINE32 << endl;
87     cout << n << "皇后问题一共有" << cnt << "种解决方案" << endl; 
88     cout << LINE32 << endl;
89     cout << "回溯非递归算法实现2 解决" << n << "皇后问题耗时" << /*end-begin << "打点" <<*/(double)(end-begin)/CLOCKS_PER_SEC  << "s" << endl;
90     return 0;
91 }
92 // 14 3~5s