n皇后问题python代码实现及解释

以下是n皇后问题的Python代码实现及解释：

def is_valid(board, row, col):
    """
    判断当前位置是否合法
    """
    n = len(board)
    for i in range(row):
        if board[i] == col or abs(row - i) == abs(col - board[i]):
            return False
    return True


def backtrack(board, row, res):
    """
    回溯函数
    """
    n = len(board)
    if row == n:
        res.append(board[:])
        return

    for i in range(n):
        if is_valid(board, row, i):
            board[row] = i
            backtrack(board, row + 1, res)
            board[row] = -1


def solve_n_queens(n):
    """
    解决n皇后问题
    """
    board = [-1] * n  # 构造空棋盘
    res = []
    backtrack(board, 0, res)
    return res

该代码实现了n皇后问题的求解。在解释代码之前，让我们先了解一下n皇后问题的背景和规则。

n皇后问题是一种经典的回溯算法问题，其规则如下：

在一个$n \times n$的棋盘上放置n个皇后，使得每个皇后所在的行、列和对角线上都不存在其他皇后。其中，对角线包括正方向（左上到右下）和反方向（左下到右上）。

现在，让我们回到我们的代码。代码主要分为三个函数：`is_valid`、`backtrack`和`solve_n_queens`。

`is_valid`函数用于判断当前位置是否合法。对于当前位置$(row, col)$来说，其是否合法由以下条件决定：

1. 当前列上没有其他皇后；
2. 在之前的行里，不存在皇后和当前位置在同一对角线上。

满足上述两个条件则说明当前位置合法。

`backtrack`函数是回溯函数。其首先判断当前行是否为最后一行，如果是，则说明找到了一组解，并将其添加到结果列表里。否则，它会尝试将皇后逐个放在当前行的每一个位置上，并进入下一行继续放置。如果在某个位置上放置后发现无法继续前进，则回溯到上一行重新选择其他位置放置皇后。

`solve_n_queens`函数是解决n皇后问题的入口函数。它首先构造一个长度为n的空棋盘，并调用backtrack函数求解问题。最终，它会返回所有可能的解。