C++写一个代码dfs解决八皇后问题

在C++中，我们可以使用深度优先搜索（Depth-First Search，DFS）算法来解决经典的八皇后问题。这是一个典型的回溯法应用，目标是在8x8的棋盘上放置8个皇后，使得任意两个皇后不在同一行、同一列或对角线上。

以下是一个简单的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

// 检查某行、列或对角线是否已经有皇后
bool isSafe(vector<vector<bool>>& board, int row, int col) {
    // 检查列冲突
    for (int i = 0; i < row; ++i)
        if (board[i][col])
            return false;
    
    // 检查左上方对角线冲突
    int di = -1,dj = 1;
    while (row + di >= 0 && col + dj >= 0) {
        if (board[row + di][col + dj])
            return false;
        di += 2;
        dj += 2;
    }
    
    // 检查右上方对角线冲突
    di = 1, dj = 1;
    while (row + di < board.size() && col + dj < board[0].size()) {
        if (board[row + di][col + dj])
            return false;
        di += 2;
        dj += 2;
    }

    return true;
}

// 递归函数，将皇后放在指定位置
void solveNQueens(vector<vector<bool>>& board, int n, int row) {
    if (row == n) { // 如果放置完所有皇后，找到一种解决方案
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j)
                cout << (board[i][j] ? "Q" : ".");
            cout << endl;
        }
        cout << "Solution found!" << endl;
        return;
    }

    // 尝试每个列
    for (int col = 0; col < n; ++col) {
        if (isSafe(board, row, col)) {
            board[row][col] = true; // 设置皇后位置

            // 继续在下一行尝试
            solveNQueens(board, n, row + 1);

            // 回溯，如果当前路径无效，则撤销这一步
            board[row][col] = false;
        }
    }
}

int main() {
    const int N = 8;
    vector<vector<bool>> board(N, vector<bool>(N, false));
    solveNQueens(board, N, 0);
    return 0;
}

在这个代码中，`solveNQueens`函数递归地寻找解决方案，`isSafe`函数检查当前位置是否安全。当找到一个解后，它会打印出棋盘布局并输出“Solution found!”。