N-Queens II
皇后会攻击所在行、所在列以及两条对角线上的所有格子，无论距离多远。给定一个整数 n，返回在 n × n 棋盘上放置 n 个皇后的方法数，使得任意两个皇后都不会互相攻击。
只要有任意一个格子不同，棋盘就分别计数，包括互为镜像的棋盘。
函数
- ninteger
- 棋盘的大小和皇后的数量
- 返回值integer
- 摆放皇后的方法数，使得没有皇后能互相攻击
约束条件
1 ≤ n ≤ 12- 对于
n = 12，答案是 14,200，因此它可以存储在 32 位整数中。
示例
- 输入
- n = 4
- 输出
- 2
- 解释
- 从上到下写出每一行中皇后所在的列，棋盘分别是
1, 3, 0, 2和2, 0, 3, 1：它们互为镜像，计作两种。其他所有摆法都会让两个皇后位于同一列或同一条对角线上。
- 输入
- n = 3
- 输出
- 0
- 解释
- 顶角的皇后会在中间一行留下一格安全的位置，而底下一行则没有安全位置。顶行中间的皇后会攻击整行中间位置。
进阶
你能只统计旋转或镜像棋盘后仍然不同的棋盘吗？当 n = 8 时，92 个棋盘可分为 12 组。
提示
逐个打开提示，每个都会多透露一点。
同一行中的两个皇后会互相攻击，所以每一行都恰好放置一个皇后。知道这一点后，还需要选择什么？
从顶部开始，一行一行地填满棋盘。一旦新放置的皇后受到攻击，就放弃当前未完成的棋盘，因为你在下面添加的内容都无法修复它。要在不查看整个棋盘的情况下测试一个格子，请记住哪些列和对角线上已经有皇后。沿着一个方向的对角线，所有格子的
row + col都相同；沿着另一个方向的对角线，row - col都相同。编写
place(row)，它返回从当前位置出发可以完成的完整棋盘数量。当row == n时，返回 1。否则，尝试每个满足列、row + c对角线和row - c对角线都空闲的列c：标记这三条线，将place(row + 1)加到累计总数中，然后取消标记。答案是place(0)。
题解
同一行中的两个皇后总会互相攻击，因此棋盘每行放一个皇后：共有 n^n 个列表，n = 12 时约为 8.9 × 10^12。改为逐行构建棋盘，一旦皇后受到攻击，就立即丢弃不完整的棋盘，并标记已占用的列和对角线，这样检查一个格子只需查询三次。
尝试每种摆放方式，确保每行放一个皇后
结果正确，但无法在最大的测试中运行完毕
思路
把一种摆放方式写成列表 cols，其中每一行的皇后所在列对应列表中的一个元素，然后像里程表一样遍历所有 n^n 个列表。对于行 i < j，如果 cols[i] == cols[j] 或 |cols[i] - cols[j]| == j - i，这些皇后就会互相攻击，因为对角线每向下一行就移动一列。每个列表都只检查一次，因此不会漏掉或重复计算任何棋盘。
没有任何机制会提前停止：即使前两行的皇后冲突，仍然要检查 n^(n-2) 个列表。对于 n = 8，92 个棋盘对应 16,777,216 个列表；对于 n = 12，则有 8.9 × 10^12 个列表，如果每个列表用 1 纳秒检查，大约需要 2.5 小时。
算法
- 先将
cols全部设为 0。 - 如果不存在一对行
i < j，满足cols[i] == cols[j]或|cols[i] - cols[j]| == j - i，就将计数加 1。 - 像里程表一样递增：从最后一行开始向上，将每个值为
n-1的项重置为 0，然后将第一个小于n-1的项加 1。 - 当每一项都曾为
n-1时，停止并返回计数。
def totalNQueens(n):
def is_valid(cols):
# cols[r] is the column of the queen in row r, so rows never clash.
for i in range(n):
for j in range(i + 1, n):
if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
return False
return True
cols = [0] * n
count = 0
while True:
if is_valid(cols):
count += 1
# Move to the next placement, like an odometer with n digits in base n.
row = n - 1
while row >= 0 and cols[row] == n - 1:
cols[row] = 0
row -= 1
if row < 0:
return count
cols[row] += 1使用列集合和对角线集合进行回溯
思路
按行放置皇后，每放置一个就检查它。下面几行的填法无法挽救受到攻击的皇后，所以跳过那个格子。安全的皇后会递归进入下一行，并在调用返回时移除；到达第 n 行时，计为一个棋盘。
只有三条线可以攻击格子 (row, c)：它所在的列、/ 对角线（row + c 为常数），以及 \ 对角线（row - c 为常数，将 n-1 加到索引上，使索引从 0 开始）。标记数组 cols、diag 和 anti 将安全性检查变成三次查找。每条线上最多有一个皇后，因此返回时清除标记，就能准确恢复数组。
第 k 行最多有 n - k 列可选，因此搜索的复杂度上限为 O(n!)，空间复杂度为 O(n)。
算法
- 创建大小为
n的标记数组cols，以及大小为2n-1的diag和anti，并将它们全部设为关。 place(row)：如果row == n，返回 1。- 对于每一列
c，如果cols[c]、diag[row + c]或anti[row - c + n - 1]为开，则跳过该列。 - 否则，将这三个标记设为开，把
place(row + 1)加到总数中，然后将它们设为关。 - 返回总数。答案是
place(0)。
def totalNQueens(n):
cols = [False] * n # cols[c]: column c holds a queen
diag = [False] * (2 * n - 1) # diag[r + c]: that / diagonal holds a queen
anti = [False] * (2 * n - 1) # anti[r - c + n - 1]: that \ diagonal holds a queen
def place(row):
if row == n:
return 1 # a queen in every row: one complete board
count = 0
for c in range(n):
if cols[c] or diag[row + c] or anti[row - c + n - 1]:
continue # attacked: three lookups, no scan of the board
cols[c] = diag[row + c] = anti[row - c + n - 1] = True
count += place(row + 1)
cols[c] = diag[row + c] = anti[row - c + n - 1] = False # take it back
return count
return place(0)使用位掩码进行回溯
思路
标志搜索仍会测试每行的全部 n 列；位掩码可以直接跳到空闲列。位 c 表示当前正在填充的行中的第 c 列：cols 保存已占用的列，left 和 right 保存两条对角线上被攻击的位置。然后，free = ~(cols | left | right) & full，其中 full 是低位的 n 个比特，而 free & -free 是最低的空闲位置。向下一行移动时，列仍保持占用状态，每条对角线上的攻击位置都会移动一列。
当 n = 4，且第一位皇后位于 bit = 0010 时，第 1 行得到 free = 1000：第 3 列，无需测试其他列即可找到。对于 n = 12，856,188 次循环步骤取代了 10,103,868 次方格测试。R 代码一次性扩展出一整行部分棋盘，而不是使用递归。
算法
- 设置
full = (1 << n) - 1。 count(cols, left, right)：如果cols == full，返回 1。- 计算
free = ~(cols | left | right) & full。 - 当
free不为 0 时，取bit = free & -free，将它从free中移除，并将count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)加到总数中。 - 返回总数。答案是
count(0, 0, 0)。
def totalNQueens(n):
full = (1 << n) - 1 # bit c stands for column c of the current row
def count(cols, left, right):
# cols: columns taken. left, right: squares of this row hit along a diagonal.
if cols == full:
return 1 # every column used: n queens placed
total = 0
free = full & ~(cols | left | right)
while free:
bit = free & -free # the lowest free square
free -= bit
# Moving down a row shifts each diagonal attack one column over.
total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
return total
return count(0, 0, 0)
易错点和边界情况
- 使用
row - c对anti进行索引时，没有加上n-1。Java 会抛出异常，C 会读取数组外的数据，而 Python 的anti[-2]会悄悄读取另一条对角线的标记。 - 对角线数组的大小设为
n，而不是2n-1。row + c的最大值会达到2n-2。 - 递归调用后没有清除标记。后续分支会看到已经移走的皇后，计数也会减少。
- 在
free中漏掉了& full。~x会设置列n-1之上的位，所以循环会选中棋盘外的格子；在 Python 或 Ruby 中，free会变成负数，循环永远不会结束。
常见问题3
N-Queens II 的时间复杂度是多少？
回溯的复杂度上界为 O(n!)：第一行有 n 种选择，下一行最多有 n-1 种，以此类推。剪枝能大幅减少实际工作量，将 n = 12 时的部分棋盘数量降至 856,189 个。空间复杂度为 O(n)。
N 皇后和 N 皇后 II 有什么区别？
N 皇后会返回每个棋盘，并将其绘制为文本行；N 皇后 II 只返回棋盘数量。搜索过程相同，但计数时不会存储棋盘，这很适合位掩码版本。
你能利用对称性加快求解 N-Queens II 的速度吗？
将棋盘左右镜像后仍是有效棋盘，因此统计第一位皇后位于第 0 到 n/2 - 1 列的棋盘数量，再乘以 2。如果 n 是奇数，再把第一位皇后位于中间列的棋盘数量加一次。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def totalNQueens(n):
# 在这里编写代码测试 #1
测试 #2
参数
n = 4
预期输出
2