Sudoku FlowКак компьютеры решают судоку
Обновлено 2026-10-05
Поиск с возвратом
Программа пробует поставить допустимую цифру в пустую ячейку и продолжает решение. Если ни одна цифра не приводит к решению, она отменяет один из предыдущих выборов и пробует другой. Если сначала выбирать ячейку с наименьшим числом возможных цифр, поиск часто становится значительно короче.
Источники: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Точное покрытие и Dancing Links
Судоку можно переформулировать как задачу точного покрытия: выбрать размещения цифр так, чтобы каждая ячейка и каждая цифра в каждой строке, столбце и блоке были покрыты ровно один раз. В статье, опубликованной в ноябре 2000 года, Дональд Кнут описал Dancing Links, эффективный способ выполнения своего алгоритма X с поиском с возвратом; применённый к модели судоку в виде задачи точного покрытия, он быстро находит все решения головоломки.
Источники: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Случайный поиск
Некоторые программы заполняют сетку случайным образом, а затем переставляют цифры, чтобы уменьшить число конфликтов, используя такие методы, как имитация отжига или генетические алгоритмы. Эти методы изучались как альтернативные подходы; их эффективность зависит от программы и головоломки.
Источники: Wikipedia: Sudoku solving algorithms
Программы, рассуждающие как люди
У системы подсказок другая задача: не просто найти ответ, а показать следующий шаг, который человек сможет понять и выполнить. Система в нашем приложении пробует человеческие техники в фиксированном порядке, от самых простых, таких как «Скрытая одиночка», до самых сложных, таких как цепочки и почти замкнутые множества, и использует первую технику, которая приводит к размещению цифры; более сложные техники сначала исключают кандидатов. Самая сложная техника, которую система использует при решении головоломки, определяет уровень этой головоломки в приложении.
Источники: Что требуется от вас на каждом уровне судоку
