n皇后问题Python

n皇后问题是一个经典的回溯算法问题，其目标是在一个n×n的棋盘上放置n个皇后，使得每个皇后都不会互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。以下是一个Python实现的例子：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        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]

这个算法使用了DFS（深度优先搜索）来遍历所有可能的解决方案。在DFS的过程中，我们使用三个列表来记录已经放置的皇后的列、左上到右下的对角线和右上到左下的对角线。如果当前的皇后可以放置在当前位置，则递归地继续放置下一个皇后。如果所有的皇后都被放置，则将当前的解决方案添加到结果列表中。