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

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

def solveNQueens(n):
    def DFS(queens, xy_dif, xy_sum):
        p = len(queens)
        if p == n:
            result.append(queens)
            return None
        for q in range(n):
            if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
    result = []
    DFS([],[],[])
    return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

# 示例：
print(solveNQueens(4))

输出：

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

其中，solveNQueens(n) 函数返回一个包含所有满足条件的n皇后问题解的列表。在DFS函数中，queens列表存储每行皇后所在的列数，xy_dif列表存储所有斜率为-1的位置（如(0,0)和(1,1)），xy_sum列表存储所有斜率为1的位置（如(0,1)和(1,0)）。在每次递归调用时，将当前行可以放置皇后的所有列数作为候选，然后判断是否满足条件，如果满足，则将该列加入queens，将其对应的斜率-1和斜率1的位置加入xy_dif和xy_sum，然后递归处理下一行。当queens长度为n时，表示已找到一组解，将其保存在结果列表result中。最后，将每个解转换为符合要求的格式，即一个字符串列表，表示每个棋盘行。