前言
数独（Sudoku）问题很适合当作算法与 C++ 语言特性的综合练习：问题规模小到可以在一瞬间求解，规则又足够结构化，能清楚地看到"建模—剪枝—搜索"这条主线。它的标准形式是一个 9×9 的格子，要求每行、每列、每个 3×3 宫（box）内都恰好出现一次数字 1 到 9。
初学者最常见的做法是"每个空格都从 1 试到 9，检查合法性，不合法就换下一个"，这个思路是对的，但有两个地方会拖慢程序：一是每次都重新扫描整行整列来判断数字能不能填，二是随便挑一个空格开始试。前者可以把行、列、宫的"已用数字"压缩成三个位掩码（bitmask）来避免重复扫描；后者可以用"最少候选优先"的启发式大幅减少回溯次数。
本文先给出问题的精确建模，再写一个朴素回溯版本说明思路，然后加上位掩码与候选数启发式，最后给出一份完整可编译的程序与它的输出。本文不给出任何运行耗时数据——那取决于机器、编译器与优化选项，需要的话请自己在本地用std::chrono测。文中所有代码以 C++17 为基准，在 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/3 |
cell[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 说明当前分支必然无解，可以立即剪枝返回；候选数最少的格子通常最容易确定，能让搜索树更窄。这个启发式在约束满足问题里通常叫 MRV（minimum 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 的个数，C++17 里没有标准设施，需要自己写。最省事的写法是经典的x & (x - 1)去掉最低位的 1，循环计数：
static int popcount(std::uint16_t x) { int n = 0; while (x) { x = static_cast<std::uint16_t>(x & (x - 1)); ++n; } return n; }C++20 起可以直接用std::popcount（声明在<bit>中），编译器通常能把它映射到一条硬件指令；C++17 项目就用上面这个手写版本，或者如果确认编译器支持内建函数（GCC/Clang 的__builtin_popcount、MSVC 的__popcnt）也可以用它，但那属于编译器扩展，不是标准。
四、完整可编译的程序
下面这份代码把上面几节合在一起，是一个完整、可直接复制编译的程序。
// 文件 sudoku.cpp，需要 C++17 // 编译：g++ -std=c++17 -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::array<int, N>; using Grid = std::array<Row, N>; // 从 9 行文本载入题目：'1'~'9' 为已知数字，'.' 或 '0' 为空格 bool load(const std::array<std::string, N>& rows) { for (int r = 0; r < N; ++r) { if (rows[static_cast<std::size_t>(r)].size() != static_cast<std::size_t>(N)) { return false; } for (int c = 0; c < N; ++c) { const char ch = rows[static_cast<std::size_t>(r)][static_cast<std::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_cast<std::uint16_t>(1u << (d - 1)); } static int popcount(std::uint16_t x) { int n = 0; while (x) { x = static_cast<std::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_cast<std::uint16_t>(rowMask_[r] | bit); colMask_[c] = static_cast<std::uint16_t>(colMask_[c] | bit); boxMask_[box(r, c)] = static_cast<std::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_cast<std::uint16_t>(rowMask_[r] | bit); colMask_[c] = static_cast<std::uint16_t>(colMask_[c] | bit); boxMask_[box(r, c)] = static_cast<std::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_cast<std::uint16_t>(rowMask_[r] & ~bit); colMask_[c] = static_cast<std::uint16_t>(colMask_[c] & ~bit); boxMask_[box(r, c)] = static_cast<std::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_cast<std::uint16_t>( rowMask_[r] | colMask_[c] | boxMask_[box(r, c)]); const std::uint16_t avail = static_cast<std::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::array<int,N> 保存 uint16_t 掩码 Row colMask_{}; Row boxMask_{}; bool masksReady_ = false; }; int main() { const std::array<std::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::array<int, 9>保存，每次运算都显式static_cast到std::uint16_t。这样做是为了避免整型提升带来的隐式截断警告（-Wconversion下很常见）；如果嫌啰嗦，也可以直接用std::array<std::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_cast<std::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 这类技巧求解，那是另一个方向的优化了。
