Ako vygenerovať sudoku s jediným riešením

Sudoku s jediným riešením vygenerujete v dvoch krokoch. Najprv vyplňte prázdnu mriežku 9×9 celú, backtrackingom s náhodným poradím číslic. Potom z nej po jednom a v náhodnom poradí mažte políčka a po každom vymazaní solverom skontrolujte, či má zadanie stále práve jedno riešenie. Ak nie, číslicu vráťte späť. Na bežnom procesore to trvá v mediáne menej ako milisekundu.

Postup je vhodný pre každú hru alebo aplikáciu, ktorá potrebuje neobmedzený počet nových zadaní bez ručnej prípravy. Takto vznikajú sudoku napríklad v našej aplikácii s krížovkami a hlavolamami (App Store, Google Play).

#Prečo práve jedno riešenie

Pravidlá sudoku pozná každý: v každom riadku, stĺpci a štvorci 3×3 je každá číslica 1 až 9 práve raz. Menej sa hovorí o tom, že dobré zadanie má jediné riešenie. Až vtedy sa dá vyriešiť čistou logikou, bez hádania.

Má to aj praktický dôsledok. Hra si zvyčajne pamätá jedno riešenie a podľa neho kontroluje výsledok a dáva nápovedy. Ak má zadanie riešenia dve, hráč môže dôjsť k tomu druhému, ktoré je rovnako správne, a hra mu ho neuzná.

#Krok 1: Napíšte rýchly solver

Solver je program, ktorý sudoku vyrieši. Pracuje backtrackingom: vyplní políčko jednou z možných číslic, pokračuje ďalším políčkom, a keď narazí na spor, vráti sa a skúsi inú číslicu. Budete ho potrebovať dvakrát: na vyplnenie prázdnej mriežky a na kontrolu jednoznačnosti. Kontrola beží po každom vymazanom políčku, teda 40 až 70-krát na jedno zadanie, preto musí byť rýchla. Dve veci rozhodujú:

• Bitové masky. Pre každý riadok, stĺpec a štvorec si držte 9-bitové číslo s už použitými číslicami. Kandidáti políčka, teda číslice, ktoré doň ešte môžu prísť, sú potom jedna operácia: všetky číslice okrem tých, ktoré sú v jeho riadku, stĺpci alebo štvorci. Počet kandidátov je počet jednotkových bitov a dá sa vopred vypočítať do tabuľky s 512 hodnotami.
• Najprv políčko s najmenším počtom kandidátov. Nevyberajte prvé prázdne políčko zľava, ale to, ktoré má najmenej možností (v literatúre heuristika MRV, minimum remaining values). Políčko s jediným kandidátom vyplňte hneď, políčko bez kandidáta znamená slepú vetvu a vraciate sa.

Na ťažkých zadaniach potrebuje kontrola jednoznačnosti s týmto pravidlom v mediáne 311 krokov. Ak solver berie políčka postupne zľava doprava, v mediáne 28 579 krokov a v najhorších 5 % prípadov vyše 300 000. Rozdiel je zhruba 90-násobný.

#Krok 2: Vyplňte celú mriežku

Plnú mriežku dostanete tým istým solverom spusteným na prázdnej mriežke. Jediný rozdiel je, že kandidátov políčka skúšate v náhodnom poradí. Prvé nájdené riešenie je náhodná, platná, úplne vyplnená mriežka.

#Prečo nestačí vymazať náhodné políčka

Najjednoduchší nápad je vymazať z plnej mriežky N náhodných políčok, napríklad 40, 50 alebo 55 podľa obťažnosti. Zadanie vyzerá v poriadku, len často nemá jediné riešenie.

Typický prípad je na obrázku. Štyri políčka v rohoch obdĺžnika, ktorý zasahuje do dvoch štvorcov, sa dajú vyplniť dvoma spôsobmi a zvyšok mriežky to nijako nerozhodne. Riešitelia sudoku tento vzor poznajú ako deadly pattern. Na 1 000 zadaniach pre každú obťažnosť vyzerá výsledok takto:

Ťažké zadanie z náhodného vymazávania má v priemere stovky riešení. Kontrola jednoznačnosti po každom vymazaní je preto nutná.

#Krok 3: Mažte s kontrolou jednoznačnosti

Prejdite všetkých 81 políčok v náhodnom poradí. Každé skúste vymazať a solverom spočítajte riešenia, ale počítanie zastavte pri dvoch. Viac netreba vedieť: jedno riešenie znamená, že políčko môže ostať prázdne, dve znamenajú, že ho treba vrátiť.

zadanie = kópia plnej mriežky
prázdnych = 0
pre každé políčko v náhodnom poradí:
    ak prázdnych == cieľ: koniec
    číslica = zadanie[políčko]
    zadanie[políčko] = prázdne
    ak počet_riešení(zadanie, najviac 2) == 1:
        prázdnych = prázdnych + 1
    inak:
        zadanie[políčko] = číslica

Políčko, ktoré raz vrátite, už neskúšajte znova. Ďalšie mazanie zadanie len uvoľňuje, takže ak políčko nešlo vymazať teraz, nepôjde ani neskôr.

#Krok 4: Nastavte obťažnosť počtom prázdnych políčok

Najjednoduchšia miera obťažnosti je počet vymazaných políčok. Tri úrovne, ktoré používame v našej hre:

Čím menej číslic ostáva, tým častejšie by ďalšie vymazanie pokazilo jednoznačnosť a políčko sa musí vrátiť. Pri ťažkej úrovni sa jeden prechod občas zastaví skôr, než dosiahne 55 prázdnych políčok. Vtedy vygenerujte novú plnú mriežku a skúste to znova. Pri meraní na 1 000 ťažkých zadaniach stačil prvý prechod v 97,6 % prípadov a nikdy nebolo treba viac ako 3 pokusy.

#Rýchlosť a spoľahlivosť generátora

Generátor sme spustili na 1 000 zadaniach pre každú obťažnosť (Node.js 22 na serverovom procesore, telefón bude pomalší):

Každé vygenerované zadanie sme navyše nezávisle skontrolovali solverom. Všetkých 3 000 malo jediné riešenie.

#Kde počet prázdnych políčok nestačí

Počet vodítok je hrubá miera obťažnosti. Dve zadania s 26 číslicami môžu byť rôzne ťažké podľa toho, aké logické techniky vyžadujú. Presnejšia obťažnosť by zadanie vyriešila ako človek a zaznamenala najťažšiu techniku, ktorú musela použiť. Na mobilnú hru, kde si hráč vyberá z troch úrovní, počet vodítok stačí.

Ak riešite podobný problém, generujete hlavolamy alebo potrebujete mobilnú aplikáciu, napíšte nám. Ako vygenerovať osemsmerovku s tajničkou, opisuje samostatný návod. Švédskej krížovke s tajničkou sa venuje ďalší návod.