n 皇后问题【Python】

解题思路：

n皇后问题是一个比较经典的回溯算法问题，对于每一行，我们需要确定皇后应该放在哪一列上。但是，由于同一行和同一列以及对角线上不允许出现两个皇后，因此我们需要使用一个数组来记录哪些列已经被占用。

具体实现如下：

1. 定义 DFS 函数，每次递归时需要传入当前行数 row 和已经占用的列 nums。
2. 如果当前行数等于n，说明已经找到一种合法方案，令 count加一。
3. 遍历每一列，如果当前列已经被占用了，跳过继续遍历，否则将当前列标记为已占用，并进入下一行进行递归。
4. 递归后需要将当前行和列的占用状态恢复，以进行回溯。

Python 代码如下：

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1:
            return 0
        self.count = 0
        self.DFS(n, 0, set(), set(), set())
        return self.count
 
    def DFS(self, n, row, cols, xy_diff, xy_sum):
        if row == n:
            self.count += 1
            return
        for col in range(n):
            if col in cols or row - col in xy_diff or row + col in xy_sum:
                continue
            cols.add(col)
            xy_diff.add(row - col)
            xy_sum.add(row + col)
            self.DFS(n, row + 1, cols, xy_diff, xy_sum)
            cols.remove(col)
            xy_diff.remove(row - col)
            xy_sum.remove(row + col)