C 训练营教程

主题

Lesson 29: 八皇后问题 — 回溯与剪枝 ​

练习任务 ​

难度：难 【标杆题】

在 8x8 的国际象棋棋盘上放置 8 个皇后，使得任意两个皇后不能互相攻击。统计所有可能的摆放方案数量。皇后攻击规则：同行、同列、同对角线（正斜线 / 反斜线）。

实现 is_safe(row, c) 冲突检测函数和 solve(row) 回溯函数，输出所有解的个数（应为 92）。col[8] 数组已声明为全局变量，表示每行皇后所在的列号。

本课有 1 组验证用例：

无输入 → 输出 "92"

提示：八皇后是回溯算法的标杆题，也是算法面试中的经典题目。核心挑战有两点：一是理解对角线的冲突判定公式 abs(row - i) == abs(c - col[i])（为什么行差等于列差就意味着同对角线？），二是理解"剪枝"如何将 16,777,216 种暴力枚举缩减为约 15,000 次有效探索。

核心知识点 ​

  • 一维棋盘降维 — col[row] = c 将 8x8 棋盘压缩为 8 元素数组，利用"每行一个皇后"的天然约束
  • 对角线冲突公式 — abs(row - i) == abs(c - col[i])，源自对角线上任意两点的 |Delta r| = |Delta c|
  • is_safe 冲突检测 — 遍历已放置的 0..row-1 行，检查同列 (col[i] == c) 和对角线冲突
  • 剪枝 vs 暴力枚举 — 暴力 8^8 = 16,777,216 种放置，回溯剪枝仅访问约 15,000 节点（剪枝率 > 99.9%）
  • 覆写即撤销 — 递归返回溯算下一轮循环覆盖 col[row]，无需显式恢复旧值
  • 行冲突无需检查 — 按行递归天然保证每行只有一个皇后
  • 92 解的来源 — 8 皇后共有 92 个不同解，旋转/镜像对称下只有 12 个本质不同的解
  • 回溯框架对比 — 全排列（无剪枝，swap 撤销）vs 八皇后（有剪枝，覆写撤销）

代码框架 ​

29_eight_queens.c
c
#include <stdio.h>
#include <stdlib.h>  /* abs() */

int count = 0;
int col[8];  /* col[row] = 皇后在第 row 行所在的列 */

/* 判断在第 row 行第 c 列放置皇后是否安全 */
int is_safe(int row, int c)
{
    // 遍历已经放置好的第 0 到 row-1 行
    // 在这里实现循环：for (int i = 0; i < row; i++) { ... }

    // 检测 1：同列冲突 — 新皇后和已有皇后在同一列
    // if (col[i] == c) return 0;

    // 检测 2：对角线冲突 — 行列差的绝对值相等
    // if (abs(row - i) == abs(c - col[i])) return 0;

    // 都通过则安全，返回 1
}

/* 回溯求解：逐行放置皇后 */
void solve(int row)
{
    // 终止条件：所有 8 行都放好了 → 找到一个解，计数 +1
    // 在这里实现：if (row == 8) { count++; return; }

    // 枚举当前行的每一列 c in [0, 7]
    // 在这里实现循环：for (int c = 0; c < 8; c++) { ... }

    // 如果 (row, c) 安全 → 放置，递归处理下一行
    // 覆写即撤销：下次循环覆盖 col[row]，无需显式恢复
    // 在这里实现：if (is_safe(row, c)) { col[row] = c; solve(row + 1); }
}

int main(void)
{
    // 在这里调用 solve(0);

    // 在这里打印 count：
    // printf("%d\n", count);

    return 0;
}

阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：is_safe 函数中为什么只检查 i < row？对角线冲突公式的绝对值为什么不能省略？

TIP

先不要 往下翻看参考解答。尝试模仿 L28 全排列的回溯模板——选择（枚举列 c）→ 约束检查（is_safe）→ 递归（solve(row+1)）→ 撤销（覆写覆盖）。注意观察与排列的两个关键区别：有剪枝（不安全的列直接跳过），以及撤销通过覆写实现（而不用显式 swap）。

深度讲解 ​

1. 一维棋盘降维：col[row] 的设计智慧 ​

1.1 从二维到一维的灵感 ​

初看八皇后问题，直觉方案是用一个 8x8 的二维数组表示棋盘。但八皇后问题有一个天然的约束条件：每行必须且只能放一个皇后（否则同行攻击）。

既然按行递归放置，每行恰好一个皇后，我们只需要记录每行的皇后放在哪一列。这就是降维的核心思想。

c
int col[8];  // col[row] = 皇后在第 row 行所在的列号 (0~7)
棋盘（8x8）到一维数组的映射：

  0 1 2 3 4 5 6 7         col[8] 数组:
0 . . Q . . . . .         col[0] = 2
1 . . . . Q . . .         col[1] = 4
2 . Q . . . . . .         col[2] = 1
3 . . . . . . . Q         col[3] = 7
4 Q . . . . . . .         col[4] = 0
5 . . . Q . . . .         col[5] = 3
6 . . . . . Q . .         col[6] = 5
7 . . . . . . Q .         col[7] = 6

降维带来的好处：

因为: 每行必须放 1 个皇后（按行递归天然保证）
所以: 不需要 8x8=64 个格子的二维数组，8 个元素的数组足够
效果: 冲突检测只需 O(row) 扫描已放置的行，而不是 O(64)

1.2 数据结构选择的通用原则 ​

这个技巧反映了算法设计中一条重要原则：利用问题内在约束减少数据结构维度。

问题直观数据结构降维后降维依据
八皇后bool board[8][8]int col[8]每行一个皇后
数独int board[9][9](不可降维)每格需独立值
N 皇后bool board[N][N]int col[N]同上

2. 对角线冲突公式：|Delta r| = |Delta c| ​

2.1 几何直觉 ​

皇后是国际象棋中最强的棋子，可以沿横线、竖线、正斜线（/）、反斜线（\）任意距离移动。行冲突由按行递归天然避免，列冲突只需比较列号。对角线的判定是最精妙的部分。

皇后 Q 的攻击范围（× 表示可攻击的格子）：

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
0  | x |   |   | x |   |   |   | x |
   +---+---+---+---+---+---+---+---+
1  |   | x |   | x |   |   | x |   |
   +---+---+---+---+---+---+---+---+
2  |   |   | x | x |   | x |   |   |
   +---+---+---+---+---+---+---+---+
3  | x | x | x | Q | x | x | x | x |  ← 同行攻击
   +---+---+---+---+---+---+---+---+
4  |   |   | x | x |   | x |   |   |
   +---+---+---+---+---+---+---+---+
5  |   | x |   | x |   |   | x |   |
   +---+---+---+---+---+---+---+---+
6  | x |   |   | x |   |   |   | x |
   +---+---+---+---+---+---+---+---+
    ↑
   同列攻击

2.2 对角线公式的证明 ​

在同一条对角线上的任意两点 (r1,c1) 和 (r2,c2)，与水平方向呈 45 度角，意味着斜率绝对值为 1：

|r1 - r2| = |c1 - c2|
正斜线 (/) 示例:                    反斜线 (\) 示例:
  (1,3) 和 (2,2): 行差 1, 列差 1    (0,0) 和 (2,2): 行差 2, 列差 2
  (1,3) 和 (3,1): 行差 2, 列差 2    (1,4) 和 (3,2): 行差 2, 列差 2

任意对角线上两点: |r1-r2| == |c1-c2| 恒成立

由此推导出 is_safe 的核心判断逻辑：

c
int is_safe(int row, int c)
{
    for (int i = 0; i < row; i++) {
        if (col[i] == c)                    // 同列冲突
            return 0;
        if (abs(row - i) == abs(c - col[i])) // 同对角线冲突
            return 0;
    }
    return 1;  // 所有检查通过
}

IMPORTANT

必须用 abs() 取绝对值！如果写成 row - i == c - col[i] 则只检查了正斜线方向（行差等于列差），漏检了行差和列差符号相反的反斜线。abs() 需要 #include <stdlib.h>。

3. 剪枝 vs 暴力枚举：量化对比 ​

3.1 剪枝的具体效果 ​

以第 0 行皇后放在列 3（col[0] = 3）为例，看第 1 行各列的检测结果：

列 0: col[0]=3!=0 ✓, |1-0|=1, |0-3|=3 !=1 ✓ → 安全，递归
列 1: col[0]=3!=1 ✓, |1-0|=1, |1-3|=2 !=1 ✓ → 安全，递归
列 2: col[0]=3!=2 ✓, |1-0|=1, |2-3|=1 =1 ✗ → 对角线冲突！剪掉！
列 3: col[0]=3=3     → 同列冲突！剪掉！
列 4: col[0]=3!=4 ✓, |1-0|=1, |4-3|=1 =1 ✗ → 对角线冲突！剪掉！
列 5: col[0]=3!=5 ✓, |1-0|=1, |5-3|=2 !=1 ✓ → 安全，递归
列 6: col[0]=3!=6 ✓, |1-0|=1, |6-3|=3 !=1 ✓ → 安全，递归
列 7: col[0]=3!=7 ✓, |1-0|=1, |7-3|=4 !=1 ✓ → 安全，递归

8 列中 3 列被剪掉 → 37.5% 的剪枝率仅在第 1 层！
每层剪枝都会产生指数级的节省。

3.2 全局对比 ​

维度暴力枚举 (8^8)回溯 + 剪枝提升
搜索空间16,777,216~15,000—
剪枝率0%> 99.9%几乎全部剪掉
耗时不可行毫秒级—
策略生成所有 8^8 种放置再验证边生成边验证，提前剪掉—

NOTE

剪枝率超过 99.9% 意味着：每 1000 种可能的放置中，只有不到 1 种通过了冲突检测。这就是剪枝的力量——在搜索树的内部节点上排除整棵子树，避免指数级浪费。

4. "覆写即撤销"：无需要达式恢复 ​

4.1 与全排列的撤销方式对比 ​

全排列（L28）中的回溯需要显式撤销 swap：

c
swap(&str[l], &str[i]);       // 选择
permute(str, l + 1, r);       // 递归
swap(&str[l], &str[i]);       // 撤销 ← 必须写！

八皇后中的回溯无需要达式式撤销：

c
void solve(int row)
{
    if (row == 8) { count++; return; }

    for (int c = 0; c < 8; c++) {
        if (is_safe(row, c)) {
            col[row] = c;        // 放置（选择）
            solve(row + 1);      // 递归
            // 无需写 col[row] = old_value！
            // 因为下次循环的 col[row] = new_c 会直接覆盖
        }
    }
}

4.2 为什么覆写就够？ ​

两个关键理由：

  1. is_safe 只检查 i < row：当前行 row 的旧值 col[row] 在后续递归中只作为 i < row 的检查对象，而 i < row+1 下一层递归会固定 row+1。当递归返回到当前层时，col[row] 的旧值只会影响 for 循环的下一次迭代中的 is_safe(row, c_new)——但此时我们正在给 col[row] 赋新值，旧值不会被使用。

  2. 赋值覆盖了旧值：col[row] = c_new 直接覆盖了 col[row] = c_old，无需先擦除再写。

TIP

这是一个重要的编程直觉：如果下一次赋值必然覆盖当前值，就不需要显式撤销。反之，如果操作是增量式的（如 used[i]=true 标记已使用），则需要显式恢复 used[i]=false。

5. 为何无需行冲突检查 ​

这是一个理解回溯框架设计的关键问题。

答案：按行递归天然避免。

solve(row) 的含义：在第 row 行放置一个字皇后
├─ 每一层递归只处理一行
├─ 每行只放一个皇后（for 循环中只赋值 col[row] = c 一次）
─── 不存在"同一行放两个皇后"的可能

因此检查同列和对角线就够了。

如果改成按列递归（solve(col)），则需要检查行冲突而不是列冲突——原理完全对称。按行是习惯选择，因为 row 作为递归参数取值 0..7 与数组索引天然对应。

6. 92 解 → 旋转/镜像下 12 本质解 ​

6.1 为什么恰好是 92？ ​

8 皇后问题共有 92 个不同的解。每个解由 col[0..7] 数组唯一确定。printf("%d\n", count) 输出 92 是正确的验证结果。

6.2 对称性分析 ​

考虑棋盘的对称变换——旋转 90/180/270 度和镜像翻转——许多解可以通过这些变换互相转化：

对称变换类型：旋转 90 度、旋转 180 度、旋转 270 度、水平镜像、垂直镜像、对角线镜像

92 个解 → 考虑所有 8 种对称变换 → 归类为 12 组等价类 → 12 个本质不同的解

例如第 1 个解: col[] = {0, 2, 4, 1, 7, 5, 3, 6}
旋转 90 度后变为另一个解（仍属于同一等价类）
概念数量说明
所有解92旋转和镜像视为不同
本质解12旋转和镜像视为相同

对称变换的具体例子：拿第 1 个解 col[] = {0, 2, 4, 1, 7, 5, 3, 6}（即皇后在 (0,0), (1,2), (2,4), (3,1), (4,7), (5,5), (6,3), (7,6)），对它施加旋转 90 度（公式：(r,c) -> (c, 7-r)）：

变换过程:
  (0,0) -> (0,7)    (1,2) -> (2,6)    (2,4) -> (4,5)    (3,1) -> (1,4)
  (4,7) -> (7,3)    (5,5) -> (5,2)    (6,3) -> (3,1)    (7,6) -> (6,0)

按行排序后得到新解 col[] = {0, 3, 4, 6, 5, 7, 2, 1}。这仍然是 8 皇后的一个合法解，且与原解属于同一个等价类。

每个等价类可能包含 1~8 个解（取决于该解在哪些变换下保持不变），92 个解经 8 种对称变换归类后，恰好形成 12 个等价类，因此本质不同的解只有 12 个。

7. 回溯框架对比：全排列 vs 八皇后 ​

维度全排列 (L28)八皇后 (L29)
搜索空间n! 种排列8^8 = 16,777,216 种放置
约束条件无重复使用同一元素皇后之间不能互相攻击
剪枝无（生成所有排列）有（冲突即跳过）
冲突检测used[i] 标记is_safe() 检查列和对角线
撤销操作显式 swap 恢复覆写赋值，无需显式撤销
递归深度n（排列长度）8（行数）
叶子节点数n!< n!（剪枝后远少于 8!）
时间复杂度O(n x n!)< O(8^8)（有剪枝）

NOTE

全排列和八皇后是回溯算法的两个经典范例，分别展示了回溯的两种形态："无剪枝的回溯"（排列 生成）和"带剪枝的回溯"（约束满足）。理解这两者的区别和联系，就掌握了回溯算法的核心框架。

参考解答 ​

练习: is_safe + solve 完整实现
solution_29_eight_queens.c
c
#include <stdio.h>
#include <stdlib.h>  /* abs() */

int count = 0;
int col[8];  /* col[row] = 皇后在第 row 行所在的列 */

/* 判断在第 row 行第 c 列放置皇后是否安全 */
int is_safe(int row, int c)
{
    for (int i = 0; i < row; i++) {
        /* 检测同列冲突 */
        if (col[i] == c)
            return 0;

        /* 检测对角线冲突：|行差| == |列差| */
        if (abs(row - i) == abs(c - col[i]))
            return 0;
    }
    return 1;  /* 安全 */
}

/* 回溯算求解：逐行放置皇后 */
void solve(int row)
{
    if (row == 8) {
        count++;         /* 找到一个解 */
        return;
    }

    for (int c = 0; c < 8; c++) {
        if (is_safe(row, c)) {
            col[row] = c;       /* 放置 */
            solve(row + 1);     /* 递归下一行 */
            /* 覆写即撤销：下次循环覆盖 col[row] */
        }
    }
}

int main(void)
{
    count = 0;
    solve(0);
    printf("%d\n", count);  /* 输出 92 */
    return 0;
}

核心逻辑解析：

  1. is_safe 精确检测两种冲突：同列（值相等）、同对角线（行列差绝对值相等）。
  2. 剪枝发生在 if (is_safe(row, c))：不安全的列直接跳过，不进入递归。
  3. 撤销通过覆写实现：col[row] = c 在每次循环迭代重新赋值，旧值自然被覆盖。
  4. solve(0) 启动：从第 0 行开始，逐步构建 8 行的完整体右放。

对照检查：is_safe 遍历了 i < row 吗？对角线用了 abs() 吗？solve 在 row == 8 时计数了吗？main 初始化了 count = 0 吗？

课堂讨论 ​

  1. 如果把对角线冲突公式中的 abs() 去掉（即 row - i == c - col[i]），结果会变成多少？为什么？
  2. 八皇后的剪枝率和哪些因素有关？如果棋盘大小从 8 变成 N，剪枝率会如何变化？
  3. 在回溯框架中，"选择-递归-撤销"三分支。其中，八皇后的"撤销"为什么可以省略？在什么情况下不能省略？
  4. 全排列（L28）和八皇后（L29）在回溯框架上最本质的区别是什么？用一个词概括并解释。
  5. 已知 8 皇后有 92 个解，12 个本质解。能否通过数学推导（不运行程序）证明 92 这个数字？

讨论答案 ​

Q1: 去掉 abs() 的结果

如果写成 row - i == c - col[i]（即只用正斜线判断），会漏检反斜线上（行列差符号相反）的冲突，导致大量非法解被错误接受。

例如：col[2] = 0 和 col[4] = 6：

  • 行差 = 4 - 2 = 2
  • 列差 = 6 - 0 = 6
  • row - i == c - col[i] → 2 == 6 → false（正确，不在同一对角线？不对！）

等等——实际上 abs(2) == abs(6) 是 false（不冲突），所以这个例子没问题。但考虑：

  • col[0] = 0 和 col[1] = 1：abs(1) == abs(1) → 冲突（正斜线），1-0 == 1-0 → true → 也检测到
  • col[0] = 0 和 col[1] = 7：abs(1) == abs(7) → 不是对角线
  • col[2] = 3 和 col[5] = 0：abs(3) == abs(3) → 冲突（反斜线），5-2 == 0-3 → 3 == -3 → false → 漏检！

所以去掉 abs() 会漏检反斜线上的冲突，count 会远大于 92。

Q2: 剪枝率的变化规律

剪枝率受到棋盘大小 N、皇后数量和冲突检测策略的影响：

  • N 增大时：搜索空间呈指数级增长（N^N），但合法解的增长速度慢得多
  • 剪枝率会更高（几乎接近 100%），因为约束密度增大
  • 但实际访问节点数仍会增长（虽然被大幅剪枝），N=20 时即使剪枝后也很难在合理时间内完成
Q3: 撤销何时不能省略？

当"选择"操作是增量式（而非覆写式）时，必须显式撤销。例如：

c
// 增量式（必须显式撤销）：
bool used[8] = {false};
void backtrack(int row){
    for(int c=0;c<8;c++){
        if(!used[c]){
            used[c]=true;        // 增量：标记为已使用
            backtrack(row+1);
            used[c]=false;       // 必须显式撤销！
        }
    }
}

// 覆写式（无需显式撤销）：
col[row]=c; // 直接覆盖旧值，下次循环会再次覆盖

核心区别：增量式在"标记"时修改了一个共享状态，不撤销会影响其他分支；覆写式每次赋值都完全替换旧值，旧值自然失效。

Q4: 最本质的区别

剪枝。

全排列排列没有剪枝——它必须生成所有 n! 个排列。八皇后有剪枝——在搜索树的中间节点就排除了不可能的分支。

剪枝是回溯算法强大效率的来源。没有剪枝的回溯就是穷举搜索；有了剪枝，回溯成为真正高效的算法设计范式。

Q5: 能否数学推导 92

严格意义上，92 是一个通过计算机搜索发现的经验数字。没有简单的闭合公式可以直接推导出 N 皇后问题的解的数量。

原因在于：N 皇后问题属于组合数学中的"精确覆盖"问题，解的数量不是一个简单的解析函数。它是一个典型的"需要程序计算"的组合数。

但可以通过以下方式验证：

  • 对称性分析将搜索空间缩减到原空间的 1/8
  • 使用生成函数或 Burnside 引理验证 12 个本质解的存在
  • 通过回溯程序的输出确认 92 是所有解的总数

课后练习 ​

  1. 打印棋盘布局。修改 solve 函数，每找到一个解时打印完整的 8x8 棋盘（'Q' 表示皇后，'.' 表示空格），然后提示用户按任意键继续。观察第一个解的棋盘布局。

    知识点提示：col[row] 记录了每行皇后的列号。打印棋盘用两层循环：外层 row 遍历行，内层 c 遍历列，col[row] == c 处打印 'Q' 否则 '.'。

    参考解答
    print_board.c
    c
    void print_board(void)
{
    for (int row = 0; row < 8; row++) {
        for (int c = 0; c < 8; c++) {
            if (col[row] == c)
                printf("Q ");
            else
                printf(". ");
        }
        printf("\n");
    }
    printf("\n");
}

void solve(int row)
{
    if (row == 8) {
        count++;
        printf("Solution %d:\n", count);
        print_board();
        getchar();  /* 按任意键继续 */
        return;
    }
    /* ... 同上 ... */
}

  2. 只找第一个解。修改 solve 函数，找到第一个解后就立即退出所有递归（不继续搜索剩余的 91 个解）。

    知识点提示：设置一个安全全局标志 int found = 0，在 row == 8 时置为 1。每一层递归前检查 if (found) return;，确保一旦找到解就从所有递归层快速退出。

    参考解答
    first_solution.c
    c
    int found = 0;

void solve(int row)
{
    if (found) return;  /* 已找到，快速退出 */

    if (row == 8) {
        found = 1;
        /* 打印或只记录 col[] */
        return;
    }

    for (int c = 0; c < 8; c++) {
        if (is_safe(row, c)) {
            col[row] = c;
            solve(row + 1);
            if (found) return;  /* 传播退出信号 */
        }
    }
}

  3. N 皇后问题。将棋盘大小从 8 改为 N（N 由用户输入），修改数组大小和循环边界，统计 N 皇后问题的解数量。测试 N=4 时有 2 个解，N=5 时有 10 个解。

    知识点提示：用 int *col = malloc(N * sizeof(int)) 动态分配数组。is_safe 和 solve 的逻辑不变，只需用 N 替换字面量 8。

    参考解答
    n_queens.c
    c
    #include <stdio.h>
#include <stdlib.h>

int count = 0;
int *col;
int N;

int is_safe(int row, int c)
{
    for (int i = 0; i < row; i++) {
        if (col[i] == c) return 0;
        if (abs(row - i) == abs(c - col[i])) return 0;
    }
    return 1;
}

void solve(int row)
{
    if (row == N) { count++; return; }
    for (int c = 0; c < N; c++) {
        if (is_safe(row, c)) {
            col[row] = c;
            solve(row + 1);
        }
    }
}

int main(void)
{
    scanf("%d", &N);
    col = malloc(N * sizeof(int));
    count = 0;
    solve(0);
    printf("%d\n", count);
    free(col);
    return 0;
}

    验证：N=4 → 2, N=5 → 10, N=6 → 4, N=7 → 40, N=8 → 92

  4. 回溯框架迁移：数独求解器。给定一个 9x9 的数独棋盘（用 '.' 表示空格），用回溯算法填充所有空格。检测规则：每行 、每列、每个 3x3 方块内 1-9 不重复。

    知识点提示：这是八皇后在更高维度上的扩展——约束从 2 种（列、对角线）增加到 3 种（行、列、3x3 方块）。is_safe 需要检查三个维度。回溯框架完全相同：枚举候选数字 → 安全检查 → 放置 → 递归 → 撤销。

    参考解答
    sudoku_solver.c
    c
    #include <stdio.h>
#include <stdbool.h>

/* board[row][col] = 0 表示空格，1-9 表示已填数字 */
int board[9][9];

bool is_safe(int row, int col, int num)
{
    /* 检查行 */
    for (int c = 0; c < 9; c++)
        if (board[row][c] == num) return false;

    /* 检查排列 */
    for (int r = 0; r < 9; r++)
        if (board[r][col] == num) return false;

    /* 检查 3x3 方块 */
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int r = 0; r < 3; r++)
        for (int c = 0; c < 3; c++)
            if (board[startRow + r][startCol + c] == num)
                return false;

    return true;
}

bool solve(int row, int col)
{
    if (row == 9) return true;  /* 所有行完成 */
    if (col == 9) return solve(row + 1, 0);  /* 转到下一行 */
    if (board[row][col] != 0) return solve(row, col + 1);  /* 已填，跳过 */

    for (int num = 1; num <= 9; num++) {
        if (is_safe(row, col, num)) {
            board[row][col] = num;
            if (solve(row, col + 1)) return true;
            board[row][col] = 0;  /* 回溯：撤销 */
        }
    }
    return false;  /* 无解 */
}

    观察：数独的回溯框架与八皇后高度相似。区别在于：数独有 3 种约束（行、列、宫），且每个格子的候选是 1-9（而非 0-7 列）。

参考资料 ​

  • Wikipedia: Eight Queens Puzzle — 八皇后问题的完整数学分析
  • 《算法导论》(CLRS) 第 4 版 — 回溯算法章节
  • N. Wirth《Algorithms + Data Structures = Programs》 — 经典的"程序 = 算法 + 数据结构"论述
  • OEIS A000170 — N 皇后问题解的序列：1, 1, 0, 0, 2, 10, 4, 40, 92, 352, ...

"The purpose of computing is insight, not numbers." — Richard Hamming

Released under the MIT License.

Copyright © 2026-present OpenCamp C Team