回溯算法进阶：用位运算优化 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

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

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

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

• 主对角线攻击范围会向左移动一格
• 副对角线攻击范围会向右移动一格

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

(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():
    solve(0, 0, 0, 0)
    print("First solution:")
    print_board(first_solution)
    print(f"Total solutions: {solution_count}")


if __name__ == "__main__":
    solve_eight_queens()

代码理解重点

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

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

七、C 实现

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

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

#define N 8

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

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

void print_board(const int 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, int cols, int main_diag, int 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;
    }

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

    while (available) {
        int pick = available & -available;
        available -= pick;

        positions[row] = pick;

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

        positions[row] = 0;
    }
}

int main(void) {
    solve(0, 0, 0, 0);
    printf("First solution:\n");
    print_board(first_solution);
    printf("Total solutions: %d\n", solution_count);
    return 0;
}

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

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

八、示例输出

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

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

最终两份代码都会输出：

Total solutions: 92

九、这种优化为什么更快

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

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

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

而位运算版里：

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

对于 8 皇后 这种规模，优化的意义更多体现在“写法更高级、更紧凑”。但如果你把思路扩展到更大的 N 皇后，位运算版通常会明显比数组版更快。

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

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

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

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

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

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

十一、总结

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

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

1. available = LIMIT & ~(cols | main_diag | anti_diag) 用来求当前行可放位置
2. pick = available & -available 用来取出最低位的 1
3. 主对角线左移，副对角线右移，表示对下一行的攻击范围

如果说标准版 8 皇后教会你“什么是回溯”，那么位运算版 8 皇后教会你的就是：同一个回溯框架，状态表示一旦优化，代码会更短，搜索也会更快。