DiBS：扩散模型引导的分支选择
针对数独求解中学习型求解器缺乏正确性保证、符号求解器易陷入长尾搜索的问题，研究人员提出了一种扩散模型引导的分支选择方法DiBS。该方法在保持符号求解器完备性的同时，利用扩散模型对候选值进行排序，显著降低了搜索成本。在Royle 17线索数独基准测试上，DiBS减少了节点数、回溯次数和长尾百分位，证明了全局学习引导在困难实例上的有效性。
数独是一种经典的约束满足问题，要求求解器在严格的离散约束下进行全局结构推理。目前主流方法分为两类：传统启发式算法和深度学习求解器。然而，两者各有缺陷：学习型求解器虽然速度快，但无法保证输出结果的正确性，可能给出错误答案；而完备的符号求解器虽然能保证正确性，但在处理复杂实例时容易陷入长尾搜索，即大部分求解时间花费在少数极端困难的搜索分支上。这种互补性局限严重制约了数独求解的效率和可靠性。
为了解决这一矛盾，来自多所机构的研究人员提出了一种名为DiBS（Diffusion-Informed Branch Selection）的创新方法。其核心思想是将符号求解器的完备性与扩散模型的引导能力有机融合。具体来说，DiBS保持符号求解器的完整搜索框架，但利用扩散模型作为分支排序的智能指南。在每一步部分赋值中，DiBS通过轻量级的一致性信号对候选值进行排序，从而优先探索最有希望的分支，避免在错误方向上浪费计算资源。
研究团队不仅提出了方法，还提供了深入的理论证明，揭示了扩散模型为何能有效指导分支选择的内在机理。在极具挑战性的Royle 17线索数独基准测试上，实验结果表明，DiBS相比强启发式基线显著降低了搜索成本，尤其是在节点数、回溯次数和长尾百分位等关键指标上表现突出。这些结果有力地证实了，在分支顺序错误代价极高的困难实例上，学习到的全局指导具有显著优势。
此外，研究团队已将DiBS的全部代码在GitHub上开源，为后续研究提供了坚实的基础。这项工作不仅为数独求解开辟了新路径，也为其他约束满足问题中融合符号推理与神经网络技术提供了重要参考，有望推动人工智能在组合优化领域的进一步发展。