Накратко: програмата решава судоку на два етапа. Първо попълва сигурните клетки с логика. После пробва възможните цифри и се връща назад при грешка (търсене с връщане назад). Така дори най-трудното судоку се решава за части от секундата. Вижте го в действие в судоку решителя.

Алгоритъмът стъпка по стъпка

  1. За всяка празна клетка намерете кандидатите - цифрите, които ги няма в реда, колоната и квадрата й.
  2. Ако клетка има само един кандидат, впишете го.
  3. Ако в ред, колона или квадрат дадена цифра има само едно възможно място, впишете я.
  4. Повтаряйте стъпки 1-3, докато има промени.
  5. Ако остават празни клетки, изберете тази с най-малко кандидати и пробвайте първия.
  6. Продължете напред. Ако стигнете до клетка без нито един кандидат, върнете се и пробвайте следващата цифра.
  7. Когато няма празни клетки, судокуто е решено.

Етап 1: логика

Стъпки 2 и 3 са същите техники, които ползва и човек: единствен кандидат и скрит единак. Само с тях се решават повечето лесни и средни судоку. За трудните човек ползва по-сложни техники, като двойки и свързани кандидати. Те са описани в как се решава судоку. Програмата може да мине и без тях, защото има етап 2.

Етап 2: търсене с връщане назад

Това е като излизане от лабиринт: вървите по един път, а при задънена улица се връщате до последното разклонение. На английски се нарича backtracking. Тайната на скоростта е в избора на клетка: ако тя има само 2 кандидата, най-много един опит ще е грешен.

Ето целия алгоритъм като псевдокод:

функция реши(решетка):
  ако няма празни клетки:
    върни РЕШЕНО
  клетка = празната клетка с най-малко кандидати
  за всяка цифра от кандидатите на клетката:
    впиши цифрата
    ако реши(решетка) = РЕШЕНО:
      върни РЕШЕНО
    изтрий цифрата
  върни ЗАДЪНЕНА УЛИЦА

Клетка без кандидати дава празен цикъл, така че функцията сама се връща назад. Този кратък код решава всяко судоку 9×9, обикновено за хилядни от секундата. Пробвайте да решите судоку на ниво Експерт сами и сравнете времето.

Как се проверява дали решението е едно

Правилното судоку има точно едно решение. За да го провери, програмата не спира след първото решение, а продължава да търси. Ако намери второ, в судокуто липсва цифра. Така работи и нашият решител.

Същата проверка служи и за създаване на нови судоку. Програмата започва с пълна решетка и маха цифри една по една. След всяка проверява дали решението е останало едно. Колкото повече цифри се махнат, толкова по-трудно е судокуто. Доказано е, че судоку 9×9 с едно решение има поне 17 дадени цифри.

Други известни алгоритми

Източници