用扩散模型指导数独求解的分支选择，显著减少搜索开销。
DiBS: Diffusion-Informed Branch Selection
- 用扩散模型对候选值排序，结合一致性信号优化分支顺序。
- 在Royle 17 clues数据集上，节点数、回溯次数和长尾百分位大幅降低。
- 适合需要高可靠性的硬实例求解，尤其适用于分支错误代价高的场景。
数独是一个典型的约束满足问题，需在严格离散约束下进行全局结构推理。现有方法主要分为传统启发式与深度学习求解两类，但均存在互补性局限：基于学习的求解器缺乏硬性正确性保证，而完整的符号求解器仍易陷入长尾搜索。为此，本文提出一种新型扩散模型引导的分支选择方法DiBS，保持符号求解的完备性，以扩散模型作为分支排序的指导。核心方法是在当前部分赋值下，对候选值进行排名，并融合轻量级一致性信号。我们还提供了深入的理论证明，揭示其工作原理与有效性。在具有挑战性的Royle 17-clue数独基准测试中，与强启发式基线相比，DiBS显著降低了搜索成本，特别是在节点数、回溯次数及长尾百分位上表现突出。结果证实，学习到的全局引导对硬实例尤为有效，因分支选择错误代价极高。所有代码已开源至https://github.com/shanxierdan/DiBS。
原文摘要 · Abstract (English)
Sudoku is a representative constraint satisfaction problem that requires global structural reasoning under strict discrete constraints. The existing works of solving Sudoku mainly focus on two dominant approaches, i.e., traditional heuristic and deep learning solver. However, they suffer from two complementary limitations: learning-based solvers lack hard correctness guarantees, while complete symbolic solvers are still prone to long-tail search. To address these shortcomings, we propose a novel diffusion model-guided approach, termed as DiBS, for the branch selection search process. Specifically, DiBS keeps the symbolic solver complete and uses the diffusion model as a branch-ordering guide. The core method is ranking candidate values under the current partial assignment and lightweight consistency signal. Furthermore, we provide an in-depth theoretical proof to reveal how it works and why it works. Experiments on the challenging Royle 17-clue Sudoku benchmark show that our DiBS substantially reduces search cost relative to strong heuristic baselines, especially in nodes, backtracks, and long-tail percentiles. Besides, these results confirm that learned global guidance is effective on hard instances where branch-order mistakes are most expensive. All codes are available at https://github.com/shanxierdan/DiBS.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。