c++回溯法n皇后问题并用递归及迭代两种方法实现

C++ 回溯法解决 N 皇后问题，可以使用递归和迭代两种方法实现。

首先，我们需要定义一个二维数组表示棋盘，初始化为0表示该位置没有皇后。然后，我们从第一行开始逐行放置皇后，对于每一行，我们需要检查该行的每一列是否可以放置皇后，如果可以，则在该位置放置皇后，并递归进入下一行；如果不行，则回溯到上一行，继续尝试其他列。

1. 递归解法

#include <iostream>
using namespace std;

const int N = 10;

int ans = 0;
int board[N][N];

void dfs(int row) {
    if (row == N) {
        ans++;
        return;
    }

    for (int col = 0; col < N; col++) {
        bool flag = true;
        for (int i = 0; i < row; i++) {
            if (board[i][col] || (col - row + i >= 0 && board[i][col - row + i]) || (col + row - i < N && board[i][col + row - i])) {
                flag = false;
                break;
            }
        }

        if (flag) {
            board[row][col] = 1;
            dfs(row + 1);
            board[row][col] = 0;
        }
    }
}

int main() {
    dfs(0);
    cout << ans << endl;
    return 0;
}

2. 迭代解法

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

const int N = 10;

int ans = 0;
int board[N][N];

struct Node {
    int row;
    int col;
    int state;
    Node(int i, int j, int s): row(i), col(j), state(s) {}
};

void dfs() {
    stack<Node> s;
    s.push(Node(0, 0, 0));

    while (!s.empty()) {
        Node node = s.top();
        s.pop();

        int row = node.row;
        int col = node.col;
        int state = node.state;

        if (row == N) {
            ans++;
            continue;
        }

        if (state == 0) { // 第一次访问节点
            for (int c = 0; c < N; c++) {
                bool flag = true;
                for (int i = 0; i < row; i++) {
                    if (board[i][c] || (c - row + i >= 0 && board[i][c - row + i]) || (c + row - i < N && board[i][c + row - i])) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    s.push(Node(row, col, 1));
                    s.push(Node(row + 1, c, 0));
                    board[row][c] = 1;
                    break;
                }
            }
        } else { // 第二次访问节点
            board[row][col] = 0;
        }
    }
}

int main() {
    dfs();
    cout << ans << endl;
    return 0;
}