回溯法n皇后问题c++

回溯法是解决复杂搜索问题的一种算法策略，常用于求解八皇后问题这类典型的子集生成问题。八皇后问题是一个经典问题，要求在8x8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列或对角线上。在C++中，你可以使用回溯法通过递归的方式来寻找所有可能的解决方案。

以下是解决八皇后问题的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] || (row - i) == (col - board[i])) // 对角线检查
            return false;
    }
    return true;
}

// 递归放置皇后
void solveNQueens(int n, int row, std::vector<std::vector<int>>& board, std::vector<std::vector<int>>& solutions) {
    if (row == n) { // 找到解决方案，将当前棋盘加入结果中
        solutions.push_back(board);
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isSafe(row, col, board)) {
            board[row][col] = 1; // 放置皇后
            solveNQueens(n, row + 1, board, solutions); // 递归尝试下一行
            board[row][col] = 0; // 回溯，移除皇后
        }
    }
}

// 主函数入口
int main() {
    int n = 8; // 设置为8皇后问题，也可以根据需求修改
    std::vector<std::vector<int>> board(n, std::vector<int>(n, 0));
    std::vector<std::vector<int>> solutions;

    solveNQueens(n, 0, board, solutions);

    std::cout << "Number of solutions: " << solutions.size() << std::endl;
    for (const auto& solution : solutions) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                std::cout << solution[i][j] << " ";
            }
            std::cout << std::endl;
        }
        std::cout << "------------------------" << std::endl;
    }

    return 0;
}