Jak vygenerovat sudoku s jediným řešením

Sudoku s jediným řešením vygenerujete ve dvou krocích. Nejdřív vyplňte prázdnou mřížku 9×9 celou, backtrackingem s náhodným pořadím číslic. Potom z ní po jednom a v náhodném pořadí mažte políčka a po každém smazání solverem zkontrolujte, jestli má zadání stále právě jedno řešení. Pokud ne, číslici vraťte zpět. Na běžném procesoru to trvá v mediánu méně než milisekundu.

Postup se hodí pro každou hru nebo aplikaci, která potřebuje neomezený počet nových zadání bez ruční přípravy. Takto vznikají sudoku například v naší aplikaci s křížovkami a hlavolamy (App Store, Google Play).

#Proč právě jedno řešení

Pravidla sudoku zná každý: v každém řádku, sloupci a čtverci 3×3 je každá číslice 1 až 9 právě jednou. Méně se mluví o tom, že dobré zadání má jediné řešení. Teprve pak se dá vyřešit čistou logikou, bez hádání.

Má to i praktický důsledek. Hra si obvykle pamatuje jedno řešení a podle něj kontroluje výsledek a dává nápovědy. Pokud má zadání řešení dvě, hráč může dojít k tomu druhému, které je stejně správné, a hra mu ho neuzná.

#Krok 1: Napište rychlý solver

Solver je program, který sudoku vyřeší. Pracuje backtrackingem: vyplní políčko jednou z možných číslic, pokračuje dalším políčkem, a když narazí na spor, vrátí se a zkusí jinou číslici. Budete ho potřebovat dvakrát: na vyplnění prázdné mřížky a na kontrolu jednoznačnosti. Kontrola běží po každém smazaném políčku, tedy 40 až 70krát na jedno zadání, proto musí být rychlá. Rozhodují dvě věci:

• Bitové masky. Pro každý řádek, sloupec a čtverec udržujte 9bitové číslo s už použitými číslicemi. Kandidáti políčka, tedy číslice, které do něj ještě můžou přijít, jsou pak jedna operace: všechny číslice kromě těch, které jsou v jeho řádku, sloupci nebo čtverci. Počet kandidátů je počet jedničkových bitů a dá se předem spočítat do tabulky s 512 hodnotami.
• Nejdřív políčko s nejmenším počtem kandidátů. Nevybírejte první prázdné políčko zleva, ale to, které má nejméně možností (v literatuře heuristika MRV, minimum remaining values). Políčko s jediným kandidátem vyplňte hned, políčko bez kandidáta znamená slepou větev a vracíte se.

Na těžkých zadáních potřebuje kontrola jednoznačnosti s tímto pravidlem v mediánu 311 kroků. Pokud solver bere políčka postupně zleva doprava, v mediánu 28 579 kroků a v nejhorších 5 % případů přes 300 000. Rozdíl je zhruba 90násobný.

#Krok 2: Vyplňte celou mřížku

Plnou mřížku dostanete stejným solverem spuštěným na prázdné mřížce. Jediný rozdíl je, že kandidáty políčka zkoušíte v náhodném pořadí. První nalezené řešení je náhodná, platná, úplně vyplněná mřížka.

#Proč nestačí smazat náhodná políčka

Nejjednodušší nápad je smazat z plné mřížky N náhodných políček, například 40, 50 nebo 55 podle obtížnosti. Zadání vypadá v pořádku, jen často nemá jediné řešení.

Typický případ je na obrázku. Čtyři políčka v rozích obdélníku, který zasahuje do dvou čtverců, se dají vyplnit dvěma způsoby a zbytek mřížky to nijak nerozhodne. Řešitelé sudoku tento vzor znají jako deadly pattern. Na 1 000 zadáních pro každou obtížnost vypadá výsledek takto:

Těžké zadání z náhodného mazání má v průměru stovky řešení. Kontrola jednoznačnosti po každém smazání je proto nutná.

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

Projděte všech 81 políček v náhodném pořadí. Každé zkuste smazat a solverem spočítejte řešení, ale počítání zastavte u dvou. Víc vědět nepotřebujete: jedno řešení znamená, že políčko může zůstat prázdné, dvě znamenají, že ho musíte vrátit.

zadání = kopie plné mřížky
prázdných = 0
pro každé políčko v náhodném pořadí:
    pokud prázdných == cíl: konec
    číslice = zadání[políčko]
    zadání[políčko] = prázdné
    pokud počet_řešení(zadání, nejvýš 2) == 1:
        prázdných = prázdných + 1
    jinak:
        zadání[políčko] = číslice

Políčko, které jednou vrátíte, už nezkoušejte znovu. Další mazání zadání jen uvolňuje, takže pokud políčko nešlo smazat teď, nepůjde ani později.

#Krok 4: Nastavte obtížnost počtem prázdných políček

Nejjednodušší míra obtížnosti je počet smazaných políček. Tři úrovně, které používáme v naší hře:

Čím méně číslic zbývá, tím častěji by další smazání pokazilo jednoznačnost a políčko se musí vrátit. U těžké úrovně se jeden průchod občas zastaví dřív, než dosáhne 55 prázdných políček. Pak vygenerujte novou plnou mřížku a zkuste to znovu. Při měření na 1 000 těžkých zadáních stačil první průchod v 97,6 % případů a nikdy nebylo potřeba víc než 3 pokusy.

#Rychlost a spolehlivost generátoru

Generátor jsme spustili na 1 000 zadáních pro každou obtížnost (Node.js 22 na serverovém procesoru, telefon bude pomalejší):

Každé vygenerované zadání jsme navíc nezávisle zkontrolovali solverem. Všech 3 000 mělo jediné řešení.

#Kde počet prázdných políček nestačí

Počet vodítek je hrubá míra obtížnosti. Dvě zadání s 26 číslicemi můžou být různě těžká podle toho, jaké logické techniky vyžadují. Přesnější obtížnost by zadání vyřešila jako člověk a zaznamenala nejtěžší techniku, kterou musela použít. Pro mobilní hru, kde si hráč vybírá ze tří úrovní, počet vodítek stačí.

Pokud řešíte podobný problém, generujete hlavolamy nebo potřebujete mobilní aplikaci, napište nám. Jak vygenerovat osmisměrku s tajenkou, popisuje samostatný návod. Švédské křížovce s tajenkou se věnuje další návod.