n皇后python回溯法

下面是一个基于回溯法的 n 皇后 Python 实现：

def solveNQueens(n):
    def is_valid(board, row, col):
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == row - i:
                return False
        return True

    def backtrack(board, row):
        if row == n:
            res.append(list(board))
            return
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                backtrack(board, row + 1)
                board[row] = -1

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

这里采用一个一维数组 `board` 来表示棋盘，`board[i]` 表示第 i 行皇后所在的列数，初始值为 -1。在每一行中，我们枚举该行所有列，如果可以放置皇后，则将其放置在该位置，并递归处理下一行。如果发现该位置无法放置皇后，则回溯到上一行重新处理。

`is_valid()` 函数用于判断当前位置是否可以放置皇后。若在同一列或同一对角线上已经有皇后，则返回 False。如果没有冲突，则返回 True。

最终返回的是所有可行的皇后摆法，每一种摆法都表示为一个长度为 n 的列表，列表的第 i 个元素表示第 i 行皇后所在的列数。