DiBS: New diffusion model slashes search time for Sudoku by guiding symbolic solvers

Sudoku solving has long been a testbed for constraint satisfaction algorithms, with two dominant approaches: heuristic-based symbolic solvers that guarantee correctness but struggle with exponential search in hard puzzles, and deep learning solvers that are fast but lack hard guarantees. Their complementary flaws—long-tail search on one side, hallucinated solutions on the other—leave a clear gap. Researchers from multiple institutions address this with DiBS (Diffusion-Informed Branch Selection), a method that keeps the symbolic solver intact but uses a diffusion model as a branch-ordering guide.

DiBS ranks candidate values under the current partial assignment using a lightweight consistency signal, effectively teaching the solver to make better branch decisions early. The team provides theoretical proof for why diffusion guidance reduces search cost. On the Royle 17-clue benchmark—notorious for its hardest instances—DiBS substantially reduces nodes visited, backtrack counts, and long-tail percentiles compared to strong heuristic baselines, demonstrating that learned global guidance can drastically cut search cost where branch-order mistakes are most expensive. All code is available on GitHub.