C++,N皇后问题代码

在C++中解决N皇后问题的一种常见方法是使用深度优先搜索（DFS）或者广度优先搜索（BFS），这里以DFS为例给出一个简单的解决方案：

#include <iostream>
#include <vector>

using namespace std;

// 定义一个数组用于记录某一列是否有皇后
bool isSafe(int row, int col, vector<vector<int>>& board) {
    // 检查同一列是否有皇后
    for (int i = 0; i < row; ++i)
        if (board[i][col])
            return false;
    // 检查左上方对角线是否有皇后
    int rowOffset = row - col;
    for (int i = 0; i <= rowOffset; ++i)
        if (board[row-i][col+i])
            return false;
    // 检查右上方对角线是否有皇后
    rowOffset = row + col;
    for (int i = 0; i <= rowOffset; ++i)
        if (board[row-i][col-i])
            return false;
    return true;
}

void solveNQueens(int n, vector<vector<int>>& board, int row) {
    if (row == n) {
        // 打印解决方案
        for (const auto& row : board)
            for (int num : row)
                cout << num << " ";
        cout << endl;
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (isSafe(row, col, board)) {
            // 将皇后放在当前位置
            board[row][col] = 1;
            // 继续向下一行放置
            solveNQueens(n, board, row+1);
            // 回溯，如果当前行没有放好皇后，则移除并尝试下一个位置
            board[row][col] = 0;
        }
    }
}

int main() {
    int n;
    cout << "请输入N: ";
    cin >> n;
    vector<vector<int>> board(n, vector<int>(n, 0));
    solveNQueens(n, board, 0);
    return 0;
}

这段代码首先读取用户输入的N值，然后通过递归函数`solveNQueens`寻找所有可能的解决方案。每个函数调用时，它会在给定的行数下尝试将皇后放在每一列，同时检查是否满足条件，如果不满足则回溯。