前言数独Sudoku问题很适合当作算法与 C 语言特性的综合练习问题规模小到可以在一瞬间求解规则又足够结构化能清楚地看到建模—剪枝—搜索这条主线。它的标准形式是一个 9×9 的格子要求每行、每列、每个 3×3 宫box内都恰好出现一次数字 1 到 9。初学者最常见的做法是每个空格都从 1 试到 9检查合法性不合法就换下一个这个思路是对的但有两个地方会拖慢程序一是每次都重新扫描整行整列来判断数字能不能填二是随便挑一个空格开始试。前者可以把行、列、宫的已用数字压缩成三个位掩码bitmask来避免重复扫描后者可以用最少候选优先的启发式大幅减少回溯次数。本文先给出问题的精确建模再写一个朴素回溯版本说明思路然后加上位掩码与候选数启发式最后给出一份完整可编译的程序与它的输出。本文不给出任何运行耗时数据——那取决于机器、编译器与优化选项需要的话请自己在本地用std::chrono测。文中所有代码以 C17 为基准在 GCC 13 / Clang 17 / MSVC 19.3x 下均可编译。一、问题建模约束与状态数独的三条约束可以统一表述为对任意一个格子它的行、列、宫三个集合中都不能已经出现同一个数字。因此当前还剩哪些候选数字可以表示成一个 9 位的掩码记号含义位定义rowMask[r]第 r 行已用数字第 d-1 位为 1 表示数字 d 已用colMask[c]第 c 列已用数字同上boxMask[b]第 b 个 3×3 宫已用数字同上b (r/3)*3 c/3cell[r][c]该格的数字0 表示空格0 到 9用位掩码的关键好处是判断数字 d 能否填在 (r,c)只需要两三次位运算不必再遍历行、列、宫。宫的编号公式(r/3)*3 c/3把 9 个宫从左到右、从上到下依次编号为 0 到 8。状态维护必须成对出现填一个数就把三个掩码的对应位置 1撤销时再清 0。回溯算法能否正确工作几乎全看撤销是否彻底。二、回溯的骨架回溯backtracking的结构非常固定找一个空格枚举它的候选数字对每个候选做三件事——试探、递归、撤销。递归返回真就说明已经解出一路向上返回全部候选都失败则返回假交给上一层继续试。搜索(状态): 若没有空格: 返回 成功 选一个空格 (r, c) 对每个候选数字 d: 执行 落子(r, c, d) 若 搜索(状态) 成功: 返回 成功 执行 撤销(r, c, d) 返回 失败有两个细节决定了这份骨架是否可靠第一选哪个空格。随便选和选候选数最少的差别很大。候选数为 0 说明当前分支必然无解可以立即剪枝返回候选数最少的格子通常最容易确定能让搜索树更窄。这个启发式在约束满足问题里通常叫 MRVminimum remaining values最少剩余取值。第二什么时候判定无解。如果某次扫描发现一个空格一个候选都没有就不必再递归下去了。这个剪枝往往比试到最后才发现矛盾省掉大量节点。三、位掩码与候选枚举把 9 个数字对应到低 9 位1u (d - 1)就是数字 d 的位。整个 1 到 9 的集合就是0x1FF也就是低 9 位全为 1。已用集合used rowMask[r] | colMask[c] | boxMask[b]可用集合avail 0x1FF ~used某个格子剩余候选数avail中 1 的个数枚举候选从 d 1 到 9检查avail的第 d-1 位是否为 1统计二进制中 1 的个数C17 里没有标准设施需要自己写。最省事的写法是经典的x (x - 1)去掉最低位的 1循环计数static int popcount(std::uint16_t x) { int n 0; while (x) { x static_caststd::uint16_t(x (x - 1)); n; } return n; }C20 起可以直接用std::popcount声明在bit中编译器通常能把它映射到一条硬件指令C17 项目就用上面这个手写版本或者如果确认编译器支持内建函数GCC/Clang 的__builtin_popcount、MSVC 的__popcnt也可以用它但那属于编译器扩展不是标准。四、完整可编译的程序下面这份代码把上面几节合在一起是一个完整、可直接复制编译的程序。// 文件 sudoku.cpp需要 C17 // 编译g -stdc17 -O2 -Wall -Wextra sudoku.cpp -o sudoku #include array #include cstdint #include iostream #include ostream #include string class Sudoku { public: static constexpr int N 9; static constexpr std::uint16_t kAllDigits 0x1FF; // 低 9 位全 1 using Row std::arrayint, N; using Grid std::arrayRow, N; // 从 9 行文本载入题目1~9 为已知数字. 或 0 为空格 bool load(const std::arraystd::string, N rows) { for (int r 0; r N; r) { if (rows[static_caststd::size_t(r)].size() ! static_caststd::size_t(N)) { return false; } for (int c 0; c N; c) { const char ch rows[static_caststd::size_t(r)][static_caststd::size_t(c)]; if (ch . || ch 0) { cell_[r][c] 0; } else if (ch 1 ch 9) { cell_[r][c] ch - 0; } else { return false; } } } masksReady_ false; return true; } bool solve() { if (!masksReady_) { if (!buildMasks()) { return false; } // 题目本身有冲突 masksReady_ true; } return search(); } void print(std::ostream os) const { for (int r 0; r N; r) { for (int c 0; c N; c) { os cell_[r][c]; if (c % 3 2 c ! N - 1) { os ; } } os \n; if (r % 3 2 r ! N - 1) { os \n; } } } private: static int box(int r, int c) { return (r / 3) * 3 (c / 3); } static std::uint16_t digitBit(int d) { return static_caststd::uint16_t(1u (d - 1)); } static int popcount(std::uint16_t x) { int n 0; while (x) { x static_caststd::uint16_t(x (x - 1)); n; } return n; } // 依据当前格子重建掩码若题目本身重复则返回 false bool buildMasks() { rowMask_.fill(0); colMask_.fill(0); boxMask_.fill(0); for (int r 0; r N; r) { for (int c 0; c N; c) { const int d cell_[r][c]; if (d 0) { continue; } const std::uint16_t bit digitBit(d); if ((rowMask_[r] bit) || (colMask_[c] bit) || (boxMask_[box(r, c)] bit)) { return false; // 同一数字在同一约束集合里出现两次 } rowMask_[r] static_caststd::uint16_t(rowMask_[r] | bit); colMask_[c] static_caststd::uint16_t(colMask_[c] | bit); boxMask_[box(r, c)] static_caststd::uint16_t(boxMask_[box(r, c)] | bit); } } return true; } void place(int r, int c, int d) { const std::uint16_t bit digitBit(d); cell_[r][c] d; rowMask_[r] static_caststd::uint16_t(rowMask_[r] | bit); colMask_[c] static_caststd::uint16_t(colMask_[c] | bit); boxMask_[box(r, c)] static_caststd::uint16_t(boxMask_[box(r, c)] | bit); } void unplace(int r, int c, int d) { const std::uint16_t bit digitBit(d); cell_[r][c] 0; rowMask_[r] static_caststd::uint16_t(rowMask_[r] ~bit); colMask_[c] static_caststd::uint16_t(colMask_[c] ~bit); boxMask_[box(r, c)] static_caststd::uint16_t(boxMask_[box(r, c)] ~bit); } bool search() { int bestR -1, bestC -1, bestCount 10; std::uint16_t bestAvail 0; for (int r 0; r N; r) { for (int c 0; c N; c) { if (cell_[r][c] ! 0) { continue; } const std::uint16_t used static_caststd::uint16_t( rowMask_[r] | colMask_[c] | boxMask_[box(r, c)]); const std::uint16_t avail static_caststd::uint16_t(kAllDigits ~used); const int count popcount(avail); if (count 0) { return false; } // 立即剪枝 if (count bestCount) { bestCount count; bestR r; bestC c; bestAvail avail; } } } if (bestR -1) { return true; } // 无空格求解完成 for (int d 1; d 9; d) { if ((bestAvail digitBit(d)) 0) { continue; } place(bestR, bestC, d); if (search()) { return true; } unplace(bestR, bestC, d); // 撤销必须彻底 } return false; } Grid cell_{}; Row rowMask_{}; // std::arrayint,N 保存 uint16_t 掩码 Row colMask_{}; Row boxMask_{}; bool masksReady_ false; }; int main() { const std::arraystd::string, Sudoku::N puzzle { 530070000, 600195000, 098000060, 800060003, 400803001, 700020006, 060000280, 000419005, 000080079 }; Sudoku s; if (!s.load(puzzle)) { std::cerr 题目格式错误\n; return 1; } if (!s.solve()) { std::cout 该题目无解\n; return 1; } s.print(std::cout); return 0; }这段代码有一处刻意的取舍掩码数组用std::arrayint, 9保存每次运算都显式static_cast到std::uint16_t。这样做是为了避免整型提升带来的隐式截断警告-Wconversion下很常见如果嫌啰嗦也可以直接用std::arraystd::uint16_t, 9此时rowMask_[r] | bit的结果仍是int赋值回uint16_t时会窄化需要同样的显式转换或放宽警告等级。这道题是广为使用的经典数独题目解是唯一的。程序输出为534 678 912 672 195 348 198 342 567 859 761 423 426 853 791 713 924 856 961 537 284 287 419 635 345 286 179常见坑点❌ 递归返回前忘记撤销unplace导致后续分支看到错误的状态。✅ 把place与unplace写成严格配对的两行中间只夹一次递归调用不要用return search();提前返回而跳过撤销。❌ 用bool used[10]之类的局部数组每次重新扫描行、列、宫。✅ 用位掩码把三者的判断合并成两三次位运算正确性等价扫描次数明显减少。❌ 把1u (d - 1)与~组合时忘记截断得到高位的垃圾位。✅ 参与掩码运算前统一static_caststd::uint16_t(...)或用 0x1FF显式限定宽度。❌ 认为能填就填就够了不做任何剪枝遇到难的题目回溯量爆炸。✅ 至少加上两条候选数为 0 立即返回失败优先选择候选数最少的格子。❌ 不校验输入的合法性遇到本身有矛盾同一行出现两个相同的已知数字的题目时给出奇怪结果。✅ 在buildMasks阶段检测重复并直接返回失败把题目非法和题目无解分开报告。❌ 手工写box(r, c)时写成(r % 3) * 3 (c / 3)。✅ 宫的编号用整除(r / 3) * 3 (c / 3)。写错时程序往往仍能跑出结果只是结果违反了宫的约束——非常隐蔽。❌ 求解函数里修改全局状态却不恢复同时又在多线程里调用。✅ 本文的实现把状态放在对象里本身不是线程安全的要多线程求解就每个线程各持一个Sudoku实例不要共享。❌ 用char存掩码char可能是有符号的移位到第 9 位会出问题。✅ 用std::uint16_t或更宽的无符号类型做位运算。总结关注点朴素写法位掩码 MRV判断能否填数遍历行、列、宫两三次位运算选格子的依据扫描到的第一个空格候选数最少的空格无解检测试到最后才发现候选数为 0 时立即剪枝状态表示9×9 网格网格 三组 9 位掩码撤销恢复网格恢复网格并清位用 C 解数独的价值不在于能不能解出来而在于它把一个完整的算法流程压缩在了很小的代码量里建模掩码→ 剪枝候选数为 0→ 搜索回溯→ 状态还原成对撤销。把这份骨架里的place/unplace换成别的约束操作它就能直接迁移到八皇后、填字游戏、图着色这一整类约束满足问题上。想继续深入的话数独可以形式化为精确覆盖问题用 Algorithm X 或 Dancing Links 这类技巧求解那是另一个方向的优化了。