回溯法求八皇后问题

八皇后问题是指在一个 8x8 的棋盘上放置 8 个皇后，使得任意两个皇后都不能在同一行、同一列或同一斜线上。这个问题可以通过回溯法求解。

回溯法是一种通过探索所有可能的解来找到所有解的算法。如果在探索过程中发现了不符合条件的解，就回溯到上一步继续探索其他可能的解。在八皇后问题中，我们可以通过递归实现回溯。

具体实现过程如下：

1. 定义一个数组 chessboard，用于存储皇后的位置，初始值为 0。

2. 定义一个递归函数 solve，用于放置皇后。

3. 在 solve 函数中，首先遍历棋盘的每一列，判断当前列是否可以放置皇后。如果可以，就遍历当前列的每一行，判断当前行是否可以放置皇后。如果可以，就将当前位置设为 1，表示放置了皇后，并将皇后的位置存入 chessboard 数组中。然后递归调用 solve 函数，继续放置下一列的皇后。如果最后一列的皇后也成功放置，则说明找到了一组解，输出 chessboard 数组即可。

4. 如果发现当前位置不能放置皇后，则回溯到上一步，将当前位置设为 0，继续遍历当前列的下一个位置。

下面是具体的代码实现：

def solve(chessboard, row):
    # 所有皇后都已经成功放置，输出结果
    if row == len(chessboard):
        print(chessboard)
        return
    
    # 遍历每一列，尝试放置皇后
    for col in range(len(chessboard)):
        # 判断当前列是否可以放置皇后
        if check(chessboard, row, col):
            # 放置皇后并递归调用 solve 函数
            chessboard[row][col] = 1
            solve(chessboard, row + 1)
            # 回溯到上一步
            chessboard[row][col] = 0

def check(chessboard, row, col):
    # 检查当前列是否已经有皇后
    for i in range(row):
        if chessboard[i][col] == 1:
            return False
    
    # 检查左上方是否有皇后
    i = row - 1
    j = col - 1
    while i >= 0 and j >= 0:
        if chessboard[i][j] == 1:
            return False
        i -= 1
        j -= 1
    
    # 检查右上方是否有皇后
    i = row - 1
    j = col + 1
    while i >= 0 and j < len(chessboard):
        if chessboard[i][j] == 1:
            return False
        i -= 1
        j += 1
    
    return True

# 初始化棋盘
chessboard = [[0 for j in range(8)] for i in range(8)]
# 从第一行开始放置皇后
solve(chessboard, 0)

输出结果为：

[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 0]

每一行表示一个解，其中 1 表示皇后的位置。