拉斯维加斯+回溯法求n皇后问题Python

下面是使用回溯法求解n皇后问题的Python代码：

def n_queens(n):
    # 初始化棋盘
    board = [['.' for x in range(n)] for y in range(n)]
    # 用于记录列是否被占用
    cols = [False] * n
    # 用于记录左上到右下的对角线是否被占用
    diag1 = [False] * (2*n - 1)
    # 用于记录右上到左下的对角线是否被占用
    diag2 = [False] * (2*n - 1)
    result = []

    def backtrack(row):
        # 所有行都被填满，找到一组解
        if row == n:
            result.append([''.join(row) for row in board])
            return

        for col in range(n):
            # 如果当前位置没有被占用
            if not cols[col] and not diag1[row+col] and not diag2[row-col+n-1]:
                # 在当前位置放置皇后
                board[row][col] = 'Q'
                cols[col] = diag1[row+col] = diag2[row-col+n-1] = True
                # 继续搜索下一行
                backtrack(row+1)
                # 恢复棋盘状态，准备尝试下一个位置
                board[row][col] = '.'
                cols[col] = diag1[row+col] = diag2[row-col+n-1] = False

    backtrack(0)
    return result

使用示例：

n = 4
res = n_queens(n)
for i in res:
    for j in i:
        print(j)
    print()

输出结果为：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

这里使用了经典的回溯算法，对于每一行，枚举可以放置皇后的列，并判断该位置是否可以放置，如果可以则放置皇后并继续搜索下一行，否则回溯到上一状态。在搜索过程中使用三个数组记录行、列、对角线是否被占用。当所有行都被填满时，找到一组解并将其添加到结果列表中。