🔁 回溯搜索
最直接的解法:给空格逐个试数字,冲突就退回来换下一个——穷举+剪枝。配合「候选最少格子优先」(MRV 启发式),普通盘毫秒级解完。约束满足问题
🕸 精确覆盖 × 舞蹈链
数独可以改写成精确覆盖问题:729 个「行候选」(格 i 填 d),要覆盖 324 个约束列(81 格各填一数+81 行各含 1–9+81 列各含 1–9+81 宫各含 1–9)。Knuth 的舞蹈链 DLX(Algorithm X,2000)在双向十字链表上优雅地「盖上/揭开」行列,是公认最快的通用数独求解器。Algorithm X
⛏ 挖洞出题(本工坊的做法)
①用带随机性的回溯生成一张完整解盘;②把格子(按对称位置成对)逐个挖空;③每挖一格就用求解器数解 ≤ 2 早停,一旦多解立即回填——保证每一题唯一解。4×4 启蒙盘与 9×9 标准盘用的是同一套引擎。唯一解保证
📏 难度怎么定
专业定难度不只数提示,而是评估人类解题技巧链:唯一余数 → 隐性唯一 → 区块摒除 → 数对/三链数 → X-Wing……需要动用越深的技巧,题越难。本工坊用「提示数+挖洞成功率」双标准分五档。
🔢 有多少个盘面
标准数独完整盘共 6,670,903,752,021,072,936,960 个(Felgenhauer & Jarvis 2005);把旋转、反射、换数字等视为等价后,本质不同只有 5,472,730,538 个(Russell & Jarvis 2006)。4×4 数独只有 288 个完整盘——小朋友也能穷举一遍,正好体会「搜索」的含义。
🪨 17 提示之墙
已发现约 5 万个 17 提示唯一解盘,而 McGuire 等(2012,约 700 万核时)证明 16 提示必无唯一解——17 就是这堵墙。顺带一提:广义 n²×n² 数独的求解是 NP 完全问题(Yato & Seta 2003)。