8皇后问题的回溯算法实现C++

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

#include <iostream>
#include <vector>

using namespace std;

// 定义一个布尔数组，表示每个位置是否放了皇后
bool isSafe(vector<int>& board, int row, int col) {
    // 检查列冲突
    for (int i = 0; i < row; ++i)
        if (board[i] == col || abs(board[i] - col) == row - i)
            return false;
    return true;
}

// 回溯函数，尝试在给定行放置皇后
void solveNQueens(vector<int>& board, int row, vector<vector<bool>>& results) {
    if (row == 8) { // 如果放置到最后一行，找到了一个解
        results.push_back(board);
        return;
    }

    // 遍历每一列，尝试在当前行放置皇后
    for (int col = 0; col < 8; ++col) {
        if (isSafe(board, row, col)) {
            board[row] = col; // 放置皇后
            solveNQueens(board, row + 1, results); // 继续向下一行尝试
            board[row] = -1; // 回溯，移除皇后
        }
    }
}

// 主函数入口点
int main() {
    vector<vector<bool>> solutions(8, vector<bool>(8, false)); // 初始化解决方案数组
    vector<int> board(8, -1); // 初始化棋盘，-1表示空位

    solveNQueens(board, 0, solutions);

    cout << "8皇后问题的解有：" << endl;
    for (const auto& sol : solutions) {
        for (int i = 0; i < 8; ++i) {
            if (sol[i] != -1)
                cout << sol[i] + 1 << " ";
            else
                cout << "." << " ";
        }
        cout << endl;
    }

    return 0;
}

这个程序首先初始化了一个解决方案列表和一个8x8的棋盘矩阵，然后通过递归地尝试每一种可能性，直到找到所有可能的皇后布局。当找到一个合法的解时，就将它添加到结果集中。