N皇后問題回溯非遞回演算法 C++實作1-有解無憂

運行結果

代碼如下

 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 queen[MAX+1];
 8 
 9 void print() {
10     cout << LINE32 << endl;
11     cout << "第" << cnt << "個方案: " << endl;
12     for (int i = 1; i <= n; i++) {
13         if (i != 1) {
14             cout << ", ";
15         }
16         cout << "(" << i << "," << queen[i] << ")";
17     } 
18     cout << endl;
19     for (int i = 1; i <= n; i++) {
20         for (int j = 1; j <= n; j++) {
21             if (queen[i] != j) {
22                 cout << 'x';
23             } else {
24                 cout << 'Q';
25             }
26         }
27         cout << endl;
28     }
29 }
30 
31 bool check(int row, int col) {// 檢查是否可以在（row，col）這個坐標放置皇后 
32     for (int placed = 1; placed < row; placed++) {
33         if (queen[placed]==col || abs(row-placed)==abs(col-queen[placed])) {
34             return false;
35         }
36     }
37     return true;
38 }
39 void solve(int n) {
40     int row = 1;// row表示當前正在放置的行，初始值為1，表示從第一行開始放置皇后
41     queen[row] = 1;    // 即a[1]=1，表示初始時，先放一個皇后在（1，1）
42     while (row > 0) {// row的值最后為0，因為所有情況都檢查完時，第一行往上回溯，row值就為0
43         if (row > n) {
44             // 找到一個解，之后需要向上回溯：從上一行的下一列開始檢查 
45             cnt++;
46             if (PRINT_DETAILS) {
47                 print();
48             } 
49             queen[--row]++; 
50         } else if (queen[row] > n) {
51             // queen[row]表示的是當前row行上待檢測的列的位置 
52             // 此時row行已經全部的位置都檢查完了，同樣的向上回溯：從上一行的下一列開始檢查 
53             queen[--row]++; 
54         } else if (check(row, queen[row])) {
55             // 找到一個符合的位置，開始放置下一行，從第一列開始 
56             queen[++row] = 1; 
57         } else {
58             // 此時表示這個位置不符合，查看這一行下一列的位置
59             queen[row]++; 
60         } 
61     }
62 } 
63 
64 int main() {
65     // input
66     cout << "輸入皇后個數: "; 
67     cin >> n;
68     // compute
69     clock_t begin = clock(); 
70     solve(n); 
71     clock_t end = clock(); 
72     // output
73     cout << LINE32 << endl;
74     cout << n << "皇后問題一共有" << cnt << "種解決方案" << endl; 
75     cout << LINE32 << endl;
76     cout << "回溯非遞回演算法實作1 解決" << n << "皇后問題耗時" << /*end-begin << "打點" <<*/(double)(end-begin)/CLOCKS_PER_SEC  << "s" << endl;
77     return 0;
78 } 
79 // 14 9~11s

與回溯遞回演算法實作1對比

回溯遞回演算法實作1運行情況

回溯非遞回演算法實作1運行情況

可以看到，非遞回實作1比遞回實作1運行時間略多一些，這不符合預期，按理來說，非遞回實作運行時間應該更短，下一篇博客會再次對比非遞回實作與遞回實作，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199360.html

標籤：其他

上一篇：回溯演算法和解數獨

下一篇：第11屆藍橋杯省賽模擬單詞加密

N皇后問題 回溯非遞回演算法 C++實作1

N皇后問題回溯非遞回演算法 C++實作1