n*n棋盘中放入个皇后C++

在n×n的棋盘上放置n个皇后的问题是一个经典的问题，也被称为“八皇后问题”（N-Queens Problem）。目标是在不互相攻击的情况下，找到所有可能的皇后布局，即每行、每列以及每个对角线都没有两个皇后。

在C++中，解决这个问题通常采用递归回溯法，这是一种搜索算法。基本思路是从第一行开始，尝试将皇后放在每一列，然后检查是否违反了其他行或对角线的规则。如果可以，继续在下一行放置；如果不可以，则回溯到上一行并尝试下一个位置。当所有的皇后都放置完毕，就找到了一种解法。最后统计所有找到的解的数量。

以下是简单的C++代码示例：

#include <iostream>
#include <vector>

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

    // 检查左上方对角线是否有皇后
    int-diag = row - col;
    for (int i = 0; i < diag; ++i)
        if (board[i][col - i])
            return false;

    // 检查右上方对角线是否有皇后
    int-diag = row + col;
    for (int i = 0; i < diag; ++i)
        if (board[row - i][col + i])
            return false;

    return true;
}

void solveNQueens(int n, int col, std::vector<std::vector<bool>>& board, std::vector<int>& res) {
    if (col == n) {
        res.push_back(std::vector<int>(board.size()));
        for (int i = 0; i < n; ++i)
            res.back()[i] = board[i][col];
        return;
    }

    for (int i = 0; i < n; ++i) {
        if (isSafe(i, col, board)) {
            board[i][col] = true;
            solveNQueens(n, col + 1, board, res);
            board[i][col] = false; // 回溯
        }
    }
}

std::vector<std::vector<int>> solveNQueens(int n) {
    std::vector<std::vector<bool>> board(n, std::vector<bool>(n, false));
    std::vector<int> res;
    solveNQueens(n, 0, board, res);
    return res;
}

int main() {
    int n = 8; // 可以修改这个值改变棋盘大小
    auto solutions = solveNQueens(n);
    std::cout << "Number of solutions: " << solutions.size() << "\n";
    for (const auto& solution : solutions) {
        for (int queen : solution)
            std::cout << queen << " ";
        std::cout << "\n";
    }
    return 0;
}