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

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

#include <iostream>
using namespace std;

// 棋盘大小
const int N = 8;

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

// 回溯函数
void solveNQueens(int col, bool board[N], vector<int>& result) {
    if (col == N) {
        // 找到解决方案，添加到结果中
        result.push_back(col);
        cout << "Solution found:\n";
        for (int i = 0; i < N; i++)
            cout << board[i] << " ";
        cout << endl;
        return;
    }

    // 尝试将皇后放在当前列的所有位置
    for (int i = 0; i < N; i++) {
        if (isSafe(i, col, board)) {
            board[i] = col;
            solveNQueens(col + 1, board, result); // 继续下一个列
        }
    }
}

int main() {
    vector<int> solution;
    bool board[N];
    memset(board, 0, sizeof(board));
    solveNQueens(0, board, solution);
    return 0;
}