DiBS：扩散模型引导数独求解，大幅减少搜索回溯
近日，一篇题为 《DiBS: Diffusion-Informed Branch Selection》 的论文在 arXiv 上公开，提出了一种将扩散模型与传统符号求解器相结合的新方法，专门用于解决数独这类约束满足问题（CSP）。该研究由来自中国多所机构的研究人员完成，相关代码已开源。
研究背景：学习与推理的鸿沟
数独是 CSP 的经典代表，要求求解器在严格离散约束下进行全局结构推理。现有方法主要分为两类：
- 传统启发式搜索：如回溯法、约束传播，能保证解的完全正确性，但在困难实例上容易出现长尾搜索，即大部分时间花在极少数复杂分支上。
- 深度学习求解器：通过神经网络直接预测答案或指导搜索，速度快但缺乏硬正确性保证，无法确保最终解绝对合法。
两者的优缺点恰好互补，但鲜有研究能将它们的优势有机结合。
DiBS 核心思路：用扩散模型“排雷”
DiBS（Diffusion-Informed Branch Selection）的核心理念是 保持符号求解器的完全性，同时利用扩散模型作为分支排序的指导。具体来说：
- 符号求解器：负责执行完整的回溯搜索，确保一旦找到解，其正确性有严格数学保证。
- 扩散模型：在每次需要选择下一个要填的数字时，根据当前部分赋值和轻量级一致性信号，对候选值进行排序，优先推荐最可能正确的分支。
这种设计并非用模型替代求解器，而是让模型扮演“顾问”角色，帮助求解器优先探索最有希望的分支，从而减少无效回溯。
论文还提供了理论证明，解释了扩散模型为何能有效指导分支选择：它通过去噪过程学习到了数独的全局结构模式，从而在早期阶段就能排除大量错误路径。
实验结果：搜索成本显著降低
研究者在 Royle 17-clue 数独基准（包含大量仅含 17 个提示数的困难实例）上进行了测试，与多种强启发式基线（如最小剩余值 MRV 策略）对比。结果显示：
- 搜索节点数：平均减少约 40%
- 回溯次数：下降幅度超过 50%
- 长尾百分位：最坏情况下的搜索深度显著缩短，说明模型对困难实例尤其有效
这些数据表明，DiBS 成功地将学习到的全局指导转化为搜索效率的提升，且不会牺牲正确性。
行业意义：约束求解与深度学习的融合新范式
DiBS 的价值不仅在于数独本身。约束满足问题 在调度、规划、资源分配、硬件验证等领域广泛存在。传统符号方法虽精确但效率瓶颈明显，而纯学习模型又难以保证 100% 正确。DiBS 提供了一种可复用的混合框架：
- 保持符号求解器的完整性，满足工业级可靠性要求；
- 利用生成式模型的模式识别能力，加速搜索过程。
这一思路与近年来 “神经符号系统” 的趋势一致，即结合神经网络的感知能力和符号系统的推理能力。DiBS 的成功进一步验证了扩散模型在离散推理任务中的潜力，未来或可推广至更复杂的 CSP（如数独变体、图着色、SAT 问题等）。
小结
DiBS 通过一个简洁而优雅的设计——将扩散模型作为分支排序器集成到回溯搜索中——在保证完全性的前提下显著提升了求解效率。它不仅是数独求解领域的进步，更为约束满足问题的混合求解策略提供了新的参考方向。