DiBS: Diffusion-Informed Branch Selection
For constraint satisfaction problems like Sudoku, DiBS addresses the trade-off between learning-based solvers (no correctness guarantees) and symbolic solvers (long-tail search) by using learned guidance to improve efficiency while preserving completeness.
DiBS combines a diffusion model with a complete symbolic solver to guide branch selection in Sudoku, reducing search cost (nodes, backtracks, long-tail percentiles) on the Royle 17-clue benchmark compared to strong heuristic baselines.
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.