N皇后问题 回溯递归算法 C++实现2

 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 row) {// 在第row行上放置皇后
37     if (row > n) {
38         cnt++;
39         if (PRINT_DETAILS) {
40             print();
41         }
42     } else {
43         for (int col = 1; col <= n; col++) {
44             if (check(row, col)) {
45                 vis[0][col] = row;
46                 vis[1][row-col+n] = vis[2][row+col] = 1;
47                 place(row+1);
48                 vis[0][col] = vis[1][row-col+n] = vis[2][row+col] = 0;
49             }
50         }
51     }
52 } 
53 
54 int main() {
55     // input
56     cout << "输入皇后个数: "; 
57     cin >> n;
58     // compute
59     clock_t begin = clock(); 
60     place(1);
61     clock_t end = clock(); 
62     // output
63     cout << LINE32 << endl;
64     cout << n << "皇后问题一共有" << cnt << "种解决方案" << endl; 
65     cout << LINE32 << endl;
66     cout << "回溯递归算法实现2 解决" << n << "皇后问题耗时" << /*end-begin << "打点" <<*/(double)(end-begin)/CLOCKS_PER_SEC  << "s" << endl;
67     return 0;
68 } 
69 // 14 3~5s