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

运行结果

代码如下

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;
const char *LINE32 = "--------------------------------";
const bool PRINT_DETAILS = false; 
long long n, cnt = 0;// n表示皇后数量，cnt表示方案数量 
int queen[MAX+1];

void print() {
    cout << LINE32 << endl;
    cout << "第" << cnt << "个方案: " << endl;
    for (int i = 1; i <= n; i++) {
        if (i != 1) {
            cout << ", ";
        }
        cout << "(" << i << "," << queen[i] << ")";
    } 
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (queen[i] != j) {
                cout << 'x';
            } else {
                cout << 'Q';
            }
        }
        cout << endl;
    }
}

bool check(int row, int col) {// 检查是否可以在（row，col）这个坐标放置皇后 
    for (int placed = 1; placed < row; placed++) {
        if (queen[placed]==col || abs(row-placed)==abs(col-queen[placed])) {
            return false;
        }
    }
    return true;
}
void solve(int n) {
    int row = 1;// row表示当前正在放置的行，初始值为1，表示从第一行开始放置皇后
    queen[row] = 1;    // 即a[1]=1，表示初始时，先放一个皇后在（1，1）
    while (row > 0) {// row的值最后为0，因为所有情况都检查完时，第一行往上回溯，row值就为0
        if (row > n) {
            // 找到一个解，之后需要向上回溯：从上一行的下一列开始检查 
            cnt++;
            if (PRINT_DETAILS) {
                print();
            } 
            queen[--row]++; 
        } else if (queen[row] > n) {
            // queen[row]表示的是当前row行上待检测的列的位置 
            // 此时row行已经全部的位置都检查完了，同样的向上回溯：从上一行的下一列开始检查 
            queen[--row]++; 
        } else if (check(row, queen[row])) {
            // 找到一个符合的位置，开始放置下一行，从第一列开始 
            queen[++row] = 1; 
        } else {
            // 此时表示这个位置不符合，查看这一行下一列的位置
            queen[row]++; 
        } 
    }
} 

int main() {
    // input
    cout << "输入皇后个数: "; 
    cin >> n;
    // compute
    clock_t begin = clock(); 
    solve(n); 
    clock_t end = clock(); 
    // output
    cout << LINE32 << endl;
    cout << n << "皇后问题一共有" << cnt << "种解决方案" << endl; 
    cout << LINE32 << endl;
    cout << "回溯非递归算法实现1 解决" << n << "皇后问题耗时" << /*end-begin << "打点" <<*/(double)(end-begin)/CLOCKS_PER_SEC  << "s" << endl;
    return 0;
} 
// 14 9~11s

与回溯递归算法实现1对比

回溯递归算法实现1运行情况

回溯非递归算法实现1运行情况

可以看到，非递归实现1比递归实现1运行时间略多一些，这不符合预期，按理来说，非递归实现运行时间应该更短。下一篇博客会再次对比非递归实现与递归实现。