题目
N皇后问题II - 统计所有解的数量
信息
- 类型：问答
- 难度：⭐⭐⭐
考点
回溯算法设计,剪枝优化,递归实现
快速回答
N皇后问题II要求计算在N×N棋盘上放置N个皇后，使得它们互不攻击的所有方案数。
- 使用回溯算法逐行放置皇后，避免行冲突
- 用三个集合分别记录列、主对角线和副对角线的占用情况
- 主对角线用行号减列号标识，副对角线用行号加列号标识
- 当放置到第N行时，计数加一
- 通过剪枝避免无效搜索：放置前检查当前列和两个对角线是否已被占用
问题描述
给定整数N，返回在N×N棋盘上放置N个皇后，使得它们不能互相攻击（任意两个皇后不在同一行、列或对角线）的所有不同解决方案的数量。
原理说明
回溯算法的核心思想是：
- 逐行放置皇后，避免行冲突
- 使用三个集合记录状态：
cols：已被占用的列diag1：主对角线（行-列值相同）diag2：副对角线（行+列值相同）
- 递归尝试每行的所有列位置：
- 若当前位置安全（列和两个对角线均未被占用），放置皇后并更新状态
- 递归处理下一行
- 回溯：移除当前皇后并恢复状态
- 当成功放置第N个皇后时，计数器加一
代码示例（Python）
def totalNQueens(n: int) -> int:
def backtrack(row, cols, diag1, diag2):
nonlocal count
if row == n:
count += 1
return
for col in range(n):
d1 = row - col # 主对角线标识
d2 = row + col # 副对角线标识
# 剪枝：检查冲突
if col in cols or d1 in diag1 or d2 in diag2:
continue
# 放置皇后并更新状态
cols.add(col)
diag1.add(d1)
diag2.add(d2)
# 递归下一行
backtrack(row + 1, cols, diag1, diag2)
# 回溯：移除皇后
cols.remove(col)
diag1.remove(d1)
diag2.remove(d2)
count = 0
backtrack(0, set(), set(), set())
return count最佳实践
- 状态压缩：使用集合实现O(1)复杂度的冲突检查
- 对角线标识：主对角线用row-col，副对角线用row+col，确保唯一性
- 剪枝优化：在递归前进行冲突检测，避免无效递归
- 空间优化：使用单个整数位运算替代集合（进阶技巧）
常见错误
- 忘记回溯：递归返回后未恢复状态，导致状态污染
- 对角线计算错误：混淆主副对角线的计算公式
- 无效剪枝：使用二维数组遍历检查冲突，导致O(N)时间复杂度
- 终止条件错误：未正确处理row==n的终止情况
复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(N!)（最优剪枝情况下） |
| 空间复杂度 | O(N)（递归栈深度+集合存储） |
扩展知识
- 位运算优化：使用整数位掩码代替集合，将空间复杂度降至O(1)：
def totalNQueens(n): def dfs(row, cols, diag1, diag2): if row == n: return 1 count = 0 bits = (~(cols | diag1 | diag2)) & ((1 << n) - 1) while bits: p = bits & -bits # 获取最低位的1 bits &= bits - 1 # 清除最低位的1 count += dfs(row + 1, cols | p, (diag1 | p) << 1, (diag2 | p) >> 1) return count return dfs(0, 0, 0, 0) - 对称性优化：利用棋盘对称性减少50%计算量
- 迭代实现：使用栈替代递归避免栈溢出
- 并行计算：对第一行的不同列分配独立计算任务
