回溯算法是很多人系统学习搜索问题时绕不开的一道坎。它表面上像“暴力枚举”，但真正的关键不是把所有情况都试一遍，而是：在搜索过程中，尽早发现不合法的选择，并立刻回退。
8 皇后问题正是一个非常经典的回溯入门题。规则不复杂，但足够典型，刚好能把回溯中的“做选择、递归、撤销选择”讲清楚。
这篇文章就从零开始，用最标准的“回溯 + 剪枝”思路，带你一步一步解决 8 皇后问题，并分别给出 C 和 Python 的完整实现。
一、什么是 8 皇后问题
8 皇后问题的要求是：
在一个
8 × 8的棋盘上放置 8 个皇后，使得任意两个皇后都不能互相攻击。
皇后的攻击方式包括：
- 同一行
- 同一列
- 同一条主对角线
- 同一条副对角线
因此，我们需要找到所有满足条件的摆放方式，并统计总解数。
8 皇后的经典结论是：一共有 92 个解。
二、为什么这道题适合用回溯
如果完全不加思考地暴力枚举，每个格子都可能放或不放，搜索空间会非常大。
但这道题有一个天然的突破口：
按行放皇后。
也就是说：
- 第 0 行放一个皇后
- 第 1 行放一个皇后
- 第 2 行放一个皇后
- ……
- 一直放到第 7 行
这样做有两个好处：
- 每一行只放一个皇后，所以“行冲突”自动消失
- 我们只需要额外检查列冲突和对角线冲突
于是问题就变成了：
在当前这一行，尝试把皇后放到某一列；如果合法，就继续递归到下一行；如果不合法，就换一个位置继续试。
这就是回溯最典型的结构。
三、回溯算法的三步
回溯的核心可以概括成三句话：
- 做选择
- 递归进入下一层
- 撤销选择
放到 8 皇后问题里，对应关系非常直接：
- 做选择：把当前行的皇后尝试放到某一列
- 递归：继续去处理下一行
- 撤销选择：把刚才放下的皇后拿掉，恢复状态，尝试别的列
这里“撤销选择”非常重要。因为回溯并不是一条路走到底，而是一旦发现当前分支走不通，就要退回上一步，重新选。
四、状态怎么设计
如果想让程序写得清楚，先要想清楚到底需要记录哪些信息。
1. 用 board[row] = col 表示皇后位置
比如：
board[0] = 0
board[1] = 4
board[2] = 7表示：
- 第 0 行皇后放在第 0 列
- 第 1 行皇后放在第 4 列
- 第 2 行皇后放在第 7 列
2. 用 cols[col] 记录列是否被占用
如果某一列已经放过皇后，那么当前行就不能再放到这一列。
3. 用 main_diag[row - col + n - 1] 记录主对角线
主对角线的特点是：row - col 相同。
由于这个值可能为负数，所以通常加上偏移量 n - 1。
4. 用 anti_diag[row + col] 记录副对角线
副对角线的特点是：row + col 相同。
5. 为什么不用单独记录“行是否被占用”
因为我们本来就是按行递归：
- 递归到第 0 层，就处理第 0 行
- 递归到第 1 层，就处理第 1 行
- 递归到第 2 层，就处理第 2 行
所以每一层天然只会给一行放一个皇后，不需要再额外记录行状态。
五、剪枝到底剪掉了什么
所谓剪枝，就是在还没有搜索到底的时候，提前发现“这条路不可能成功”，于是直接停止往下搜。
在 8 皇后问题里，如果当前准备把皇后放在 (row, col)，只要满足下面任意一个条件，就可以直接跳过：
- 这一列已经有皇后
- 这条主对角线已经有皇后
- 这条副对角线已经有皇后
这就是为什么我们说 8 皇后是“回溯 + 剪枝”的经典题：它不是盲目试探，而是边试边排除无效分支。
六、搜索过程怎么展开
整个搜索过程可以理解成一棵树：
- 每一层代表一行
- 每个分支代表这一行选择某一列
- 如果该位置不合法，就不再继续深入这条分支
举个简单例子：
- 从左到右搜索，会到达前五行依次放在
[0, 2, 4, 1, 3]的分支。 - 处理第 5 行时，列 0 到 4 已占用；剩下的列 5、6、7 也都受到对角线攻击。
- 第 5 行没有合法选择，于是回到第 4 行撤销列 3，继续尝试其他列。
- 只在该层候选全部耗尽时再往上退，不是遇到一次冲突就直接退回第 0 行。
这就是回溯中的“往前试、走不通就退回来”。
七、Python 实现
下面先给出 Python 版本。它会打印全部解，并在最后统计总解数。
N = 8
cols = [False] * N
main_diag = [False] * (2 * N - 1)
anti_diag = [False] * (2 * N - 1)
board = [-1] * N
solution_count = 0
def print_board():
for row in range(N):
line = ["."] * N
line[board[row]] = "Q"
print(" ".join(line))
print()
def backtrack(row: int) -> None:
global solution_count
if row == N:
solution_count += 1
print(f"Solution {solution_count}:")
print_board()
return
for col in range(N):
d1 = row - col + N - 1
d2 = row + col
if cols[col] or main_diag[d1] or anti_diag[d2]:
continue
board[row] = col
cols[col] = True
main_diag[d1] = True
anti_diag[d2] = True
backtrack(row + 1)
cols[col] = False
main_diag[d1] = False
anti_diag[d2] = False
board[row] = -1
def solve_eight_queens() -> None:
global solution_count
solution_count = 0
cols[:] = [False] * N
main_diag[:] = [False] * (2 * N - 1)
anti_diag[:] = [False] * (2 * N - 1)
board[:] = [-1] * N
backtrack(0)
print(f"Total solutions: {solution_count}")
if __name__ == "__main__":
solve_eight_queens()
这段代码最关键的地方
row == N说明 8 行都已经成功放置皇后，此时找到一个完整解if cols[col] or main_diag[d1] or anti_diag[d2]用来做合法性判断- 递归前先标记占用状态，递归后再恢复状态
这就是标准回溯模板最典型的写法。
入口函数还负责清零计数并重置数组。递归返回时撤销的是当前搜索分支的占用状态，不会自动把 solution_count 清零。旧版在同一进程连续调用两次会输出 92、184；现在两次都输出 92。这里仍使用全局变量演示状态，所以适合顺序调用，不是线程安全的求解器接口。
八、C 实现
再看一版 C 实现。算法逻辑和 Python 版本完全一致，只是写法更偏底层。
#include <stdbool.h>
#include <stdio.h>
#define N 8
_Static_assert(N >= 1 && N <= 12, "Teaching example: N must be 1..12");
static bool cols[N];
static bool main_diag[2 * N - 1];
static bool anti_diag[2 * N - 1];
static int board[N];
static int solution_count = 0;
void print_board(void) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (board[row] == col) {
printf("Q ");
} else {
printf(". ");
}
}
printf("\n");
}
printf("\n");
}
void backtrack(int row) {
if (row == N) {
solution_count++;
printf("Solution %d:\n", solution_count);
print_board();
return;
}
for (int col = 0; col < N; col++) {
int d1 = row - col + N - 1;
int d2 = row + col;
if (cols[col] || main_diag[d1] || anti_diag[d2]) {
continue;
}
board[row] = col;
cols[col] = true;
main_diag[d1] = true;
anti_diag[d2] = true;
backtrack(row + 1);
cols[col] = false;
main_diag[d1] = false;
anti_diag[d2] = false;
board[row] = -1;
}
}
void solve_eight_queens(void) {
solution_count = 0;
for (int i = 0; i < N; i++) {
cols[i] = false;
board[i] = -1;
}
for (int i = 0; i < 2 * N - 1; i++) {
main_diag[i] = false;
anti_diag[i] = false;
}
backtrack(0);
printf("Total solutions: %d\n", solution_count);
}
int main(void) {
solve_eight_queens();
return 0;
}
虽然语言不同，但思路完全一样：
- 当前处理第
row行 - 枚举这一行所有可能的列
- 合法就递归
- 递归回来之后撤销状态
九、示例输出
按照“从左到右尝试列”的顺序，程序找到的第一组解对应的列下标是：
[0, 4, 7, 5, 2, 6, 1, 3]对应棋盘如下：
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
程序最终会输出：
Total solutions: 92十、时间复杂度和空间复杂度
时间复杂度
需要区分合法搜索树和代码里的候选检查。第 r 层的合法列前缀不超过 N!/(N-r)! 个，所有层合计可用 O(N!) 给出上界；对角线剪枝还会减少实际节点。
原因是：
- 第 0 行最多尝试
N个位置 - 第 1 行最多尝试
N - 1个位置 - 第 2 行最多尝试
N - 2个位置 - 后面依次递减
上面的 N、N-1、N-2 指未占用列的数量，并不是本文 for col in range(N) 的循环次数。它在每个非终止节点仍检查 N 列，所以忽略打印时，用 O(N × N!) 描述这份数组实现的宽松时间上界更清楚。输出 S 个完整棋盘还需写出约 S × N² 个格子；计时不能把这部分当成免费操作。
空间复杂度
空间开销主要来自：
- 递归深度
O(N) - 列和对角线状态数组
O(N)
因此整体空间复杂度可以看作 O(N)。
十一、这道题真正值得学会的东西
8 皇后最重要的，不只是“做出一道题”，而是掌握下面这些回溯思想：
- 先定义搜索层次，比如这里的“按行递归”
- 明确哪些状态必须记录
- 把不合法分支尽早剪掉
- 递归返回时撤销之前的选择
当你真正理解了这些，再去看全排列、组合、子集、数独、括号生成等问题时，会发现它们的底层结构非常相似。
十二、回溯状态与验证表
判断一份 8 皇后回溯代码是否可靠，不能只看它打印了一个棋盘。更好的做法是把搜索状态、剪枝条件和最终计数拆开检查。下面这张表可以作为复现实验时的最小审计记录。
| 检查点 | 代码中的位置 | 应该验证什么 |
|---|---|---|
| 搜索层次 | backtrack(row) |
每一层只处理一行，递归深度最多为 N。 |
| 列冲突 | cols[col] |
同一列不能出现两个皇后，撤销时必须恢复为 false。 |
| 对角线冲突 | row + col 与 row - col + N - 1 |
两条对角线编号不越界，并且和棋盘攻击方向一致。 |
| 回溯恢复 | 递归调用后的状态撤销 | board、列数组、两组对角线数组都回到进入递归前的状态。 |
| 结果复核 | solution_count |
N = 8 时应输出 Total solutions: 92。 |
把 92 个解全部拿出来核对
只检查最后一行的 92 不够：程序可能重复输出同一棋盘，也可能少算一些、同时多算另一些。2026-09-07 的复核因此保留每个解的完整列序列，先检查无重复和行列/对角线约束，再用另一种方法穷举 8! 个列排列，逐一比较完整解集。这是棋盘坐标不同的全部解，不合并旋转或镜像。
下载代码与验证包，解压后运行 python3 audit_queens.py。它只需要 Python 标准库和支持 C11、AddressSanitizer、UndefinedBehaviorSanitizer 的 C 编译器。92 个参考棋盘 CSV不是手工抄的答案，而是此次实际执行导出的结果。运行后可再独立核对：
import csv
from itertools import permutations
with open("results/solutions-8.csv", newline="") as f:
reader = csv.reader(f)
next(reader)
boards = [tuple(map(int, row)) for row in reader]
expected = {
p for p in permutations(range(8))
if all(abs(p[i] - p[j]) != i - j
for i in range(8) for j in range(i))
}
assert len(boards) == len(set(boards)) == 92
assert set(boards) == expected
print("all 92 boards match the permutation check")这段校验不复用求解器的占用数组或位掩码。若最后两个断言失败，应先区分重复解、非法棋盘和漏解；不要简单把计数改成 92。问题的另一种建模方式可参阅 Google OR-Tools 的 N 皇后约束模型。
| 记录 | 实际结果 |
|---|---|
| 每层进入次数，含根节点和终止层 | 1, 8, 42, 140, 344, 568, 550, 312, 92 |
| 递归入口总次数 | 2057 |
| 候选循环体次数 | 8 × (2057 - 92) = 15720 |
| 同一进程再次调用 | 仍为 92，不累计为 184 |
验证包还测试了 N=1 到 12：解数依次为 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200。两种语言的数组版和位运算版完整解序列一致；N≤8 另做全排列对照，N=9 到 12 没有做全排列穷举，因此不把这部分语言间一致性称为同强度的独立校验。C 版在 N=8 通过两类 sanitizer 检查，具体编译器、源码哈希和结果在 运行记录中。
单独运行下载包中的教程代码：
python3 queens_array.py
cc -std=c11 -O2 -Wall -Wextra -pedantic queens_array.c -o queens_array
./queens_arrayC 代码把本教学示例限制在 N=1 到 12，避免把固定规模演示误当成任意规模接口。首次阅读只需运行默认 N=8。验证脚本会调整测试副本中的 N，并在同一进程调用两次；它不修改下载的源文件。
十三、总结
8 皇后问题是理解回溯算法的一个非常好的起点，因为它同时具备：
- 清晰的搜索结构
- 典型的剪枝条件
- 直观的状态设计
- 标准的“做选择 → 递归 → 撤销选择”流程
如果你刚开始接触回溯，建议先把这版标准写法真正敲一遍。等你把这套框架吃透之后，再去看位运算优化版，会更容易理解“状态压缩”到底优化了什么。
如果你想继续往下看，可以接着读这篇进阶文章：