从毫秒级回溯看 N 皇后位运算剪枝

问题背景：8 皇后为什么容易写成“能跑但慢”

N 皇后问题要求在 N×N 棋盘上放置 N 个皇后，使任意两个皇后不在同一列、同一行或同一条斜线上。因为每行恰好放一个皇后，搜索的核心就变成：逐行选择一个与历史放置不冲突的列。

最直观的回溯写法通常会维护三个集合：已占用列、主对角线、副对角线。它容易理解，但每进入一个候选列，都要做多次集合查询、插入和回滚；候选列也要从 0 到 N-1 全部扫描。对于 8 皇后，现代计算机仍然能很快跑完，但随着 N 增大，大量时间会消耗在“生成一个注定非法的位置，再判断它非法”上。

位运算剪枝的价值在于：把冲突信息压缩成整数位掩码，在一次位运算中求出当前行所有还能放皇后的列；随后只枚举合法候选，不再碰非法列。本文完整推导这套写法。

方案对比：集合判重与位掩码剪枝

普通集合回溯

普通方案用以下三个条件判重：

• 列冲突：col 已出现；
• 主对角线冲突：row - col 已出现；
• 副对角线冲突：row + col 已出现。

每放一个皇后，就向集合加入三个标记；递归返回后再删除。它的时间复杂度上界仍是阶乘级搜索，空间复杂度为 O(N)。

位运算剪枝回溯

位运算方案同样维护三类冲突，但不再使用集合，而是使用三个整数：

• cols：哪些列已经被占用；
• pie：哪些位置会被“左上到右下”的斜线攻击；
• na：哪些位置会被“右上到左下”的斜线攻击。

进入下一行时，斜线攻击范围整体平移一位：

• (pie | bit) << 1：攻击列向左扩散；
• (na | bit) >> 1：攻击列向右扩散。

再用 full = (1 << n) - 1 限制有效位，避免左移产生棋盘外的新位。

推导关键：三个掩码如何表示斜线约束

假设当前在某一行放置了皇后，对应位是 bit。

列约束最直接：下一行中，bit 对应列不能再使用，因此新列掩码为 cols | bit。

斜线约束需要结合“行每增加 1，斜线影响的列偏移 1”理解：

• 对主斜线来说，当前皇后在下一行攻击的位置相对当前列左移一列，所以使用 (pie | bit) << 1；
• 对副斜线来说，当前皇后在下一行攻击的位置相对当前列右移一列，所以使用 (na | bit) >> 1。

注意，这里的 pie、na 不是某一条斜线的编号，而是“传递到下一行后，所有会造成斜线冲突的列”。递归参数每次都根据当前行重新计算，因此不需要手动撤销位操作。

合法位置计算公式为：

available = full & ~(cols | pie | na)

其中取反可能产生大量高位 1，必须再与 full 做按位与，只保留棋盘范围内的 N 个低位。

Python 可运行代码：统计解数并输出棋盘

下面代码同时提供“统计解数”和“生成具体棋盘”。默认计算 8 皇后，可直接运行。

from time import perf_counter


def solve_n_queens(n):
    """返回 N 皇后的所有具体摆法，每个摆法由一组字符串表示。"""
    if n <= 0:
        return []

    full = (1 << n) - 1
    solutions = []
    board = []

    def build_row(bit):
        # bit 中只有一个 1，将其转换成 Q，其余位置为 .
        column = bit.bit_length() - 1
        chars = ["."] * n
        chars[column] = "Q"
        return "".join(chars)

    def backtrack(cols, pie, na):
        # 所有列都已经合法放置，说明找到一个完整方案
        if cols == full:
            solutions.append(board.copy())
            return

        # 一次求出当前行所有可放皇后的列
        available = full & ~(cols | pie | na)

        while available:
            # 取最低位的 1 作为当前候选位置
            bit = available & -available
            # 清除已尝试的候选位
            available ^= bit

            board.append(build_row(bit))

            backtrack(
                cols | bit,
                (pie | bit) << 1,
                (na | bit) >> 1,
            )

            board.pop()

    backtrack(0, 0, 0)
    return solutions


def count_n_queens(n):
    """只统计解数，不保存棋盘，额外空间更稳定。"""
    full = (1 << n) - 1
    count = 0

    def backtrack(cols, pie, na):
        nonlocal count

        if cols == full:
            count += 1
            return

        available = full & ~(cols | pie | na)

        while available:
            bit = available & -available
            available ^= bit

            backtrack(
                cols | bit,
                (pie | bit) << 1,
                (na | bit) >> 1,
            )

    backtrack(0, 0, 0)
    return count


if __name__ == "__main__":
    n = 8

    start = perf_counter()
    answer_count = count_n_queens(n)
    elapsed_ms = (perf_counter() - start) * 1000

    print(f"{n} 皇后解数：{answer_count}")
    print(f"仅统计耗时：{elapsed_ms:.3f} ms")

    boards = solve_n_queens(n)
    print("第一个方案：")
    print("\n".join(boards[0]))

8 皇后共有 92 个解。位运算版本只遍历 available 中的合法候选位，避免了对每一列进行重复试错。

候选位枚举：为什么是 bit = available & -available

Python 整数使用补码风格的位运算语义，-available 等于 ~available + 1。因此：

available & -available

可以取出最低位的 1。例如：

available = 101100
-available 与 available 按位与 = 000100

取出候选位后，使用异或清除它：

available ^= bit

因为 bit 一定是 available 中已有的一个一位数字，所以异或会把该位从 1 改成 0，而不会影响其他位。循环结束时，所有合法列都被尝试过。

复杂度分析：剪枝减少分支，不改变最坏阶乘量级

N 皇后没有多项式解法。若粗略按排列理解，第一行最多 N 个选择，第二行最多 N-1 个选择，因此搜索上界可写为 O(N!)。位运算剪枝不会把最坏复杂度变成多项式，但会显著减少实际进入递归的非法分支。

空间复杂度分为两部分：

• 递归深度与当前棋盘为 O(N)；
• 若保存所有完整棋盘，输出本身需要 O(S×N²)，其中 S 是解的数量。

因此，只统计解数时辅助空间为 O(N)；生成并保存所有方案时，空间复杂度由输出规模决定。

单次掩码计算、候选位提取和位清除都是整数位运算。Python 整数位数随 N 增长，但在常见面试与竞赛范围内，这种额外位长成本远小于集合维护和无效递归的成本。

避坑总结：位运算回溯的高频错误

1. 忘记 full 截断，导致棋盘外多出候选位

常见错误是直接写：

available = ~(cols | pie | na)  # 错误

现象是递归中出现棋盘外的高位，bit.bit_length() - 1 得到大于等于 N 的列号，生成棋盘时报索引错误或产生异常结果。修正方式是固定加上：

available = full & ~(cols | pie | na)

左移后的 pie 即使出现高位也不必单独清理，因为下一次求 available 时会被 full 截掉。

2. 斜线左右移方向写反

有些资料中变量名 pie、na 的定义相反，这本身没有问题，但两个递归更新方向必须与定义一致。若把 << 1 和 >> 1 对调，单个小 N 可能碰巧通过部分测试，但在 N=8 时解数会明显不等于 92。

修正时不要只靠背代码，可以在纸上验证：进入下一行后，当前皇后影响的列到底是左移一列还是右移一列，再确定移位方向。

3. 用减法或取反清除候选位，破坏其他状态

看到 bit = available & -available 后，容易误写：

available -= bit          # 多数情况下可行，但语义不如异或清晰
available &= available - 1 # 也可清除最低位，但容易和 bit 脱节

更稳妥的写法是：

bit = available & -available
available ^= bit

这样明确表达“枚举并移除当前候选位”。另外，不要对 cols、pie、na 执行异或回滚，因为它们是作为不可变递归参数传入的；每次递归都会生成新掩码，当前层的变量并未被修改。

4. 终止条件误写成候选位为 0

available == 0 只能说明当前行没有合法位置，应该让失败分支自然返回；它不能表示已经找到完整方案。正确终止条件是：

if cols == full:
    count += 1

因为每行放一个皇后，当 N 个列位都被占用时，恰好已经放满 N 行。若用 available == 0 计数，会把“下一行无路可走”和“最后一行放置成功”混在一起。

5. 保存棋盘时直接追加同一个列表对象

生成具体方案时，下面写法可能导致最终结果中的棋盘全部变成最后一次回溯状态：

solutions.append(board)  # 错误：保存的是同一个引用

应在找到完整解时复制快照：

solutions.append(board.copy())

递归返回后的 board.pop() 只会撤销当前路径，不会影响已经复制保存的方案。

结语

N 皇后是理解回溯剪枝的经典题目。集合写法重在表达约束，位运算写法重在压缩状态和批量求合法候选。掌握 cols | pie | na、full & ~conflict、available & -available 这三个关键表达式后，不仅能写出毫秒级完成 8 皇后统计的代码，也能把“状态压缩 + 只枚举有效分支”的思路迁移到数独、棋盘覆盖和其他约束搜索问题中。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。