N皇后C++非递归实现

以下是 N 皇后问题的 C++ 非递归实现代码，使用了迭代加深搜索算法：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;

int n, ans;
int col[N], dia[N], udia[N];  // 分别表示列、正对角线、反对角线是否被占用

int dfs() {
    int path[N], top = -1;
    memset(col, 0, sizeof col);
    memset(dia, 0, sizeof dia);
    memset(udia, 0, sizeof udia);
    int cnt = 0;  // 记录当前摆放皇后的数量
    for (int i = 0; i < n; i++) {
        path[++top] = i;  // 将第一行皇后放在第 i 列
        col[i] = dia[i + top] = udia[n - i + top] = 1;  // 标记列、对角线
        cnt++;
    }
    while (top >= 0) {
        int u = path[top--];  // 取出栈顶元素
        cnt--;
        for (int i = u + 1; i < n; i++) {
            if (!col[i] && !dia[i - u + N] && !udia[n - i - u + N]) {
                path[++top] = i;
                col[i] = dia[i - u + N] = udia[n - i - u + N] = 1;
                cnt++;
            }
        }
        if (cnt == 0) ans++;  // 摆放了 n 个皇后，答案加 1
        while (top >= 0 && (top + n - u <= cnt)) {  // 回溯
            int j = path[top--];
            col[j] = dia[j - u + N] = udia[n - j - u + N] = 0;
            cnt--;
        }
    }
    return ans;
}

int main() {
    cin >> n;
    cout << dfs() << endl;
    return 0;
}

这里的核心思想是使用栈来模拟回溯过程，每次将当前行可以放置皇后的列号入栈，在回溯时依次弹出栈顶元素，并将其对应的列、对角线解除标记。