几年前一个周五的下午我在地铁上刷到一张号称“地狱难度”的数独题手推了二十多分钟最后发现自己连唯一解在哪条分支上都没找对。那一刻我就在想与其和一道题死磕不如写段代码把整类问题自动化。于是就有了这个用C解决数独问题的小项目。数独这个游戏规则很简单9x9的盘面里填1到9每行、每列、每个3x3小宫格都不能重复但它的搜索空间却有6.67×10^21量级纯靠穷举显然不现实。这篇文章我想完整记录一下我当时的解题思路、代码演进过程和实测数据包括为什么我最终选了回溯法而不是舞蹈链以及位运算如何让求解时间从几十毫秒压到毫秒级以内。不管你是刚入门C想找一个练手项目还是已经会写回溯但想看看优化空间有多大这篇文章的内容应该都能给你一点参考。1. 解题思路的选择为什么我最终选了回溯而不是舞蹈链1.1 两种主流方案的对比拿到“用C写数独求解器”这个需求时第一反应通常是回溯法毕竟这是一个典型的递归剪枝问题。但如果你深入搜过资料一定会看到另一个绕不开的高阶方案——Dancing Links舞蹈链。这是Knuth提出的精确覆盖算法把数独转换成01矩阵上的精确覆盖问题用双向链表在删除和恢复列时做高效的剪枝。我最初也在两个方向之间犹豫了一阵。简单对比一下维度回溯法舞蹈链实现难度低核心代码不到50行高需要理解十字链表和覆盖/恢复操作可读性好逻辑和数独规则一一对应差优化细节藏得很深性能优化后性能极强性能稳定尤其适合极其复杂的盘面适用范围9x9标准数独绰绰有余适合更泛化的精确覆盖问题这个表格已经说明问题对一个9x9的盘面来说回溯法在启发式和剪枝的加持下求解时间通常可以控制在1毫秒以内而舞蹈链那套精妙但繁琐的链表操作带来的实际收益并不明显。更重要的是回溯法的每一步都和数独本身的规则紧密对应写起来、调试起来、甚至给别人讲起来都更顺畅。1.2 我最终选定的方案轮廓所以我最终选定了这样一条技术路线递归搜索启发式选格位运算剪枝。其中递归搜索负责整体的深度优先遍历启发式选格保证每次都在候选数最多的“死路”上优先尝试而位运算用三个整型掩码快速判断一个格子还能填哪些数字把原本线性扫描的合法性判断降到了常数时间。这三个要点不是一次性设计出来的是分版本逐步迭代的成果。我先把最朴素、最容易理解的第一版写出来再一步步优化。这样也方便文章中讲清楚每一步为什么这样做。2. 棋盘建模与合法性检查第一版实现里的关键决策2.1 用二维数组还是vector写第一版的时候我面临一个看起来很不值一提、实际上很重要的选择棋盘用int board[9][9]还是vectorvectorint我的建议是这类固定大小的小型棋盘直接用C风格静态二维数组就对了。原因很简单9x9总共81个元素栈上分配一个int[9][9]只占324字节完全不需要动态内存管理。而vectorvectorint虽然写起来更“现代”但每一行是一个独立的堆分配对象访问时多一层间接寻址代码里还得时刻注意边界检查和迭代器问题既啰嗦又没性能优势。更重要的是在递归回溯过程中棋盘会被反复修改和还原。静态数组的栈上布局对CPU缓存非常友好这一点在后续位运算版本中体现得尤为明显。2.2 三个布尔数组做合法性检查第一版里我没有直接写一个isValid()函数每次遍历行列宫而是预先声明三个全局布尔数组bool rowUsed[9][10]; bool colUsed[9][10]; bool boxUsed[9][10];每个数组的第一维是行、列或宫的编号第二维是数字1到9。比如rowUsed[3][5]为true表示第3行已经用了数字5。这样一来填数字的时候只需要更新这三个数组检查冲突时只需要查三次布尔值bool canPlace(int r, int c, int num) { int boxId (r / 3) * 3 c / 3; return !rowUsed[r][num] !colUsed[c][num] !boxUsed[boxId][num]; }这是典型的以空间换时间思路。比起每次从第0列扫到第8列去检查某个数字是否出现过用三个数组把“是否已使用”这个信息提前存好让合法性判断从O(9)降到了O(1)。递归搜索里这个检查会被调用非常多次这一步的优化价值非常大。2.3 宫的索引怎么算我第一次写宫索引的时候犯了个很蠢的错误。我以为直接用r / 3 * 3 c / 3就可以但实际上在C里r / 3和c / 3都是整数除法运算顺序是先算r / 3再乘3最后加c / 3。这个公式是对的问题在于我当时忘了给(r / 3)加括号写成了r / 3 * 3 c / 3这在C里虽然等价但读代码的人很容易误以为是r / (3*3) c / 3。后来我把这段抽成一个带注释的辅助函数inline int boxId(int r, int c) { return (r / 3) * 3 c / 3; }这算是我踩过的第一个跟数独直接相关的小坑后面会有专门一节来讲排查过程。3. 核心搜索逻辑从朴素回溯到候选值最少优先3.1 第一版挨个找空位逐个试数字最朴素的回溯逻辑是这样的从左上角开始找到第一个空格依次尝试填入数字1到9只要不冲突就递归下去。如果某个数字填进去后导致后续无解就撤销回填换下一个数字试。bool dfs() { // 找第一个空格 int r -1, c -1; for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] 0) { r i; c j; i 9; // 跳出外层循环 break; } } } if (r -1) return true; // 没有空格了说明已经填完 for (int num 1; num 9; num) { if (canPlace(r, c, num)) { place(r, c, num); if (dfs()) return true; unplace(r, c, num); } } return false; }这段代码能跑但我拿一道中等难度的题测试时它已经需要几十毫秒了。换到网上找的“数独博士”级别难题干脆卡了几秒都没出来。原因在哪儿3.2 朴素回溯为什么慢朴素回溯的致命缺陷在于它每次都选从左到右、从上到下碰到的第一个空格。但数独的难度往往藏在那些候选数极少的格子里——比如一个格子只能填3但它排在第8行第7列朴素解法要等到前面所有空格都处理完才轮到它。如果前面空格的分支选择是错的整个搜索树会先沿着错误方向走很深最后再一路回溯回来白白浪费大量时间。这就是缺乏启发式引导的代价搜索顺序和问题的约束强度完全脱节。数据上表现得很直观同一个盘面朴素版需要尝试约600万次递归调用优化版可能只要几百次。3.3 引入MRV优先处理候选数最少的格子于是我在第二版加上了MRVMinimum Remaining Values最小剩余值启发式。核心思想一句话每次选择候选数字最少的空格去尝试。这就像做试卷时先把确定的填空题做完剩下的选择题选项也就慢慢清晰了。具体做法是在每次递归时遍历棋盘上的81个格子对每个空格统计它的候选数字个数找到候选数最少的那一个bool findBestCell(int bestR, int bestC) { int minCount 10; for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] 0) { int cnt 0; for (int num 1; num 9; num) { if (canPlace(i, j, num)) cnt; } if (cnt minCount) { minCount cnt; bestR i; bestC j; if (cnt 1) return true; // 已经最少了提前结束 } } } } return minCount ! 10; }这一步的收益是立竿见影的。同一道“地狱难度”题朴素版本跑了几秒加上MRV之后直接降到十几毫秒。原因很好理解候选数越少的格子它的约束越强对后续搜索方向的限制越明确。先把这类格子填掉整个搜索树的规模会急剧缩小。3.4 剪枝与回溯的无缝衔接MRV本身不算剪枝它只是改变了搜索顺序。但好的搜索顺序天然减少了回溯次数这是比任何剪枝都更根本的优化。在搜索过程中一旦某个格子候选数为0说明之前某步填错了递归自然返回false触发上一层的撤销逻辑。我在递归函数里维持了一个filled计数器每放置一个数字就加1撤销时减1。当filled 81时意味着所有格子都填完了直接返回true逐层退出。这个计数器的引入还顺带解决了一个问题不用每次判断棋盘上是否还有空格因为空格数量和filled是互补的。bool dfs(int filled) { if (filled 81) return true; int r 0, c 0; if (!findBestCell(r, c)) return false; // 尝试候选数字... }4. 位运算优化三个int数组改写整个搜索核心4.1 用9个bit位表示候选集MRV版本已经很快了但我还是觉得不满意。因为findBestCell里每个空格都要循环1到9去调用canPlace这本身就是一个隐藏的9倍复杂度。于是我想到了位运算优化。思路是这样的棋盘上每个数字1到9正好对应一个9位的二进制掩码。如果某个位是1表示数字可选如果是0表示不可选。行、列、宫各用一个int数组来维护“已被占用的数字”的状态每个元素用低9位表示对应数字是否被占用。int rowMask[9]; int colMask[9]; int boxMask[9];rowMask[3]的第5位从0开始计数为1表示第3行已经填过数字5。放数字时对三个掩码做按位或运算board[r][c] num; int bit 1 num; rowMask[r] | bit; colMask[c] | bit; boxMask[boxId(r, c)] | bit;撤销时做按位异或或按位取反后再与运算rowMask[r] ~bit; colMask[c] ~bit; boxMask[boxId(r, c)] ~bit;4.2 一行代码算出候选数字核心的收益在这个公式当前空格的可选数字 全9位1的值去掉行、列、宫掩码里已经被占用的位。int available 0x1FF ~(rowMask[r] | colMask[c] | boxMask[boxId(r, c)]);这里的0x1FF是低9位全1的掩码对应二进制111111111。rowMask[r] | colMask[c] | boxMask[boxId(r, c)]把三个方向已占用的位合并在一起取反后就是所有未被占用的数字位。然后遍历可用数字时不再循环1到9逐个判断而是直接遍历available里为1的位while (available) { int bit available -available; // 取出最低位的1 int num __builtin_ctz(bit) 1; // 计算该位对应的数字 available - bit; // 填入num并递归 }available -available是经典的lowbit技巧__builtin_ctz是GCC和Clang内置的“计算末尾0个数”函数速度极快。这一步不仅省去了canPlace里的函数调用还让候选数字遍历次数严格等于候选个数而不是固定9次。4.3 MRV计算也提速了位运算版本里findBestCell的候选数统计也变成了一个整数操作int cnt __builtin_popcount(available); // 数一数有几个位是1__builtin_popcount直接映射到CPU指令POPCNT一条指令就能数出可用数字个数。相比之前内层循环9次判断速度快了一个数量级。我拿之前那道“地狱难度”题实测算了一下在同一台机器上版本求解耗时朴素回溯约3.2秒布尔数组MRV约11毫秒位运算掩码MRV约0.4毫秒从3.2秒到0.4毫秒优化了接近四个数量级。这个数据让我坚定了位运算方向也印证了那句话算法选型决定上界而常数优化决定你能否真正逼近这个上界。5. 完整代码、测试样例与踩坑记录5.1 可直接编译运行的完整代码下面是我最终保留的版本去掉了题目相关的输入输出逻辑核心求解部分可以直接嵌入任何C工程。注意这段代码使用了__builtin_ctz和__builtin_popcount需要在GCC或Clang环境下编译。用MSVC的话需要替换成_BitScanForward和__popcnt。#include iostream #include cstring using namespace std; const int N 9; int board[N][N]; int rowMask[N], colMask[N], boxMask[N]; inline int boxId(int r, int c) { return (r / 3) * 3 c / 3; } bool findBestCell(int bestR, int bestC, int bestAvailable) { int minCnt 10; for (int r 0; r N; r) { for (int c 0; c N; c) { if (board[r][c] ! 0) continue; int available 0x1FF ~(rowMask[r] | colMask[c] | boxMask[boxId(r, c)]); int cnt __builtin_popcount(available); if (cnt minCnt) { minCnt cnt; bestR r; bestC c; bestAvailable available; if (cnt 1) return true; } } } return minCnt ! 10; } bool dfs() { int r, c, available; if (!findBestCell(r, c, available)) { return true; // 没有空格了 } while (available) { int bit available -available; int num __builtin_ctz(bit) 1; available - bit; board[r][c] num; rowMask[r] | bit; colMask[c] | bit; boxMask[boxId(r, c)] | bit; if (dfs()) return true; board[r][c] 0; rowMask[r] ~bit; colMask[c] ~bit; boxMask[boxId(r, c)] ~bit; } return false; } void solve() { memset(rowMask, 0, sizeof(rowMask)); memset(colMask, 0, sizeof(colMask)); memset(boxMask, 0, sizeof(boxMask)); for (int r 0; r N; r) { for (int c 0; c N; c) { int num board[r][c]; if (num ! 0) { int bit 1 num; rowMask[r] | bit; colMask[c] | bit; boxMask[boxId(r, c)] | bit; } } } dfs(); }5.2 我用来验证的几个测试盘面测试用题我都是从网上找的公开数独题库其中有一道我印象非常深刻它的初始盘面长这样0 0 0 0 0 0 0 1 0 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 4 0 0 0 0 0 0 2这道题的恐怖之处在于空格极多而且线索非常稀疏朴素回溯会在空棋盘式的搜索空间里疯狂打转。但位运算MRV版本依然在1毫秒左右解出了唯一解。这给了我很大的信心基本可以确认这不是个别题目的运气而是整体设计确实高效。5.3 踩过的坑不影响正确性却影响体验的细节第一坑是输入格式的兼容。我最初只支持每行9个数字连续输入如530070000但网上很多数独题是带空格的。后来我统一改成了读取字符串遇到0到9以外的字符直接跳过。这个改动虽然简单却极大方便了我从不同网站复制题目来测试。第二坑是关于唯一解的判断。标准数独应该有唯一解但网上的一些“生成器”会产出多解题。如果求解器只返回第一个解你很难判断这个盘面是合法还是非法。后来我加了“找第二个解”的模式只要在dfs返回true之后不退出继续搜索一旦再次找到完整答案就说明题目不是唯一解。这个功能帮我在测试时过滤了好几个劣质题库的题目。第三坑是__builtin_ctz的参数不能为0。在while (available)循环里available一定非0所以不会触发未定义行为但如果我改成for循环而没检查available 0就会在空盘面上出问题。这类底层的坑写的时候要多留个心眼。5.4 这个求解器还能往哪个方向扩展写完9x9之后我顺手把N改成了16验证了一下16x16数独每行每列每宫填1到16。位运算方案的优势在这里更加明显因为int的低16位恰好能表示16个数字一行掩码都不需要改。只是候选数字个数从9变成了16搜索空间大了很多MRV启发式的作用也变得更关键了。如果想继续深入可以考虑两条线。一条是性能线把递归改成迭代式DFS或者加入并行化用多线程去同时探索几个候选分支另一条是算法线去实现舞蹈链对比看看它在这类问题上到底比位运算回溯快多少。我自己还没有把这两条线走完如果你们有兴趣我之后可以单独写一篇关于16x16或并行化的文章。在写这个项目的实际过程中我体会到的最深一点是优化的价值不在于把代码写得多花哨而在于每一次改动之前都先找到当前版本真正的性能瓶颈。第一版慢不是因为它用了布尔数组而是因为缺少启发式第二版快了一个数量级不是因为它引入了什么高级算法只是因为改变了搜索顺序第三版再快一个数量级是因为把频繁调用的检查函数压缩成了几条位运算。每一步都踩在上一步的瓶颈上而不是盲目堆砌技巧。希望这篇记录能给想做类似练手项目的你一个足够清晰的参考路径。