N 皇后问题(queen)

N 皇后问题是一个经典的回溯算法问题，其目标是在 N x 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 函数用于递归求解，queens 数组记录每行皇后所在的列数，xy_dif 数组记录每个位置的 x-y 值之差，xy_sum 数组记录每个位置的 x+y 值之和。在递归过程中，如果已经放置了 N 个皇后，则将当前解加入结果数组中。否则，对于每一列，判断该列是否可以放置皇后，如果可以，则继续递归放置下一行皇后。

以下是一个 N=4 的例子的输出结果：

[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]