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

8皇后问题是一个经典的回溯法问题，目标是在一个8x8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列，以及同一条对角线上。以下是C++中使用回溯法解决8皇后问题的一个简单实现：

#include <iostream>
using namespace std;

// 检查是否可以将皇后放在当前位置
bool isSafe(int row, int col, vector<vector<bool>>& board) {
    // 检查列冲突
    for (int i = 0; i < row; ++i)
        if (board[i][col])
            return false;
    
    // 检查左上方对角线冲突
    int-diag = row - col;
    for (int i = 0; i < diag; ++i)
        if (board[i][i + diag])
            return false;
            
    // 检查右上方对角线冲突
    int-right_diag = row + col;
    for (int i = 0; i < right_diag - row; ++i)
        if (board[i][right_diag - i - 1])
            return false;
    
    return true;
}

// 递归放置皇后
void solveNQueens(int row, vector<vector<bool>>& board) {
    // 如果所有皇后都已放置完成，则成功找到解
    if (row == 8) {
        printSolution(board);
        return;
    }

    // 遍历每一列，尝试将皇后放置在该列
    for (int col = 0; col < 8; ++col) {
        if (isSafe(row, col, board)) {
            // 将皇后放在当前位置
            board[row][col] = true;

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

            // 回溯，如果找不到解决方案，撤销这一步
            board[row][col] = false;
        }
    }
}

// 打印解决方案
void printSolution(vector<vector<bool>>& board) {
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j)
            cout << (board[i][j] ? "Q " : ".");
        cout << endl;
    }
}

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