回溯策略实现八皇后问题python

八皇后问题是指在8x8的棋盘上放置8个皇后，使得每个皇后都不能相互攻击，即每个皇后所在的行、列、对角线上都不能有另一个皇后。

回溯算法是解决八皇后问题的一种常用算法，其基本思想是：从第一行开始，依次尝试在每一列上放置皇后，如果当前位置不合法，则回溯到上一行，并在上一行的下一列继续尝试放置皇后，直到找到一组合法的解或者所有可能的情况都尝试完毕。

下面是使用回溯算法实现八皇后问题的Python代码：

def is_valid(board, row, col):
    """
    判断在(row, col)位置放置皇后是否合法
    """
    n = len(board)
    # 检查列
    for i in range(n):
        if board[i][col] == 1:
            return False
    # 检查左上方斜线
    i, j = row-1, col-1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i, j = i-1, j-1
    # 检查右上方斜线
    i, j = row-1, col+1
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i, j = i-1, j+1
    return True

def solve(board, row):
    """
    递归求解八皇后问题
    """
    n = len(board)
    if row == n:
        # 找到一组解
        for i in range(n):
            for j in range(n):
                print(board[i][j], end=' ')
            print()
        print()
        return
    # 在当前行依次尝试放置皇后
    for col in range(n):
        if is_valid(board, row, col):
            board[row][col] = 1
            solve(board, row+1)
            board[row][col] = 0

# 初始化棋盘
n = 8
board = [[0]*n for _ in range(n)]
# 从第0行开始求解
solve(board, 0)

在上面的代码中，`is_valid()`函数用于判断在(row, col)位置放置皇后是否合法，`solve()`函数用于递归求解八皇后问题。在`solve()`函数中，先判断是否已经找到一组解（即当前行已经超出棋盘范围），如果找到一组解，则输出并返回；否则，在当前行依次尝试放置皇后，如果当前位置合法，则递归搜索下一行；如果当前位置不合法，则回溯到上一行，并在上一行的下一列继续尝试放置皇后。