Jak vygenerovat osmisměrku s tajenkou

Osmisměrku s tajenkou vygenerujete tak, že do prázdné mřížky ukládáte náhodná slova ze slovníku, dokud v ní nezůstane volných přesně tolik políček, kolik písmen má tajenka. Ta pak vyplníte tajenkou zleva doprava a shora dolů. V telefonu to celé trvá pár milisekund a nepotřebuje backtracking, tedy vracení se k dřívějším rozhodnutím, když se generátor zasekne.

Osmisměrka je mřížka písmen, ve které hráč hledá a škrtá slova ze seznamu. Tajenka je text, který se přečte ze zbylých, nepřeškrtnutých písmen. Generátor proto musí složit mřížku, která je úplně plná a ve které po vyškrtání slov zůstane přesně tajenka. Postup níže je ten, kterým generujeme osmisměrky v naší aplikaci s křížovkami a osmisměrkami (App Store, Google Play).

#Pravidla mřížky

Než začnete, ujasněte si, co má hotová mřížka splňovat. V naší aplikaci platí:

• Slova vedou v osmi směrech: vodorovně, svisle a po obou úhlopříčkách, každým směrem i pozpátku.
• Dvě slova se mohou překrývat nejvýš v jednom písmenu.
• Žádné slovo nesmí procházet políčkem tajenky.
• Mřížka musí být plná. Prázdné políčko je chyba.
• Tajenka se čte zleva doprava a shora dolů ze všech nepřeškrtnutých písmen.

#Krok 1: Připravte slovník

Slovník rozdělte jednou na začátku do skupin podle délky slova. Výběr náhodného slova dané délky je pak jeden náhodný index. Kdybyste u každého slova filtrovali celý slovník, generování se znatelně zpomalí, protože do jedné mřížky se zkouší stovky slov.

Náš slovenský slovník má 16 713 slov s délkou od 3 do 21 písmen, nejvíc je sedmi- a osmipísmenných, český má 64 414 slov. Pár praktických rad:

• Nechte ve slovníku i vlastní jména a zkratky. V mřížce se pak objeví třeba HOUSTON nebo MAINE. Bez krátkých a „divných“ slov nejde mřížku dostatečně zahustit.
• Vulgarismy filtrujte samostatným seznamem, který jde vypnout, pokud hráč chce obsah pro dospělé.
• U více jazyků načtěte jen ten, ve kterém se hraje. Anglický slovník má přes 414 000 slov. Načtení všech čtyř jazyků naráz při startu aplikace zmrazí slabší telefon až na 11 sekund.

#Krok 2: Vyberte tajenku

Tajenka by měla mít aspoň tolik písmen, kolik je strana mřížky, a nejvýš o čtyři víc. Kratší v mřížce zanikne, delší vyžaduje příliš mnoho děr.

V naší aplikaci je tajenka pointa vtipu. Hráč škrtá slova a ze zbylých písmen si přečte, jak vtip končí. Tajenku skládáme z konce vtipu: odzadu přidáváme celá slova, dokud její délka nespadne do uvedeného rozsahu.

Obrázky níže používají anglický vtip „Two snakes walk into a bar. Turns out they were lizards.“ (Dva hadi vejdou do baru. Ukáže se, že to byly ještěrky.) na mřížce 10×10. Tajenka je WERELIZARDS, tedy 11 písmen. Slova v obrázcích jsou z anglického slovníku zúženého na běžná slova, aby se dala číst.

#Proč nezačínat tajenkou

První nápad je dělat to, co by člověk dělal tužkou: nejdřív rozházet písmena tajenky na náhodná políčka v pořadí čtení a potom kolem nich skládat slova.

Vypadá to rozumně, dokud nepřijde konec. Generátor si vybere prázdné políčko, zkusí přes něj dostat slovo ve všech směrech a posunech, a když mřížka zhoustne, zůstanou izolované díry. Jednu díru mezi dvěma písmeny tajenky nezaplní nic, protože nejkratší slovo má tři písmena a přes tajenku slovo vést nesmí.

Na vzorku 200 mřížek 10×10 tento přístup skončil s plnou mřížkou jen ve 28 % případů, v průměru zůstaly 1 až 2 díry. Opravovat je dodatečně je složité. Tajenku proto do mřížky nedávejte, dokud nejsou hotová slova.

#Krok 3: Plňte mřížku, dokud nezůstane přesně N děr

Plnění je jednoduchý greedy algorithm: každé slovo se položí hned, jak se vejde, a už se neodebírá. Generátor si pamatuje jen jedno číslo: kolik políček je ještě prázdných. Slovo položí jen tehdy, pokud by po něm nezůstalo méně prázdných políček, než má tajenka písmen (N).

prázdná = řádky × sloupce
dokud prázdná > N a pokusů < 2000:
    slovo = náhodné slovo zvolené délky
    opakuj nejvýš 50krát:
        začátek = náhodné políčko, směr = náhodný z 8
        pokud se slovo vejde podle pravidel mřížky:
            nová = počet prázdných políček, která slovo zaplní
            pokud prázdná - nová >= N:
                polož slovo
                prázdná = prázdná - nová
                pokračuj dalším slovem
pokud prázdná != N: mřížku zahoď a začni znovu

První slova padnou do prázdné mřížky volně:

Postupně slova začínají sdílet písmena. To je vítané, protože každé sdílené písmeno je jedno políčko, které není třeba zaplňovat:

Když počet prázdných políček klesne na N, plnění končí. Kde ty díry jsou, je jedno. Mohou být rozházené kdekoli, protože tajenka jimi nemusí vést žádnou cestou:

#Krok 4: Losujte délku slova s rozumem

Dlouhá slova dělají osmisměrku zajímavou, krátká ji dokážou dokončit. Délku proto losujte ze dvou normálních rozdělení (normálně rozdělená náhodná čísla dostanete třeba Box-Mullerovou transformací):

Délka je vždy aspoň 3 a nejvýš strana mřížky. K tomu dvě pravidla, bez kterých se generátor na konci zasekává:

• Na konci vynuťte přesnou délku. Když do cíle chybí 5 a méně políček, hledejte slovo přesně takové délky, jaká chybí (nejméně 3). Jinak se bude generátor donekonečna pokoušet o šestipísmenná slova, která se už nevejdou.
• Třípísmenná slova dávejte na příděl. První tři pokusy o mřížku nesmí obsahovat ani jedno, pokusy 4 až 6 jedno, další tři dvě a tak dál. Třípísmenná slova jsou ve slovníku často zkratky typu DNA nebo CPU a v osmisměrce působí lacině. Povolte je, až když to jinak nejde.

#Krok 5: Vlijte tajenku do děr

Projděte mřížku zleva doprava a shora dolů a do každého prázdného políčka zapište další písmeno tajenky. Protože děr je přesně N, tajenka se vejde beze zbytku.

Hráč vidí jen tohle:

#Když se mřížka nepovede

Pokud generátor ani po 2 000 pokusech nedosáhne přesně N prázdných políček, celou mřížku zahoďte a začněte znovu, nejvýš 100krát. Žádné opravování děr. Je to hrubé, ale u mřížek do 12×12 to stačí s rezervou. Větší mřížky potřebují víc pokusů, jak ukazuje tabulka níže.

#Úspěšnost a rychlost podle velikosti mřížky

Generátor běžel na 300 mřížkách pro každou velikost, se skutečnými vtipy a slovenským slovníkem (Node.js 22 na serverovém procesoru, telefon bude pomalejší; obrázky v článku jsou z anglického slovníku, čísla ze slovenského, protože je menší, a tedy přísnější test). „Na první pokus“ znamená, že první kolo plnění skončilo plnou mřížkou.

Co z toho plyne pro vlastní generátor:

• Průměrné slovo má 4,7 písmene, i když cíl je kolem 6. Dlouhá slova se do zahuštěné mřížky prostě častěji nevejdou.
• Asi 9 až 10 % políček sdílejí dvě slova. Není třeba to nastavovat, plyne to z pravidla „nejvýš jedno společné písmeno“.
• Úhlopříček bude méně, než čekáte. Směr se losuje rovnoměrně z osmi, takže by měly tvořit polovinu slov. V malé mřížce ale úhlopříčné slovo mnohem častěji vypadne za okraj. Na 8×8 tvoří úhlopříčky 24 % slov, na 15×15 už 33 %. Pokud chcete víc úhlopříček, dejte jim při losování směru vyšší váhu.

#Tip: stejná mřížka při každém spuštění

Na screenshoty do obchodů potřebujete, aby se vygenerovala vždy stejná mřížka. Místo běžného generátoru náhodných čísel použijte v takovém režimu jednoduchý lineární kongruenční generátor s pevným seedem (třeba odvozeným z jazyka). Pokud držíte veškerou aritmetiku v rozsahu, který čísla v JavaScriptu reprezentují přesně, výsledek je stejný na každém zařízení. Stejným trikem jsou vygenerované i obrázky v tomto článku.

Pokud řešíte podobný problém, generujete hlavolamy nebo potřebujete mobilní aplikaci, napište nám. Krátké ukázky z vývoje dáváme i na YouTube. Podobně krok za krokem je popsáno i to, jak vygenerovat sudoku s jediným řešením. Pokud potřebujete křížovku místo osmisměrky, podívejte se, jak vygenerovat švédskou křížovku s tajenkou.