N皇后问题C++递归解法2

佚名 4年前 (2020-04-18) 算法 735人围观抢沙发百度已收录

运行结果：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码如下：

 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];    // v[0][]、v[1][]、v[2][]分别表示列、主对角线、副对角线是否存在皇后
 8                         // 为0时表示无皇后，非0则表示有，且v[0][4]=2表示第四列第二行存在皇后 
 9 
10 void print() {
11     cout << LINE32 << endl;
12     cout << "第" << cnt << "个解法: " << endl;
13     for (int i = 1; i <= n; i++) {
14         if (i != 1) {
15             cout << ", ";
16         }
17         cout << "(" << vis[0][i] << "," << i << ")";
18     } 
19     cout << endl;
20     for (int i = 1; i <= n; i++) {
21         for (int j = 1; j <= n; j++) {
22             if (vis[0][j] != i) {
23                 cout << 'x';
24             } else {
25                 cout << 'Q';
26             }
27         }
28         cout << endl;
29     }
30 }
31 
32 bool check(int row, int col) {    // 检查是否可以在（row，col）这个坐标放置皇后
33     return !(vis[0][col] || vis[1][row-col+n] || vis[2][row+col]);
34 }
35 void place(int row) {            // 在第row行上放置皇后
36     if (row > n) {
37         cnt++;
38         if (PRINT_DETAILS) {
39             print();
40         }
41     } else {
42         for (int col = 1; col <= n; col++) {
43             if (check(row, col)) {
44                 vis[0][col] = row;
45                 vis[1][row-col+n] = vis[2][row+col] = 1;
46                 place(row+1);
47                 vis[0][col] = vis[1][row-col+n] = vis[2][row+col] = 0;
48             }
49         }
50     }
51 } 
52 
53 int main() {
54     // input
55     cout << "输入皇后个数: "; 
56     cin >> n;
57     // compute
58     clock_t begin = clock(); 
59     place(1);
60     clock_t end = clock(); 
61     // output
62     cout << LINE32 << endl;
63     cout << n << "皇后问题一共有" << cnt << "种解决方案" << endl; 
64     cout << LINE32 << endl;
65     cout << "递归解法2 解决" << n << "皇后问题耗时" << /*end-begin << "打点" <<*/(double)(end-begin)/CLOCKS_PER_SEC  << "s" << endl;
66     return 0;
67 } 
68 // 14 3~4s