DiBS: Diffusion-Informed Branch Selection

Abstract: 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.

为了解决这些缺陷，我们提出了一种名为 DiBS 的新型扩散模型引导方法，用于分支选择搜索过程。具体而言，DiBS 在保持符号求解器完备性的同时，利用扩散模型作为分支排序的指南。其核心方法是在当前的局部赋值和轻量级一致性信号下，对候选值进行排序。

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 this https URL.

此外，我们提供了深入的理论证明，揭示了该方法的工作原理及其有效性。在极具挑战性的 Royle 17 线索数独基准测试上的实验表明，与强大的启发式基准相比，DiBS 大幅降低了搜索成本，特别是在节点数、回溯次数和长尾百分位方面。此外，这些结果证实，学习到的全局引导在分支顺序错误代价最高的困难实例上是有效的。所有代码均可在该链接获取。