python 回溯法 n皇后

回溯法是一种常用的解决问题的算法，它通常用于在搜索问题的所有解时使用。而 N 皇后问题是回溯算法中比较经典的问题之一，是指在一个 N × N 的棋盘上要摆 N 个皇后，使得任意两个皇后都不能处于同一行、同一列或同一斜线上。下面是 Python 中实现 N 皇后问题的回溯算法：

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]