DiBS: диффузионный метод ускоряет решение сложных судоку без потери точности
Судоку — классическая задача удовлетворения ограничений, требующая глобального структурного рассуждения. Традиционно для её решения применяют эвристические алгоритмы или нейросети. Однако у обоих подходов есть недостатки: нейросети не гарантируют правильное решение, а полные символьные решатели могут застревать в долгом поиске.
Исследователи из неизвестной организации (работа опубликована на arXiv) предложили метод DiBS (Diffusion-Informed Branch Selection). Он сочетает полный символьный решатель с диффузионной моделью, которая служит направляющей для выбора ветвлений. Суть метода — ранжирование возможных значений на основе текущего частичного присваивания и сигналов согласованности.
Авторы работы представили теоретическое доказательство, объясняющее механизм работы и эффективность подхода. Эксперименты проводились на сложном наборе Royle с 17 ключами-подсказками. Результаты показали значительное снижение затрат на поиск: количество узлов, возвратов и длинные хвосты распределения времени решения сократились по сравнению с сильными эвристиками.
Особенно заметен выигрыш на сложных экземплярах, где ошибки при выборе ветвления наиболее критичны. DiBS показывает, что обученные глобальные подсказки могут успешно дополнять традиционные алгоритмы.
Исходный код метода доступен на GitHub по ссылке https://github.com/shanxierdan/DiBS. Разработка может найти применение не только в судоку, но и в других задачах удовлетворения ограничений.
