递归算法求解八皇后问题C++

八皇后问题是指在 8x8 的国际象棋棋盘上放置 8 个皇后，使得任意两个皇后都不能处于同一行、同一列或同一斜线上。解决八皇后问题可以使用递归算法。

具体实现如下：

1. 定义一个大小为 8 的一维数组 `result`，用于存放每一行放置皇后的列数。

2. 定义递归函数 `bool placeQueen(int row)`，表示在第 `row` 行放置皇后，并返回是否成功放置。

3. 在 `placeQueen(int row)` 函数中，遍历该行所有列，判断该列是否可以放置皇后。如果可以，将该列的列数存入 `result` 数组，并递归调用 `placeQueen(row + 1)`，继续放置下一行的皇后。

4. 如果 `placeQueen(row + 1)` 返回 false，说明无法在下一行放置皇后，则回溯到上一行，并尝试放置上一行的皇后的其他位置。

5. 当 `row` 等于 8 时，说明所有皇后都已经放置完毕，输出 `result` 数组即可。

下面是具体实现的代码示例：

#include<iostream>
using namespace std;

int result[8]; // 存放每一行放置皇后的列数

bool check(int row, int col) { // 判断该列是否可以放置皇后
    for (int i = 0; i < row; i++) {
        if (result[i] == col || abs(row - i) == abs(col - result[i])) {
            return false; // 在同一列或同一斜线上
        }
    }
    return true;
}

bool placeQueen(int row) { // 在第row行放置皇后
    if (row == 8) { // 所有皇后都已经放置完毕
        return true;
    }

    bool success = false;
    for (int i = 0; i < 8; i++) {
        if (check(row, i)) {
            result[row] = i; // 记录该列的列数
            success = placeQueen(row + 1); // 递归尝试放置下一行的皇后
            if (success) break; // 如果成功放置，则直接返回
        }
    }
    if (!success) result[row] = -1; // 如果无法放置，则回溯到上一行
    return success;
}

int main() {
    if (placeQueen(0)) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (result[i] == j) {
                    cout << "Q ";
                } else {
                    cout << "* ";
                }
            }
            cout << endl;
        }
    }
    return 0;
}

在 main 函数中调用 `placeQueen(0)` 即可求解八皇后问题。