数独求解器设计与实现：位掩码、MRV剪枝与C语言实践

简介：华中科技大学计算机学院20级数据结构课程设计高分项目，主题是用C/C++实现DPLL算法SAT求解器并解决数独问题，适合正在完成类似课设、需要参考完整源码与报告的学生。压缩包共21个文件，其中12个cnf测试用例用于验证算法求解效果，3个exe可执行程序便于直接运行，1个cpp源程序提供完整实现，1份docx报告阐述设计思路，另有工程配置与依赖文件，整体约907KB。项目核心思路是将数独填充转化为合取范式（CNF），通过DPLL算法结合单位推理与回溯搜索唯一解，报告中还涉及纯文字消除、子句学习等优化策略，完整覆盖从约束编码到数独求解的主要流程。已有781人学习，内含可直接运行的主程序与数独验证工具，以及多组cnf数独题目，方便对照报告逐行理解算法实现与调试验证，对学习布尔可满足性问题建模也有帮助。

1. 华科数独课设的高分线不在回溯，而在数据结构怎么选

华中科技大学计算机学院 20 级《数据结构》课设里，数独是每年都有人选的老题：给定 9×9 残缺盘面，用程序把空格填完。看起来就是写个回溯，但真正拉开分数差距的是盘面用什么数据结构存、候选数怎么维护、剪枝在哪一层做。有人交 200 行盲目递归勉强跑通，有人用位掩码加 MRV 把「世界最难数独」压到毫秒级，还附一张复杂度对照表。下文按源程序与报告两个交付物展开：先定数据结构，再写求解器，补文件读写与测试，最后落到报告和答辩。正在做课设的同学可以照着落地，想复习数据结构与算法的工程师也能复用其中的位运算和回溯代码。

2. 数独盘面的数据结构设计：二维数组、位掩码与候选表

2.1 棋盘为什么用 int[9][9] 而不是 char[9][9]

最常见的盘面存储是 9×9 二维数组，值域 1～9，0 表示空格。有些课设为了省内存选 char 类型，其实没必要：整个问题规模就是 81 个格子，任何类型都远小于缓存行，内存不是瓶颈，代码可读性才是。int 配合 printf("%d") 直接输出，和 scanf 交互时不用处理 char 的符号问题，出 bug 的概率更低。这个「选 int 不选 char」的理由本身就可以写进报告的数据结构论证小节。

如果在意局部性，可以用一维数组 grid[81]，r 行 c 列映射到 idx = r*9 + c。对 9×9 这种规模，二维和一维几乎没有性能差异，但一维数组在空格列表场景下更顺手：空格的 idx 直接等于它在数组里的下标，回溯时不需要同时维护 (r, c) 两个字段。课设代码里可以两种混用——结构体存二维数组方便打印，空格列表存 idx 方便排序，换算只差一句除法。

2.2 用三个位掩码维护行、列、宫的候选数

教科书写法一般开三个 bool 数组，比如 valid_row[9][10]，第 k 位表示数字 k 是否可用。这种写法直观，但回溯时要同时维护三张表，每填一个数要置三个标记，代码分散且容易漏更新。更紧凑的做法是位掩码：每行、每列、每宫各用一个 unsigned short，bit k 对应数字 k+1 是否可用，数字 d 的掩码是1u << (d-1)。

判定「第 r 行第 c 列还能填哪些数」变成一次与运算：

int b = r / 3 * 3 + c / 3; // 宫号：行块 * 3 + 列块 unsigned short mask = row_mask[r] & col_mask[c] & blk_mask[b];

逻辑说明：一个数字必须同时满足行、列、宫三个约束，所以三个掩码取交集；任何一层已经用过该数字，对应位为 0，结果里就是 0。这个 mask 在每一层递归里只要三条语句就能得到，后续枚举候选数直接在 mask 上做，不再回盘面里数一遍已有值。相比逐个试 1～9 再查三张表，交集写法把「判定」和「枚举」合并了。

提示：unsigned short 只有 16 位，存 1～9 的掩码绰绰有余；用 int 也可以，但报告里写清「为什么够用」，本身就是一个小得分点。

2.3 空格列表与候选数预排序：MRV 的基础

回溯的搜索空间是空格的全排列，空格处理顺序直接影响剪枝效果。常见做法是读入盘面后，把所有空格收集成数组，每个元素记 idx 和候选数个数。初始阶段就按候选数个数升序排好，这就是 MRV（Minimum Remaining Values，最少剩余值）启发式：每次递归优先填「可填数字最少」的空格，死路会早暴露，搜索树会被大幅压缩。

候选数个数通过数 mask 里的 1 得到，C 语言里最常用的是while (mask) { cnt++; mask &= mask - 1; }，每轮清掉最低位的 1。求解器的主体结构体可以这样定义：

typedef struct { int idx; // 0..80，r = idx / 9，c = idx % 9 unsigned short mask; // 该空格当前候选掩码，缓存用 } EmptyCell; typedef struct { int grid[9][9]; // 盘面，0 表示空格 unsigned short row_mask[9]; // 每行可用数字掩码 unsigned short col_mask[9]; // 每列可用数字掩码 unsigned short blk_mask[9]; // 每宫可用数字掩码，宫号 = r/3*3 + c/3 EmptyCell empties[81]; int empty_cnt; // 空格总数 } Sudoku;

参数说明：row_mask[r] 的第 d 位为 1 表示数字 d+1 还没出现在第 r 行；结构体保存的是「当前递归状态」下的掩码，set_cell 和 clear_cell 负责同步。empties 数组每次递归重新计算各空格当前的 mask，配合 MRV 做动态选择，而不是只在读盘时排一次序——因为随着递归深入，每个空格的候选数会持续变化。这个结构体和报告里「详细设计」一节直接对应，画函数调用图也方便。

初始化时所有掩码位先全置为 1，row_mask[i] = col_mask[i] = blk_mask[i] = 0x1FF，因为 1～9 共 9 位。然后把题目给定的数字逐个通过 set_cell 填进去，掩码自动变成「剩余可用数字」。注意题目本身可能无解，例如同一行出现两个 5，这一步不会报错，要留到求解器里通过无解路径发现；也可以在 set_cell 里断言该位原来是 1，这是一个值得写进报告的防御性细节。

3. 从盲目回溯到带剪枝的求解器：C 语言递归实现

3.1 递归骨架：返回值设计成 int

求解器核心是递归函数 solve_sudoku(Sudoku *s, int rest)，rest 是剩余空格数。返回值用 int 而不是 void，好处是能表达状态：1 表示找到解，0 表示当前路径无解。后面要做多解判断时，把返回值扩展成「找到解的个数」，函数签名不用变，主调方只需换个壳。递归的终止条件有两个：rest 等于 0 说明全部填完，返回 1；某个空格的三掩码交集已经是 0，说明该格无任何可填数字，直接返回 0。

static int solve_sudoku(Sudoku *s, int rest) { if (rest == 0) return 1; // 全部填完，找到一组解 int best = pick_best_empty(s); // MRV：选候选数最少的空格 if (best < 0) return 0; // 存在无候选数的空格，剪枝 int idx = s->empties[best].idx; int r = idx / 9, c = idx % 9, b = r / 3 * 3 + c / 3; unsigned short mask = s->row_mask[r] & s->col_mask[c] & s->blk_mask[b]; while (mask) { unsigned short low = mask & -mask; // 取出最低位的 1 int d = __builtin_ctz(low) + 1; // 位编号 + 1 = 数字 mask ^= low; // 该数字试完，移出候选 set_cell(s, r, c, d); if (solve_sudoku(s, rest - 1)) return 1; clear_cell(s, r, c); // 回溯：还原盘面与掩码 } return 0; }

逻辑说明：mask & -mask是经典 lowbit 技巧，-mask 在补码下等于 ~mask + 1，与运算后只保留最低位的 1；__builtin_ctz 返回最低位 1 前面有几个 0，也就是该位在第几位，加 1 就是数字。候选数字按位从小到大枚举，顺序本身不影响结果，剪枝力度由 pick_best_empty 决定。每试一个数字，set_cell 更新盘面和掩码，递归返回失败后 clear_cell 复原，两句一前一后构成标准回溯模板。

参数说明：rest 不通过遍历盘面数空格得到，而是从 empty_cnt 传入并在每层减 1，省掉一次 O(81) 的统计。需要注意 __builtin_ctz 是 GCC/Clang 内建函数，Visual Studio 下要换成 _tzcnt_u32 或自己写位循环；课设答辩环境多半是 Linux + gcc，直接用内建即可。

3.2 pick_best_empty 与向前检查

pick_best_empty 做两件事：一是过滤出还没填的格子，二是找 mask 中 1 的个数最少的格子。如果某个空格 mask 已经是 0 且还没填，说明整个盘面无解，直接返回 -1。这个检查就是典型的向前检查（forward checking）——不需要等到递归深入才发现矛盾，在当前层就能砍掉整棵子树。

static int pick_best_empty(Sudoku *s) { int best = -1, best_cnt = 10; for (int i = 0; i < s->empty_cnt; i++) { int idx = s->empties[i].idx; int r = idx / 9, c = idx % 9, b = r / 3 * 3 + c / 3; unsigned short mask = s->row_mask[r] & s->col_mask[c] & s->blk_mask[b]; s->empties[i].mask = mask; // 缓存，供外层直接取用 if (mask == 0) return -1; int cnt = 0; for (unsigned short m = mask; m; m &= m - 1) cnt++; // 数 1 的个数 if (cnt < best_cnt) { best_cnt = cnt; best = i; } } return best; }

逻辑说明：每层递归线性扫一遍 empties，最坏 O(81)，对课设规模可以接受；想再快可以把 empties 维护成按候选数个数排序的动态数组，配合每次落子只局部调整，但代码长度会翻倍。报告里写「当前实现用线性扫描」反而是更诚实的复杂度分析，评委不会因为你没写平衡树而扣分。

从候选掩码枚举数字有三种常见写法，差异值得写进报告：

3.3 set_cell 与 clear_cell：掩码同步的三处更新

落子和撤销是对称操作。填数字 d 时，在行、列、宫三个掩码里把第 d-1 位清掉；撤销时再置回去。清位用「与上取反」而不是异或：异或隐含「该位一定是 1」的假设，一旦逻辑写错把同一个数字填了两次，异或会把位错误地恢复，排查起来非常痛苦。

static void set_cell(Sudoku *s, int r, int c, int d) { s->grid[r][c] = d; unsigned short bit = (unsigned short)(1u << (d - 1)); s->row_mask[r] &= ~bit; // 第 r 行不能再填 d s->col_mask[c] &= ~bit; // 第 c 列不能再填 d s->blk_mask[r / 3 * 3 + c / 3] &= ~bit; // 所在宫也不能再填 } static void clear_cell(Sudoku *s, int r, int c) { int d = s->grid[r][c]; s->grid[r][c] = 0; unsigned short bit = (unsigned short)(1u << (d - 1)); s->row_mask[r] |= bit; // 恢复该数字的可用性 s->col_mask[c] |= bit; s->blk_mask[r / 3 * 3 + c / 3] |= bit; }

参数说明：set_cell 的 d 取值 1～9，bit 是对应的掩码位；clear_cell 从 grid 里读回 d，所以调用顺序必须是「先 set 后 clear」配对。课设里一个典型 bug 是有人直接对 grid[r][c] 赋值而不维护掩码，结果 mask 与盘面不一致，回溯到中间层时候选交集错误，表现为「解出来有重复数字」或「某个空格明明能填却报无解」。调试时在 pick_best_empty 入口加断言assert(s->grid[r][c] == 0)能快速定位这类问题。

3.4 多解判断：把返回值改成计数

加分项之一是判断题目是否有唯一解。把 solve_sudoku 的返回从「找到即停」改成「继续找第二个解」，就得到计数版本：

static int count_solutions(Sudoku *s, int rest, int limit) { if (rest == 0) return 1; // 找到一组解 int total = 0; int best = pick_best_empty(s); if (best < 0) return 0; int idx = s->empties[best].idx; int r = idx / 9, c = idx % 9; unsigned short mask = s->row_mask[r] & s->col_mask[c] & s->blk_mask[r / 3 * 3 + c / 3]; while (mask) { unsigned short low = mask & -mask; int d = __builtin_ctz(low) + 1; mask ^= low; set_cell(s, r, c, d); total += count_solutions(s, rest - 1, limit); clear_cell(s, r, c); if (total >= limit) break; // 达到限额提前返回，剪掉剩余分支 } return total; }

逻辑说明：limit 传 2 时，返回值 0、1、2 分别对应无解、唯一解、多解。普通题目只需要输出一组合法解，用 3.1 的版本；判断唯一性时用计数版本。两段代码可以在报告里放同一小节，体现「一个模板两种用途」，这也是数据结构课设里「同一问题多种变形解法」的典型素材。

4. 数独课设的完整交付：文件读写、交互菜单与测试

4.1 从文件读盘面：格式约定与错误处理

课设要求交付可运行的源程序，程序一般不能只吃硬编码数组，要能从文件读入题目。常见格式是 9 行、每行 9 个字符，0 或 . 表示空格，1～9 表示给定数字。读取用 fgets 一行行读，不要用 fscanf("%c")，因为 fgets 能顺带检查行长度，能发现「行内不足 9 个字符」这种损坏输入。

int load_puzzle(const char *path, Sudoku *s) { FILE *fp = fopen(path, "r"); if (!fp) { perror(path); // 打印 errno 对应的错误信息 return -1; // 文件打不开 } char line[32]; for (int r = 0; r < 9; r++) { if (!fgets(line, sizeof(line), fp)) { fclose(fp); return -2; // 行数不足 9 行 } if (strlen(line) < 9) { fclose(fp); return -3; // 行内容不足 9 字符 } for (int c = 0; c < 9; c++) { char ch = line[c]; if (ch >= '1' && ch <= '9') set_cell(s, r, c, ch - '0'); // 同步维护三个掩码 else if (ch != '0' && ch != '.' && ch != '*') { fclose(fp); return -4; // 非法字符 } } } fclose(fp); return 0; // 成功 }

参数说明：返回值是错误码而非 void，主函数用 switch 打印对应提示，这个设计在报告的模块接口表里可以直接引用。另一个关键点是初始化顺序：调用者必须先初始化掩码为 0x1FF，再调 load_puzzle，否则 set_cell 里的 &= ~bit 会基于脏数据运算。更稳妥的做法是在 load_puzzle 内部先完成掩码初始化，把 init_sudoku 作为静态函数在前面执行。

4.2 打印盘面与交互菜单

打印要照顾人眼：每 3 行、每 3 列加分隔线，空格用小圆点而不是数字 0 表示，避免和盘面数字混淆。菜单用死循环加 switch，菜单项包括加载题目、求解、手动填数、退出。手动填数模式是顺带实现的加分功能，核心只是读入 r、c、d 后调用 set_cell 并重新打印盘面，复用已有函数不需要新逻辑。

void print_board(const Sudoku *s) { for (int r = 0; r < 9; r++) { if (r % 3 == 0) printf("+-------+-------+-------+\n"); for (int c = 0; c < 9; c++) { if (c % 3 == 0) printf("| "); if (s->grid[r][c] == 0) printf(". "); else printf("%d ", s->grid[r][c]); } printf("|\n"); } printf("+-------+-------+-------+\n"); }

逻辑说明：行循环和列循环里分别判断 r % 3 和 c % 3，输出宫分隔线。打印不关心宫内部的结构差异，所以不需要计算宫号。函数接受 const 指针，避免 324 字节的结构体整体拷贝，同时让编译器有机会做优化。这个函数同时用于解题前和解体后两种状态，是课设里复用度最高的函数之一。

4.3 测试用例与测量方法：无解、多解、空盘都要覆盖

测试不能只拿一两道题跑通就完事。数据结构课设的测试部分，评委看的是有没有验证边界条件。我一般会准备四类用例，最少一个空盘、一个唯一解标准题、一个高难度题、一个无解题。空盘验证算法能自行生成合法解；无解题验证剪枝能快速终止，不会死循环。

时间测量用 clock() 得到的是 CPU 时间而不是墙钟时间，对单线程程序两者差别不大：

clock_t t0 = clock(); int ok = solve_sudoku(&s, s.empty_cnt); double sec = (double)(clock() - t0) / CLOCKS_PER_SEC; printf("result: %s, time: %.3f ms\n", ok ? "found" : "none", sec * 1000);

逻辑说明：clock() 返回处理器时钟滴答数，除以 CLOCKS_PER_SEC 得到秒。测量要放在单次求解的前后，不要在循环外做累计。报告里把这段输出和盘面截图放一起，比文字描述有说服力得多。注意 debug 构建（-g 不优化）和 release 构建（-O2）的时间可能差一个数量级，写报告时注明编译选项，这也是严谨性的体现。

4.4 数据结构实验报告：从需求分析到测试的写法

数据结构的课设报告一般按需求分析、总体设计、详细设计、测试与分析、心得与不足五个部分展开。「详细设计」一节建议用函数接口表而不是大段贴代码——评委扫一眼就能看出模块划分是否清晰：

复杂度分析部分写两点就够：时间上界是 O(9^n)，n 为空格数，但 MRV 加向前检查把实际搜索树剪得很小；空间上界是递归深度 O(n) 加上常量级掩码数组。把「理论上界」和「实际运行时间」分开写，比只抄一句 O(9^81) 更站得住脚。源程序本身建议拆成三个文件：sudoku.h 放结构体与函数声明，sudoku.c 放求解与打印实现，main.c 放菜单和文件读写入口，头文件加 include guard，这份工程组织在答辩时也经得起问。

5. 进阶优化与答辩自检：唯一解验证、计时跑批和掩码调试

5.1 验证解的合法性：三个掩码全零就够了

很多课设把「校验解是否正确」写成三重循环重新检查行列和，其实不需要。如果盘面填满 81 格且三个掩码全部为 0，意味着每行、每列、每宫都恰好用掉了 1～9 各一次，这个解自动满足数独的全部约束。把这条不变量写进报告，比重复遍历三个方向的校验代码更能体现对位掩码结构的理解。

int check_finished(const Sudoku *s) { for (int i = 0; i < 9; i++) if (s->row_mask[i] || s->col_mask[i] || s->blk_mask[i]) return 0; return 1; }

参数说明：三个掩码联合判定是充分条件——掩码非 0 说明该行或该列或该宫还有数字没用掉，但总数固定是 81 且每格填 1～9，某处缺失必然在另一处造成重复。多解判断也能复用 3.4 的 count_solutions(s, s.empty_cnt, 2)，返回 2 说明题目本身不严谨，答辩时现场换题先跑唯一性再跑求解，比直接刷结果更有说服力。

5.2 统一计时跑批：测试结果直接进报告

手动一个个运行用例既慢又不好截图。把测试写成统一跑批函数，一次性打印所有用例的名字、解的性质和耗时，这个输出就能直接作为报告测试章节的素材。跑批函数最需要注意的就是每轮先重新初始化结构体，避免上一题的掩码残留污染下一题。

static void run_case(const char *name, const char *path) { Sudoku s; init_sudoku(&s); // 掩码全部置 0x1FF if (load_puzzle(path, &s) != 0) { printf("%-16s load failed\n", name); return; } clock_t t0 = clock(); int cnt = count_solutions(&s, s.empty_cnt, 2); double ms = (double)(clock() - t0) * 1000.0 / CLOCKS_PER_SEC; printf("%-16s %-12s %.3f ms\n", name, cnt == 0 ? "no solution" : (cnt == 1 ? "unique" : "multi"), ms); }

逻辑说明：run_case 先初始化，再加载，再计数求解，一次调用输出完整结果。count_solutions 带了 limit 参数，多解题目找到第二个解就会提前返回，不会把全部解枚举完，这也是「满足需求即可」的复杂度控制思路。

5.3 答辩现场必被追问的三个问题

第一个是 MRV 为什么能加速：填候选数少的格子会让矛盾更早暴露，搜索树深度不变但剪枝发生的位置更靠上，被砍掉的子树更大。第二个是掩码怎么同步：set_cell 用 &= ~bit 清位，clear_cell 用 |= bit 恢复，两者必须成对出现，且只更新当前格子所在的行、列、宫三处。第三个是复杂度上界：最坏 O(9^n)，但配合 popcount 预置表和 lowbit 枚举，实际运行时间远低于理论上界，现场拿无解用例演示毫秒级返回最有说服力。

调试阶段建议用 gcc -Wall -Wextra -g 编译，把告警清零后再谈功能；valgrind --leak-check=full 扫一遍确认没有越界和泄漏。配合 VSCode 配好的 C/C++ 调试环境，在 set_cell 下断点观察三个掩码的前后变化，比 printf 堆输出高一个档次。把 run_case 的输出保存成文本文件，连同盘面截图一起放进报告的测试章节，答辩时直接翻这一页讲时间对比，比现场敲键盘稳得多。

本文还有配套的精品资源，点击获取