n皇后问题 c++写

好的，下面是一个递归求解n皇后问题的C++代码：

#include<iostream>
using namespace std;

const int MAXN = 20;
int n, ans;
int col[MAXN], d1[MAXN * 2], d2[MAXN * 2];

void dfs(int row) {
    if(row > n) {
        ans++;
        return;
    }
    for(int i = 1; i <= n; i++) {
        if(!col[i] && !d1[i + row] && !d2[i - row + n]) {
            col[i] = d1[i + row] = d2[i - row + n] = 1;
            dfs(row + 1);
            col[i] = d1[i + row] = d2[i - row + n] = 0;
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}

其中，col数组表示每一列是否有皇后，d1数组表示从左上到右下的对角线是否有皇后，d2数组表示从右上到左下的对角线是否有皇后。

相关问题

n皇后问题c++

n 皇后问题可以用回溯算法来解决，以下是 C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

void solveNQueens(int n, vector<vector<string>>& res, vector<string>& board, vector<int>& cols, vector<int>& diag1, vector<int>& diag2, int row) {
    if (row == n) {
        res.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {
            continue;
        }
        board[row][col] = 'Q';
        cols[col] = 1;
        diag1[row + col] = 1;
        diag2[row - col + n - 1] = 1;
        solveNQueens(n, res, board, cols, diag1, diag2, row + 1);
        board[row][col] = '.';
        cols[col] = 0;
        diag1[row + col] = 0;
        diag2[row - col + n - 1] = 0;
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    vector<int> cols(n, 0);
    vector<int> diag1(2 * n - 1, 0);
    vector<int> diag2(2 * n - 1, 0);
    solveNQueens(n, res, board, cols, diag1, diag2, 0);
    return res;
}

int main() {
    int n = 4;
    vector<vector<string>> res = solveNQueens(n);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << endl;
        }
        cout << endl;
    }
    return 0;
}

其中，solveNQueens 函数是主要的递归函数，cols 数组表示列是否被占用，diag1 和 diag2 数组则表示两个对角线是否被占用。一旦找到一个可行解，就将其保存在 res 中。最后输出所有的可行解即可。

n皇后问题c++变形

以下是一个C++实现的n皇后问题的变形，使用深度优先搜索（DFS）算法：

#include <iostream>
#include <vector>

using namespace std;

// 判断当前位置是否可以放置皇后
bool isValid(vector<int>& queens, int row, int col) {
    for (int i = 0; i < row; i++) {
        // 判断是否在同一列或同一斜线上
        if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
            return false;
        }
    }
    return true;
}

// 深度优先搜索
void dfs(vector<vector<string>>& res, vector<int>& queens, int row, int n) {
    if (row == n) {
        // 生成棋盘
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; i++) {
            board[i][queens[i]] = 'Q';
        }
        res.push_back(board);
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (isValid(queens, row, col)) {
            queens[row] = col;
            dfs(res, queens, row + 1, n);
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> queens(n, -1);
    dfs(res, queens, 0, n);
    return res;
}

int main() {
    int n = 4;
    vector<vector<string>> res = solveNQueens(n);
    
    // 输出结果
    for (int i = 0; i < res.size(); i++) {
        cout << "Solution " << i + 1 << ":" << endl;
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << endl;
        }
        cout << endl;
    }
    
    return 0;
}