回溯算法进阶：用位运算优化 8 皇后（C / Python）

在上一篇 8 皇后入门文章里，我们使用了最经典的回溯写法：按行递归，用数组记录列、主对角线和副对角线是否被占用。那一版代码很好理解，也非常适合第一次接触回溯算法。

但如果你继续深入，就会很自然地问一个问题：既然每一层都要频繁判断“哪些位置还能放”，有没有更快的写法？

这篇文章就继续讨论 8 皇后问题的优化版实现：用位运算压缩状态，用同样的回溯思路，把搜索过程写得更快。

我们仍然使用回溯，不改问题本质；改变的是“状态表示方式”。文章最后会分别给出 Python 和 C 的完整实现。

如果你还没看过标准写法，建议先阅读这篇基础文章：回溯算法入门：用 C 和 Python 解决 8 皇后问题。

一、优化到底优化了什么

标准写法里，我们通常会维护三组状态：

• 哪几列已经放过皇后
• 哪几条主对角线已经被占用
• 哪几条副对角线已经被占用

这些状态用布尔数组表示时，优点是直观，缺点是每次判断和更新都要访问多个数组。

而位运算优化版的核心思想是：

把“占用状态”压缩进整数的二进制位中，让一次按位运算同时完成大量判断。

这类写法在 N 皇后、状态压缩 DP、子集枚举 中都非常常见。对于 8 皇后来说，它可以显著减少常数开销，让搜索更紧凑。

二、如何用二进制表示棋盘状态

仍然假设我们按行递归。处理到某一行时，只需要知道这一行哪些列还能放皇后。

对于 8 x 8 的棋盘，可以用一个 8 位二进制数表示列状态：

• 第 0 位为 1，表示第 0 列被占用
• 第 1 位为 1，表示第 1 列被占用
• ……
• 第 7 位为 1，表示第 7 列被占用

于是我们可以用三个整数来表示搜索状态：

• cols：已经被占用的列
• main_diag：进入当前递归行时，沿列号增大方向投影过来的对角线攻击位置
• anti_diag：进入当前递归行时，沿列号减小方向投影过来的对角线攻击位置

这里最关键的一点是：参数里的掩码描述当前行；选择位置并移位后，传给下一次递归的掩码才描述下一行。它们不是数组版中固定不变的对角线编号。

这样一来，当前行的可选位置就能统一通过一个表达式算出来。

三、当前行哪些位置还能放

先定义一个掩码：

LIMIT = (1 << N) - 1

当 N = 8 时：

LIMIT = 0b11111111

也就是低 8 位全为 1。

当前行所有不能放皇后的位置，就是：

cols | main_diag | anti_diag

因此，当前行所有还能放的位置就是：

available = LIMIT & ~(cols | main_diag | anti_diag)

这行代码非常值得记住，它几乎就是位运算版 N 皇后的核心。

它的含义是：

• 先把列冲突、主对角线冲突、副对角线冲突合并起来
• 再取反，得到“理论上可以放”的位置
• 最后和 LIMIT 相与，确保只保留棋盘范围内的低 N 位

四、如何一个一个取出可选位置

如果 available 中有多个可放位置，我们要像以前一样，一个一个尝试。

位运算里有个非常常见的技巧：

pick = available & -available

它可以取出二进制中最右侧的那个 1。

举个例子，如果：

available = 0b10110000

那么：

pick = 0b00010000

也就是说，pick 就代表“当前先尝试这一列”。

尝试完之后，再把这个位置从可选集合里删掉：

available -= pick

然后继续循环，直到这一行所有可选位置都试过。

五、递归到下一行时，对角线状态怎么更新

如果当前行放了一个皇后，对下一行来说：

• << 1 把列号 c 的攻击位移到 c+1
• >> 1 把列号 c 的攻击位移到 c-1

在位运算里，这正好对应移位：

注意位串书写方向与棋盘方向不同：整数的 bit 0 写在二进制串最右边，但本文把列 0 打印在棋盘最左边。因此“位左移”在这里对应棋盘列号向右增加，不能直接把整数移位方向当成棋盘上的左右。

(main_diag | pick) << 1
(anti_diag | pick) >> 1

所以递归调用会写成：

solve(row + 1,
      cols | pick,
      (main_diag | pick) << 1,
      (anti_diag | pick) >> 1)

注意，这里回溯的本质完全没变：

• 先做选择
• 进入下一层
• 返回后继续尝试别的位置

只不过因为整数是按值传递的，所以我们不再需要像布尔数组那样手动恢复现场。这也是位运算写法看起来更短的原因之一。

六、Python 实现

下面是优化版的 Python 代码。它会输出第一组解，并统计全部解数。

N = 8
LIMIT = (1 << N) - 1
positions = [0] * N
solution_count = 0
first_solution = None


def bit_to_col(bit: int) -> int:
    return bit.bit_length() - 1


def print_board(solution):
    for row in range(N):
        col = bit_to_col(solution[row])
        line = ["."] * N
        line[col] = "Q"
        print(" ".join(line))


def solve(row: int, cols: int, main_diag: int, anti_diag: int) -> None:
    global solution_count, first_solution

    if row == N:
        solution_count += 1
        if first_solution is None:
            first_solution = positions[:]
        return

    available = LIMIT & ~(cols | main_diag | anti_diag)

    while available:
        pick = available & -available
        available -= pick

        positions[row] = pick

        solve(
            row + 1,
            cols | pick,
            (main_diag | pick) << 1,
            (anti_diag | pick) >> 1,
        )

        positions[row] = 0


def solve_eight_queens():
    global solution_count, first_solution
    solution_count = 0
    first_solution = None
    positions[:] = [0] * N
    solve(0, 0, 0, 0)
    if first_solution is not None:
        print("First solution:")
        print_board(first_solution)
    else:
        print("No solution")
    print(f"Total solutions: {solution_count}")


if __name__ == "__main__":
    solve_eight_queens()

代码理解重点

• LIMIT 用来截断到低 8 位
• available 表示当前行所有可放位置
• pick 每次取出一个可放位置
• positions[row] 记录当前行选中的那一位，方便后面还原棋盘

这里没有使用列数组和对角线数组，而是把三种限制全部压缩到了整数里。

入口函数会清零计数、首解与位置数组，顺序重复调用不会累加结果。没有解时也不会把 None 传给棋盘打印函数。全局状态仍意味着它不适合并发调用；若要做成库，应把状态封装在每次求解自己的对象或闭包里。

七、C 实现

再看一版 C 实现。结构和 Python 版本保持一致，只是语言细节不同。

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>

#define N 8

_Static_assert(N >= 1 && N <= 12, "Teaching example: N must be 1..12");

static const uint32_t LIMIT = (UINT32_C(1) << N) - 1;
static uint32_t positions[N];
static uint32_t first_solution[N];
static int solution_count = 0;
static bool has_first_solution = false;

int bit_to_col(uint32_t bit) {
    int col = 0;
    while ((bit >>= 1) != 0) {
        col++;
    }
    return col;
}

void print_board(const uint32_t solution[]) {
    for (int row = 0; row < N; row++) {
        int queen_col = bit_to_col(solution[row]);
        for (int col = 0; col < N; col++) {
            if (col == queen_col) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
}

void solve(int row, uint32_t cols, uint32_t main_diag, uint32_t anti_diag) {
    if (row == N) {
        solution_count++;
        if (!has_first_solution) {
            for (int i = 0; i < N; i++) {
                first_solution[i] = positions[i];
            }
            has_first_solution = true;
        }
        return;
    }

    uint32_t available = LIMIT & ~(cols | main_diag | anti_diag);

    while (available) {
        uint32_t pick = available & (UINT32_C(0) - available);
        available -= pick;

        positions[row] = pick;

        solve(
            row + 1,
            cols | pick,
            (main_diag | pick) << 1,
            (anti_diag | pick) >> 1
        );

        positions[row] = 0;
    }
}

void solve_eight_queens(void) {
    solution_count = 0;
    has_first_solution = false;
    for (int i = 0; i < N; i++) {
        positions[i] = 0;
        first_solution[i] = 0;
    }
    solve(0, 0, 0, 0);
    if (has_first_solution) {
        printf("First solution:\n");
        print_board(first_solution);
    } else {
        printf("No solution\n");
    }
    printf("Total solutions: %d\n", solution_count);
}

int main(void) {
    solve_eight_queens();
    return 0;
}

这份代码里最需要注意的是：

C 掩码改用 uint32_t，UINT32_C(0) - available 刻意利用无符号运算取得最低位。原来的固定 N=8 并未触及有符号溢出边界，但直接增大 N、把移位结果移入符号位或令移位量达到类型位宽，会产生另一类问题。这里用编译期断言把教学范围限制为 N=1 到 12，不把整数类型的位宽当作可任意求解的规模保证。移位边界可参阅 SEI CERT 的 INT34-C 规则。

• pick = available & -available 依然是取最低位的 1
• 整数按值传递，所以递归时不需要手动恢复 cols 和对角线状态
• 为了演示棋盘输出，我们额外保存了第一组解

八、示例输出

按照这套搜索顺序，程序找到的第一组解对应棋盘如下：

Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

最终两份代码都会输出：

Total solutions: 92

九、这种优化为什么更快

先说结论：位运算优化并没有改变问题的指数级本质，它优化的是常数开销。

标准数组写法里，我们每一步都要：

• 检查多个数组
• 更新多个数组
• 回溯时再恢复这些数组

而位运算版里：

• 状态压缩在整数中
• 可选位置一次按位运算就能算出
• 递归参数天然形成“新状态”，不需要额外撤销复杂结构

在 2026-09-07 对本文 Python 代码的记录中，两版进入的递归节点都是 2057 个，解数都是 92。数组版在 1965 个非终止节点各检查 8 列，共 15720 次候选循环；位运算版每次循环恰好产生一条递归边，共 2056 次。它没有额外剪掉合法搜索树，只是不再逐个循环检查已经冲突的列。

这些是由实际递归入口记录和循环结构得到的操作次数，不是 CPU 指令数，也不能把 15720/2056 报成运行时间加速比。原数组示例打印全部 92 个棋盘，位运算示例只打印首解，直接计时会混入不同的输出成本。公平计时应先统一为只计数，使用相同语言、编译选项和 N，再多次测量。本文没有据此声称某个倍数的加速。

讨论复杂度时还要交代假设：若掩码装在一个机器字内，按合法候选遍历的搜索树可用 O(N!) 给出宽松上界；Python 的任意精度整数在 N 增大后并不是恒定成本。压缩状态没有消除组合爆炸，C 的位宽和计数器范围也必须单独检查。

十、什么时候该用标准写法，什么时候该用优化写法

如果你是第一次学习回溯，我仍然建议先掌握标准写法，因为它最容易看清楚问题结构。

如果你已经理解了下面这些概念：

• 按行递归
• 列冲突
• 对角线冲突
• 做选择、递归、撤销选择

那么就可以进一步学习位运算优化版。它会让你意识到：

很多搜索问题不只是“会写递归”就够了，状态表示方式同样决定了性能和代码质量。

十一、核心公式回顾

8 皇后优化版的核心，不是换了另一种算法，而是把原来的回溯过程做了更高效的状态压缩。

整篇文章最值得记住的三句话是：

1. available = LIMIT & ~(cols | main_diag | anti_diag) 用来求当前行可放位置
2. pick = available & -available 用来取出最低位的 1
3. 移位后才得到下一行的攻击范围：位左移对应列号加 1，位右移对应列号减 1

十二、从真实递归入口读取掩码

下表不再使用互不相干的示意数值，而是从本次搜索的两个实际递归入口导出。前缀 [0,4] 表示前两行分别选了列 0 和列 4，现在准备处理第 2 行。表中只显示低 8 位；原始左移掩码可能还含有棋盘外的高位，求 available 时会被 LIMIT 截掉。

同一次 N=8 搜索中的入口快照

变量	前缀 [0]，row=1	前缀 [0,4]，row=2
cols	00000001	00010001
main_diag	00000010	00100100
anti_diag	00000000	00001000
available	11111100	11000010
首个候选 pick	00000100	00000010

第二列到第三列之间选择的是列 4：(00000010 | 00010000) << 1 = 00100100，右移侧则为 00001000。当前可选列因此是 1、6、7，最低候选是列 1。它不等于首个完整解最终选到的列 7：搜索还要先尝试较低候选，失败后再继续。这张表展示指定前缀的入口，不声称它们是全局执行日志中相邻的两次调用。

另一个实际入口是前缀 [0,2,4,1,3]：到 row=5 时，三个掩码的低位并集已经是 11111111，所以 available=0。while available 根本不进入，函数直接返回上一层；并不是用 pick=0 再递归一次。

下载验证包，运行 python3 audit_queens.py 可生成包含快照的 results/audit.json。验证器在每个 Python 递归入口，还会根据已放皇后的坐标重新计算它们对当前行的攻击位置，与传入掩码逐一比对。它检查的是状态含义，而不只是最终总数。

import json
from pathlib import Path

record = json.loads(Path("results/audit.json").read_text())
snapshot = record["n8"]["bits"]["snapshots"]["[0, 4]"]
assert snapshot["main_diag_low_n"] == "00100100"
assert snapshot["available"] == "11000010"
assert snapshot["lowest_candidate"] == "00000010"
print(snapshot)

包内的 Python 和 C 源码直接从本页与基础篇的代码块提取，中英文代码逐字核对相同。C 位运算测试副本额外在终止层打印棋盘，以便核对全部解，而不改变候选选择或状态；所有实现均重复调用两次，并与 基础篇的全解验证对应。参考记录给出源文件和验证器哈希、编译器版本及 sanitizer 结果，没有用渲染动画代替求解正确性验证。

python3 queens_bits.py
cc -std=c11 -O2 -Wall -Wextra -pedantic queens_bits.c -o queens_bits
./queens_bits

十三、总结

标准版帮助理解回溯，位运算版则展示了如何降低候选检查开销。选择实现时，应同时核对解集、状态含义和同等条件下的性能；代码更短不自动等于更正确或在所有环境中更快。