n 皇后问题【Python】

皇后问题【Python】"/>

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 0self.count = 0self.DFS(n, 0, set(), set(), set())return self.countdef DFS(self, n, row, cols, xy_diff, xy_sum):if row == n:self.count += 1returnfor col in range(n):if col in cols or row - col in xy_diff or row + col in xy_sum:continuecols.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)