C++回溯算法n皇后问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后，并打印出所有的放置方法

C++的回溯算法（也称穷举法或试探法）可以有效地解决n皇后问题，这个问题的目标是在一个n×n的棋盘上放置n个皇后，使得任意两个皇后之间都不会互相攻击，即不在同一行、同一列或同一条对角线上。以下是使用回溯算法的一个基本实现：

首先，我们需要创建一个二维字符数组来代表棋盘，其中'.': 空位，'Q': 皇后。然后，我们从左上角开始尝试放置皇后，每次递增行数，如果在这个位置放置皇后不会引起冲突，则放置，否则尝试下一个位置。当我们放满一行之后，再移动到下一行继续这个过程。如果在某个时刻无法找到合适的放置位置，我们就回溯到上一步，尝试其他的位置，直到找到解决方案或者整个棋盘都尝试完毕。

下面是使用递归和非递归版本的C++代码：

**递归版本：**

#include <vector>
using namespace std;

vector<vector<char>> solveNQueens(int n, vector<vector<char>>& board, int row) {
    if (row == n) { // 当行数等于n，找到一个解，返回棋盘
        return board;
    }

    // 对每一列尝试放置皇后
    for (int col = 0; col < n; ++col) {
        // 判断当前位置是否安全（不与其他皇后冲突）
        if (isValid(board, row, col)) {
            board[row][col] = 'Q'; // 放置皇后
            vector<vector<char>> res = solveNQueens(n, board, row + 1); // 继续递归
            if (!res.empty()) { // 如果有解，返回该解
                return res;
            }
            board[row][col] = '.'; // 回溯，移除皇后
        }
    }
    return {}; // 如果没有解，返回空
}

bool isValid(vector<vector<char>>& board, int row, int col) {
    // 检查上下左右四个方向是否有冲突
    for (int i = 0; i < row; ++i)
        if (board[i][col] == 'Q') return false;
    for (int i = col; i < board.size(); ++i)
        if (board[row][i] == 'Q') return false;
    for (int i = row, j = col; i > 0 && j >= 0; --i, --j)
        if (board[i][j] == 'Q') return false;
    for (int i = row, j = col; i > 0 && j < board.size() - 1; --i, ++j)
        if (board[i][j] == 'Q') return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<vector<char>> board(n, vector<char>(n, '.'));
    board[0][0] = 'Q'; // 初始化第一行第一个位置
    vector<vector<char>> result = solveNQueens(n, board, 0);
    if (!result.empty()) {
        for (const auto& row : result)
            for (char cell : row)
                cout << cell << " ";
        cout << endl;
    } else {
        cout << "No solution found.\n";
    }
    return 0;
}

**非递归版本（迭代深化搜索）：**

// ... (其他部分代码相同)

void dfs(vector<vector<char>>& board, int depth) {
    if (depth == n) {
        for (const auto& row : board)
            for (char cell : row)
                cout << cell << " ";
        cout << endl;
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isValid(board, depth, col)) {
            board[depth][col] = 'Q';
            dfs(board, depth + 1);
            board[depth][col] = '.';
        }
    }
}

int main() {
    ... // (主函数部分，初始化棋盘，调用dfs函数)
}

当你运行上述代码，并传入特定的`n`值（如`n=4`或`n=6`），它会打印出所有合法的皇后排列方案。