几年前一个周五的下午，我在地铁上刷到一张号称“地狱难度”的数独题，手推了二十多分钟，最后发现自己连唯一解在哪条分支上都没找对。那一刻我就在想，与其和一道题死磕，不如写段代码把整类问题自动化。于是就有了这个用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]还是vector<vector<int>>？
我的建议是，这类固定大小的小型棋盘，直接用C风格静态二维数组就对了。原因很简单：9x9总共81个元素，栈上分配一个int[9][9]只占324字节，完全不需要动态内存管理。而vector<vector<int>>虽然写起来更“现代”，但每一行是一个独立的堆分配对象，访问时多一层间接寻址，代码里还得时刻注意边界检查和迭代器问题，既啰嗦又没性能优势。
更重要的是，在递归回溯过程中，棋盘会被反复修改和还原。静态数组的栈上布局对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：优先处理候选数最少的格子
于是我在第二版加上了MRV（Minimum 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或并行化的文章。
在写这个项目的实际过程中，我体会到的最深一点是：优化的价值不在于把代码写得多花哨，而在于每一次改动之前，都先找到当前版本真正的性能瓶颈。第一版慢，不是因为它用了布尔数组，而是因为缺少启发式；第二版快了一个数量级，不是因为它引入了什么高级算法，只是因为改变了搜索顺序；第三版再快一个数量级，是因为把频繁调用的检查函数压缩成了几条位运算。每一步都踩在上一步的瓶颈上，而不是盲目堆砌技巧。希望这篇记录能给想做类似练手项目的你一个足够清晰的参考路径。
