递归算法求解八皇后问题

八皇后问题是指在一个 8x8 的棋盘上放置八个皇后，使得任意两个皇后都不能在同一行、同一列或者同一对角线上。以下是递归算法求解八皇后问题的步骤：

1.定义一个数组 chessBoard，用于表示棋盘上每个位置是否有皇后，初始值为 0。

2.定义递归函数 solveQueen(int row)，表示在棋盘的第 row 行放置皇后。具体实现如下：

- 如果 row > 8，则表示已经成功放置了 8 个皇后，输出结果并返回true。
- 对于第 row 行的每个位置，判断是否可以放置皇后。如果可以，则将 chessBoard[row][i] 设为 1，然后递归调用 solveQueen(row+1)。
- 如果递归调用 solveQueen(row+1) 返回 true，则表示已经找到了一组解，直接返回 true。
- 否则，将 chessBoard[row][i] 设为 0，继续枚举第 row 行的下一个位置。

3.在主函数中调用 solveQueen(1) 开始递归搜索。

以下是具体的代码实现：

#include <iostream>
using namespace std;

const int N = 8;
int chessBoard[N+1][N+1] = {0};  // 棋盘，0 表示无皇后，1 表示有皇后

// 判断在第 row 行，第 col 列是否可以放置皇后
bool check(int row, int col)
{
    for (int i = 1; i < row; i++) {
        if (chessBoard[i][col]) return false;  // 同列有皇后
        if (col-i > 0 && chessBoard[row-i][col-i]) return false;  // 左上方有皇后
        if (col+i <= N && chessBoard[row-i][col+i]) return false;  // 右上方有皇后
    }
    return true;
}

// 在第 row 行放置皇后
bool solveQueen(int row)
{
    if (row > N) {
        // 输出结果
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (chessBoard[i][j]) cout << "Q ";
                else cout << ". ";
            }
            cout << endl;
        }
        return true;
    }

    for (int i = 1; i <= N; i++) {
        if (check(row, i)) {
            chessBoard[row][i] = 1;  // 放置皇后
            if (solveQueen(row+1)) return true;  // 递归搜索下一行
            chessBoard[row][i] = 0;  // 回溯，撤销皇后
        }
    }
    return false;
}

int main()
{
    solveQueen(1);
    return 0;
}

这里的 check 函数用于判断在第 row 行，第 col 列是否可以放置皇后，它会检查同列、左上方和右上方是否有皇后。solveQueen 函数用于在第 row 行放置皇后，并递归搜索下一行。如果已经成功放置了 8 个皇后，则输出结果并返回 true，否则回溯，撤销皇后，重新枚举下一个位置。主函数中调用 solveQueen(1) 开始递归搜索。