Накратко: програмата решава судоку на два етапа. Първо попълва сигурните клетки с логика. После пробва възможните цифри и се връща назад при грешка (търсене с връщане назад). Така дори най-трудното судоку се решава за части от секундата. Вижте го в действие в судоку решителя.
Алгоритъмът стъпка по стъпка
- За всяка празна клетка намерете кандидатите - цифрите, които ги няма в реда, колоната и квадрата й.
- Ако клетка има само един кандидат, впишете го.
- Ако в ред, колона или квадрат дадена цифра има само едно възможно място, впишете я.
- Повтаряйте стъпки 1-3, докато има промени.
- Ако остават празни клетки, изберете тази с най-малко кандидати и пробвайте първия.
- Продължете напред. Ако стигнете до клетка без нито един кандидат, върнете се и пробвайте следващата цифра.
- Когато няма празни клетки, судокуто е решено.
Етап 1: логика
Стъпки 2 и 3 са същите техники, които ползва и човек: единствен кандидат и скрит единак. Само с тях се решават повечето лесни и средни судоку. За трудните човек ползва по-сложни техники, като двойки и свързани кандидати. Те са описани в как се решава судоку. Програмата може да мине и без тях, защото има етап 2.
Етап 2: търсене с връщане назад
Това е като излизане от лабиринт: вървите по един път, а при задънена улица се връщате до последното разклонение. На английски се нарича backtracking. Тайната на скоростта е в избора на клетка: ако тя има само 2 кандидата, най-много един опит ще е грешен.
Ето целия алгоритъм като псевдокод:
функция реши(решетка):
ако няма празни клетки:
върни РЕШЕНО
клетка = празната клетка с най-малко кандидати
за всяка цифра от кандидатите на клетката:
впиши цифрата
ако реши(решетка) = РЕШЕНО:
върни РЕШЕНО
изтрий цифрата
върни ЗАДЪНЕНА УЛИЦАКлетка без кандидати дава празен цикъл, така че функцията сама се връща назад. Този кратък код решава всяко судоку 9×9, обикновено за хилядни от секундата. Пробвайте да решите судоку на ниво Експерт сами и сравнете времето.
Как се проверява дали решението е едно
Правилното судоку има точно едно решение. За да го провери, програмата не спира след първото решение, а продължава да търси. Ако намери второ, в судокуто липсва цифра. Така работи и нашият решител.
Същата проверка служи и за създаване на нови судоку. Програмата започва с пълна решетка и маха цифри една по една. След всяка проверява дали решението е останало едно. Колкото повече цифри се махнат, толкова по-трудно е судокуто. Доказано е, че судоку 9×9 с едно решение има поне 17 дадени цифри.
Други известни алгоритми
- Ограничения и търсене (Питър Норвиг). Същата идея като по-горе, описана в популярно есе с код на Python.
- Dancing Links (Доналд Кнут). Судокуто се превръща в задача за „точно покритие“, която се решава много бързо. Ползва се и за други пъзели.
- Пълно преброяване не работи. Попълнените решетки 9×9 са около 6,7 секстилиона (6 670 903 752 021 072 936 960), затова всички добри алгоритми отсичат невъзможните варианти още в началото.