八皇后问题python

八皇后问题是一个经典的回溯算法问题，它要求在一个8x8的棋盘上放置8个皇后，使得每个皇后都不会攻击到其他皇后。攻击的定义是：同一行、同一列、同一对角线上都不能有两个皇后。

以下是一个Python实现：

def is_valid(board, row, col):
    """
    判断在 board[row][col] 放置皇后是否合法
    """
    # 检查同一列上是否有皇后
    for i in range(row):
        if board[i][col] == 'Q':
            return False

    # 检查左上方是否有皇后
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q':
            return False
        i, j = i - 1, j - 1

    # 检查右上方是否有皇后
    i, j = row - 1, col + 1
    while i >= 0 and j < len(board):
        if board[i][j] == 'Q':
            return False
        i, j = i - 1, j + 1

    return True


def backtrack(board, row, res):
    """
    回溯算法
    """
    # 找到一个解
    if row == len(board):
        res.append([''.join(row) for row in board])
        return

    n = len(board[row])
    for col in range(n):
        # 判断在 board[row][col] 放置皇后是否合法
        if not is_valid(board, row, col):
            continue

        # 在 board[row][col] 放置皇后
        board[row][col] = 'Q'
        # 继续搜索下一行
        backtrack(board, row + 1, res)
        # 撤销放置皇后的操作
        board[row][col] = '.'

        
def solve_n_queens(n):
    """
    求解 n 皇后问题
    """
    board = [['.' for _ in range(n)] for _ in range(n)]
    res = []
    backtrack(board, 0, res)
    return res

可以通过调用 `solve_n_queens(8)` 来求解8皇后问题。该函数返回的是一个列表，其中每个元素表示一种合法的放置方案。每个元素是一个字符串列表，表示棋盘上每一行的放置情况。例如，`[["Q.......", "..Q.....", "....Q...", "......Q.", ".Q......", ".......Q", "...Q....", "....Q..."]]` 表示一种合法的放置方案。