数独求解器设计与实现：位掩码、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 二维数组值域 190 表示空格。有些课设为了省内存选 char 类型其实没必要整个问题规模就是 81 个格子任何类型都远小于缓存行内存不是瓶颈代码可读性才是。int 配合 printf(%d) 直接输出和 scanf 交互时不用处理 char 的符号问题出 bug 的概率更低。这个「选 int 不选 char」的理由本身就可以写进报告的数据结构论证小节。如果在意局部性可以用一维数组 grid[81]r 行 c 列映射到 idx r*9 c。对 9×9 这种规模二维和一维几乎没有性能差异但一维数组在空格列表场景下更顺手空格的 idx 直接等于它在数组里的下标回溯时不需要同时维护 (r, c) 两个字段。课设代码里可以两种混用——结构体存二维数组方便打印空格列表存 idx 方便排序换算只差一句除法。存储方案空间占用编写直观度适用环节char grid[9][9]81 B较高但 %c 读写要处理空白字符演示盘面打印int grid[9][9]324 B最高建议采用回溯主体、打印int grid[81]324 B中等搭 idx 映射空格列表、位掩码场景2.2 用三个位掩码维护行、列、宫的候选数教科书写法一般开三个 bool 数组比如 valid_row[9][10]第 k 位表示数字 k 是否可用。这种写法直观但回溯时要同时维护三张表每填一个数要置三个标记代码分散且容易漏更新。更紧凑的做法是位掩码每行、每列、每宫各用一个 unsigned shortbit k 对应数字 k1 是否可用数字 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 上做不再回盘面里数一遍已有值。相比逐个试 19 再查三张表交集写法把「判定」和「枚举」合并了。提示unsigned short 只有 16 位存 19 的掩码绰绰有余用 int 也可以但报告里写清「为什么够用」本身就是一个小得分点。2.3 空格列表与候选数预排序MRV 的基础回溯的搜索空间是空格的全排列空格处理顺序直接影响剪枝效果。常见做法是读入盘面后把所有空格收集成数组每个元素记 idx 和候选数个数。初始阶段就按候选数个数升序排好这就是 MRVMinimum Remaining Values最少剩余值启发式每次递归优先填「可填数字最少」的空格死路会早暴露搜索树会被大幅压缩。候选数个数通过数 mask 里的 1 得到C 语言里最常用的是while (mask) { cnt; mask mask - 1; }每轮清掉最低位的 1。求解器的主体结构体可以这样定义typedef struct { int idx; // 0..80r idx / 9c 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 表示数字 d1 还没出现在第 r 行结构体保存的是「当前递归状态」下的掩码set_cell 和 clear_cell 负责同步。empties 数组每次递归重新计算各空格当前的 mask配合 MRV 做动态选择而不是只在读盘时排一次序——因为随着递归深入每个空格的候选数会持续变化。这个结构体和报告里「详细设计」一节直接对应画函数调用图也方便。初始化时所有掩码位先全置为 1row_mask[i] col_mask[i] blk_mask[i] 0x1FF因为 19 共 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 维护成按候选数个数排序的动态数组配合每次落子只局部调整但代码长度会翻倍。报告里写「当前实现用线性扫描」反而是更诚实的复杂度分析评委不会因为你没写平衡树而扣分。从候选掩码枚举数字有三种常见写法差异值得写进报告写法核心语句平均迭代次数逐个试 19if (mask (1u (d-1)))固定 9 次lowbit ctzlow mask -mask; d ctz(low)1候选数个数次popcount 预置表cnt pc[mask]查表 O(1)枚举仍需迭代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 取值 19bit 是对应的掩码位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 或 . 表示空格19 表示给定数字。读取用 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 测试用例与测量方法无解、多解、空盘都要覆盖测试不能只拿一两道题跑通就完事。数据结构课设的测试部分评委看的是有没有验证边界条件。我一般会准备四类用例最少一个空盘、一个唯一解标准题、一个高难度题、一个无解题。空盘验证算法能自行生成合法解无解题验证剪枝能快速终止不会死循环。用例类型代表输入预期输出空盘81 个 0秒出任意一组合法解标准题每行 56 个给定数唯一解毫秒级高难度题21 个给定数的世界最难数独MRV 下 10ms 量级盲目回溯可能数秒无解题同一行出现两个 5提示无解且不卡死时间测量用 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 数据结构实验报告从需求分析到测试的写法数据结构的课设报告一般按需求分析、总体设计、详细设计、测试与分析、心得与不足五个部分展开。「详细设计」一节建议用函数接口表而不是大段贴代码——评委扫一眼就能看出模块划分是否清晰函数名入参返回值职责load_puzzleconst char*, Sudoku*int 错误码读文件并构建盘面pick_best_emptySudoku*int 下标或 -1MRV 选空格检测死局set_cell / clear_cellSudoku*, r, c, dvoid落子与撤销维护掩码solve_sudokuSudoku*, intint回溯求解主体复杂度分析部分写两点就够时间上界是 O(9^n)n 为空格数但 MRV 加向前检查把实际搜索树剪得很小空间上界是递归深度 O(n) 加上常量级掩码数组。把「理论上界」和「实际运行时间」分开写比只抄一句 O(9^81) 更站得住脚。源程序本身建议拆成三个文件sudoku.h 放结构体与函数声明sudoku.c 放求解与打印实现main.c 放菜单和文件读写入口头文件加 include guard这份工程组织在答辩时也经得起问。5. 进阶优化与答辩自检唯一解验证、计时跑批和掩码调试5.1 验证解的合法性三个掩码全零就够了很多课设把「校验解是否正确」写成三重循环重新检查行列和其实不需要。如果盘面填满 81 格且三个掩码全部为 0意味着每行、每列、每宫都恰好用掉了 19 各一次这个解自动满足数独的全部约束。把这条不变量写进报告比重复遍历三个方向的校验代码更能体现对位掩码结构的理解。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 且每格填 19某处缺失必然在另一处造成重复。多解判断也能复用 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-checkfull 扫一遍确认没有越界和泄漏。配合 VSCode 配好的 C/C 调试环境在 set_cell 下断点观察三个掩码的前后变化比 printf 堆输出高一个档次。把 run_case 的输出保存成文本文件连同盘面截图一起放进报告的测试章节答辩时直接翻这一页讲时间对比比现场敲键盘稳得多。本文还有配套的精品资源点击获取