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
Розв’язувачі, що мислять як люди
Рушій підказок має інше завдання: не лише знайти відповідь, а й показати наступний крок, який людина може зрозуміти й повторити. Рушій нашого застосунку перевіряє техніки людського розв’язування у фіксованому порядку, від найпростіших, як-от «Прихований одинак», до найскладніших, як-от ланцюги та майже замкнені множини, і використовує першу з них, що приводить до встановлення цифри; складніші техніки спочатку виключають кандидатів. Найскладніша техніка, яку він застосовує до головоломки, визначає її рівень у застосунку.
Джерела: Чого потребує кожен рівень складності судоку
