c++递归实现n皇后问题代码(八皇后问题)

实现n皇后问题的代码可以用递归的方法来实现。这里提供一份c++递归实现n皇后问题代码以及完整攻略。

思路简述

n皇后问题指的是在一个nxn的棋盘上放置n个皇后，使得皇后之间互不攻击，即任意两个皇后都不能放置在同一行、同一列或同一对角线上。这里我们可以使用递归的方法来实现。

具体实现思路如下：

1. 首先定义一个长度为n的一维数组board，用来存放每一行中皇后所在的列号。比如board[2]表示第3行中皇后所在的列号。
2. 然后对于每一行，依次尝试将皇后放置在每一列中，然后判断当前格子是否安全。
3. 如果安全，就在该位置放置皇后，并递归处理下一行。
4. 如果下一行无法放置，就回溯到上一行，将皇后前一次放置的位置换成不同的列进行尝试。

代码示例

下面给出一份c++递归实现n皇后问题的代码。

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

bool is_valid(vector<int>& board, int row, int col)
{
    for (int i = 0; i < row; ++i) 
    {
        int val = board[i];
        if (val == col || val + row - i == col || val - row + i == col)
            return false;
    }
    return true;
}

void solve_n_queen(vector<vector<string>>& res, vector<int>& board, int row)
{
    int n = board.size();
    if (row == n) 
    {
        vector<string> solution(n, string(n, '.'));
        for (int i = 0; i < n; ++i) 
        {
            solution[i][board[i]] = 'Q';
        }
        res.push_back(solution);
        return;
    }

    for (int col = 0; col < n; ++col) 
    {
        if (is_valid(board, row, col)) 
        {
            board[row] = col;
            solve_n_queen(res, board, row + 1);
            board[row] = -1;
        }
    }
}

vector<vector<string>> solveNQueens(int n) 
{
    // 初始化一维数组board，并全部置为-1
    vector<int> board(n, -1);
    vector<vector<string>> res;
    solve_n_queen(res, board, 0);
    return res;
}

int main()
{
    vector<vector<string>> res = solveNQueens(8);
    for (int i = 0; i < res.size(); ++i) 
    {
        cout << "Solution " << i + 1 << ":" << endl;
        for (int j = 0; j < res[i].size(); ++j) 
        {
            cout << res[i][j] << endl;
        }
        cout << endl;
    }
    return 0;
}

这份代码可以输出8皇后问题的所有解，通过改变solveNQueens函数中的参数n，可以输出n皇后问题的所有解。

示例说明

下面给出两个代码示例来说明该代码的运行结果。

示例1： 输入参数为4，该代码将输出4皇后问题的所有解。

Solution 1:
.Q..
...Q
Q...
..Q.

Solution 2:
..Q.
Q...
...Q
.Q..

示例2： 输入参数为8，该代码将输出8皇后问题的所有解，由于这里的解非常多，我们只显示其中的3个。

Solution 1:
Q.......
....Q...
.......Q
..Q.....
......Q.
.Q......
.....Q..
...Q....

Solution 2:
Q.......
.....Q..
.......Q
..Q.....
......Q.
.Q......
...Q....
....Q...

Solution 3:
.Q......
...Q....
.....Q..
.......Q
Q.......
......Q.
..Q.....
....Q...

以上就是c++递归实现n皇后问题的完整攻略。