8皇后问题的回溯算法实现c++代码8皇后问题的回溯算法实现c++代码简洁

8皇后问题是一个经典的回溯算法案例，目标是在一个8x8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列或对角线上。下面是一个简单的C++回溯算法实现：

#include <iostream>
#include <vector>

// 检查当前位置是否冲突
bool isSafe(int row, int col, std::vector<std::vector<int>>& board) {
    // 检查列是否有冲突
    for (int i = 0; i < row; ++i)
        if (board[i][col] == 1)
            return false;

    // 检查左上方对角线是否有冲突
    int di = row - col;
    while (di >= 0 && board[di][col] == 1)
        di--;

    // 检查右上方对角线是否有冲突
    di = row + col;
    while (di < 8 && board[di][col] == 1)
        di++;

    return true;
}

// 递归函数，放置皇后
void solveNQueens(std::vector<std::vector<int>>& board, int n, int row) {
    if (row == n) { // 找到解，打印矩阵
        for (int& val : board)
            for (int val2 : val)
                std::cout << val2 << " ";
        std::cout << "\n";
        return;
    }

    // 依次尝试每一列
    for (int col = 0; col < n; ++col) {
        if (isSafe(row, col, board)) {
            board[row][col] = 1; // 放置皇后
            solveNQueens(board, n, row + 1); // 继续寻找下一个位置
            board[row][col] = 0; // 回溯，移除皇后
        }
    }
}

int main() {
    int n = 8;
    std::vector<std::vector<int>> board(n, std::vector<int>(n, 0));
    solveNQueens(board, n, 0);
    return 0;
}