Leetcode51：N 皇后

题目描述：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

代码思路：

这段代码是用来解决N皇后问题的，通过递归和回溯的方式，它的核心思路是使用深度优先搜索（DFS）来尝试每一种可能的放置方法，并验证是否满足N皇后问题的条件。

下面是详细的代码思路解析：

代码实现：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        m = n * 2 -1
        ans = []
        col = [0] * n
        on_path, diag1, diag2 = [False] * n, [False] * m,  [False] * m
        def dfs(r):
            if r==n:
                ans.append(['.'*c+'Q'+'.'*(n-1-c) for c in col])
                return
            
            for c, on in enumerate(on_path):
                if not on and not diag1[r+c] and not diag2[r-c]:
                    col[r] = c
                    on_path[c] = diag1[r+c] = diag2[r-c] = True
                    dfs(r+1)
                    on_path[c] = diag1[r + c] = diag2[r - c] = False
            
        dfs(0)
        return ans