python解决回溯法求n皇后问题

回溯法是一种递归的搜索算法，它不断地尝试各种可能的解决方案，直到找到一个可行的解决方案。在求解 n 皇后问题时，回溯法可以非常有效地搜索所有可能的放置方式，并找到符合要求的解决方案。

以下是 Python 代码实现：

def is_valid(board, row, col, n):
    # 判断皇后是否能放在该位置
    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, n, res):
    # 如果当前行已经放置了 n 个皇后，则将当前解加入到结果集中
    if row == n:
        res.append(board[:])
        return
    # 尝试在当前行的每一列放置皇后
    for col in range(n):
        if is_valid(board, row, col, n):
            board[row] = col
            backtrack(board, row + 1, n, res)
            board[row] = -1

def solve_n_queens(n):
    board = [-1] * n
    res = []
    backtrack(board, 0, n, res)
    return res

在上述代码中，`is_valid` 函数用来判断当前位置是否能够放置皇后；`backtrack` 函数则是回溯搜索的核心部分，通过递归调用自身来尝试各种可能的放置方式；`solve_n_queens` 函数则是对外暴露的接口，用来求解 n 皇后问题。

求解过程中，我们先初始化一个长度为 `n` 的列表 `board`，用来记录每一行放置的皇后所在的列数。初始时所有的元素都被初始化为 `-1`。接下来我们调用 `backtrack` 函数进行搜索，将当前行的皇后放在每一列上，并递归调用自身，直到找到符合要求的解决方案或者搜索完所有的可能性。在每一次递归调用结束后，我们需要将当前行的皇后从 `board` 列表中移除，以便进行下一次搜索。

最后，我们返回所有符合要求的解决方案即可。