Ako vygenerovať osemsmerovku s tajničkou

Osemsmerovku s tajničkou vygenerujete tak, že do prázdnej mriežky ukladáte náhodné slová zo slovníka, kým v nej neostane voľných presne toľko políčok, koľko písmen má tajnička. Tie potom vyplníte tajničkou zľava doprava a zhora nadol. Celé to v telefóne trvá pár milisekúnd a nepotrebuje backtracking, teda vracanie sa k skorším rozhodnutiam, keď sa generátor zasekne.

Osemsmerovka je mriežka písmen, v ktorej hráč hľadá a škrtá slová zo zoznamu. Tajnička je text, ktorý sa prečíta zo zvyšných, neprečiarknutých písmen. Generátor preto musí poskladať mriežku, ktorá je úplne plná a v ktorej po vyškrtaní slov ostane presne tajnička. Postup nižšie je ten, ktorým generujeme osemsmerovky v našej aplikácii s krížovkami a osemsmerovkami (App Store, Google Play).

#Pravidlá mriežky

Skôr než začnete, ujasnite si, čo má hotová mriežka spĺňať. V našej aplikácii platí:

• Slová idú v ôsmich smeroch: vodorovne, zvisle a po oboch uhlopriečkach, každým smerom aj pospiatky.
• Dve slová sa môžu prekrývať najviac v jednom písmene.
• Žiadne slovo nesmie prechádzať políčkom tajničky.
• Mriežka musí byť plná. Prázdne políčko je chyba.
• Tajnička sa číta v poradí zľava doprava a zhora nadol zo všetkých neprečiarknutých písmen.

#Krok 1: Pripravte slovník

Slovník rozdeľte raz na začiatku do skupín podľa dĺžky slova. Výber náhodného slova danej dĺžky je potom jeden náhodný index. Ak by ste pri každom slove filtrovali celý slovník, generovanie sa citeľne spomalí, lebo slov sa do jednej mriežky skúša stovky.

Náš slovenský slovník má 16 713 slov s dĺžkou od 3 do 21 písmen, najviac je sedem- a osempísmenových. Pár praktických rád:

• Nechajte v slovníku aj vlastné mená a skratky. V mriežke sa potom objaví napríklad HOUSTON alebo MAINE. Bez krátkych a „divných“ slov sa mriežka nedá dostatočne zahustiť.
• Vulgarizmy filtrujte samostatným zoznamom, ktorý sa dá vypnúť, ak hráč chce obsah pre dospelých.
• Pri viacerých jazykoch načítajte len ten, v ktorom sa hrá. Anglický slovník má vyše 414 000 slov. Načítanie všetkých štyroch jazykov naraz pri štarte aplikácie zamrazí slabší telefón aj na 11 sekúnd.

#Krok 2: Vyberte tajničku

Tajnička by mala mať aspoň toľko písmen, koľko je strana mriežky, a najviac o štyri viac. Kratšia v mriežke zanikne, dlhšia vyžaduje príliš veľa dier.

V našej aplikácii je tajnička pointa vtipu. Hráč škrtá slová a zo zvyšných písmen si prečíta, ako vtip končí. Tajničku skladáme z konca vtipu: odzadu pridávame celé slová, kým nespadne do uvedeného rozsahu.

Obrázky nižšie používajú anglický vtip „Two snakes walk into a bar. Turns out they were lizards.“ (Dva hady vojdú do baru. Ukáže sa, že to boli jaštery.) a mriežku 10×10. Tajnička je WERELIZARDS, teda 11 písmen. Slová v obrázkoch sú z anglického slovníka zúženého na bežné slová, aby sa dali čítať.

#Prečo nezačínať tajničkou

Prvý nápad je robiť to, čo by človek robil ceruzkou: najprv rozhodiť písmená tajničky na náhodné políčka v poradí čítania a potom okolo nich skladať slová.

Vyzerá to rozumne, kým nepríde koniec. Generátor si vyberie prázdne políčko, skúsi cezeň dostať slovo vo všetkých smeroch a posunoch, a keď mriežka zhustne, ostanú izolované diery. Jedna diera medzi dvoma písmenami tajničky sa nedá zaplniť ničím, lebo najkratšie slovo má tri písmená a cez tajničku slovo ísť nesmie.

Na vzorke 200 mriežok 10×10 tento prístup skončil s plnou mriežkou len v 28 % prípadov, priemerne ostali 1 až 2 diery. Opravovať ich dodatočne je zložité. Tajničku preto do mriežky nedávajte, kým nie sú hotové slová.

#Krok 3: Plňte mriežku, kým neostane presne N dier

Plnenie je jednoduchý greedy algorithm: každé slovo sa položí hneď, ako sa zmestí, a už sa neodoberá. Generátor si pamätá iba jedno číslo: koľko políčok je ešte prázdnych. Slovo položí len vtedy, ak by po ňom neostalo menej prázdnych políčok, než má tajnička písmen (N).

prázdne = riadky × stĺpce
kým prázdne > N a pokusov < 2000:
    slovo = náhodné slovo zvolenej dĺžky
    opakuj najviac 50-krát:
        začiatok = náhodné políčko, smer = náhodný z 8
        ak sa slovo zmestí podľa pravidiel mriežky:
            nové = počet prázdnych políčok, ktoré slovo zaplní
            ak prázdne - nové >= N:
                polož slovo
                prázdne = prázdne - nové
                pokračuj ďalším slovom
ak prázdne != N: mriežku zahoď a začni odznova

Prvé slová padnú do prázdnej mriežky voľne:

Postupne slová začínajú zdieľať písmená. To je vítané, lebo každé zdieľané písmeno je jedno políčko, ktoré netreba zapĺňať:

Keď počet prázdnych políčok klesne na N, plnenie končí. Kde tie diery sú, je jedno. Môžu byť roztrúsené kdekoľvek, lebo tajnička sa nimi nemusí dať nijako prejsť:

#Krok 4: Losujte dĺžku slova s rozumom

Dlhé slová robia osemsmerovku zaujímavou, krátke ju dokážu dokončiť. Dĺžku preto losujte z dvoch normálnych rozdelení (normálne rozdelené náhodné čísla dostanete napríklad Box-Mullerovou transformáciou):

Dĺžka je vždy aspoň 3 a nanajvýš strana mriežky. K tomu dve pravidlá, bez ktorých sa generátor na konci zasekáva:

• Na konci vynúťte presnú dĺžku. Keď do cieľa chýba 5 a menej políčok, hľadajte slovo presne takej dĺžky, aká chýba (najmenej 3). Inak sa bude generátor donekonečna pokúšať o šesťpísmenové slová, ktoré sa už nezmestia.
• Trojpísmenové slová dávajte na prídel. Prvé tri pokusy o mriežku nesmú obsahovať ani jedno, pokusy 4 až 6 jedno, ďalšie tri dve a tak ďalej. Trojpísmenové slová sú v slovníku často skratky typu DNA alebo CPU a v osemsmerovke pôsobia lacno. Povoľte ich, až keď to inak nejde.

#Krok 5: Vlejte tajničku do dier

Prejdite mriežku zľava doprava a zhora nadol a do každého prázdneho políčka zapíšte ďalšie písmeno tajničky. Keďže dier je presne N, tajnička sa zmestí bezo zvyšku.

Hráč vidí len toto:

#Keď sa mriežka nepodarí

Ak generátor ani po 2 000 pokusoch nedosiahne presne N prázdnych políčok, celú mriežku zahoďte a začnite znova, najviac 100-krát. Žiadne opravovanie dier. Je to hrubé, ale pri mriežkach do 12×12 to stačí s rezervou. Väčšie mriežky potrebujú viac pokusov, ako ukazuje tabuľka nižšie.

#Úspešnosť a rýchlosť podľa veľkosti mriežky

Generátor bežal na 300 mriežkach pre každú veľkosť, so skutočnými vtipmi a slovenským slovníkom (Node.js 22 na serverovom procesore, telefón bude pomalší; obrázky v článku sú z anglického slovníka, čísla zo slovenského, lebo je menší a teda prísnejší test). „Na prvý pokus“ znamená, že prvé kolo plnenia skončilo plnou mriežkou.

Čo z toho vyplýva pre vlastný generátor:

• Priemerné slovo má 4,7 písmena, hoci cieľ je okolo 6. Dlhé slová sa do zahustenej mriežky jednoducho častejšie nezmestia.
• Asi 9 až 10 % políčok zdieľajú dve slová. Netreba to nastavovať, vyplýva to z pravidla „najviac jedno spoločné písmeno“.
• Uhlopriečok bude menej, než čakáte. Smer sa losuje rovnomerne z ôsmich, takže by mali tvoriť polovicu slov. V malej mriežke však uhlopriečne slovo oveľa častejšie vypadne za okraj. Na 8×8 tvoria uhlopriečky 24 % slov, na 15×15 už 33 %. Ak chcete viac uhlopriečok, dajte im pri losovaní smeru vyššiu váhu.

#Tip: rovnaká mriežka pri každom spustení

Na screenshoty do obchodov potrebujete, aby sa vygenerovala vždy tá istá mriežka. Namiesto bežného generátora náhodných čísel použite v takom režime jednoduchý lineárny kongruenčný generátor s pevným seedom (napríklad odvodeným z jazyka). Ak držíte všetku aritmetiku v rozsahu, ktorý desatinné čísla v JavaScripte reprezentujú presne, výsledok je rovnaký na každom zariadení. Rovnakým trikom sú vygenerované aj obrázky v tomto článku.

Ak riešite podobný problém, generujete hlavolamy alebo potrebujete mobilnú aplikáciu, napíšte nám. Krátke ukážky z vývoja dávame aj na YouTube. Podobne krok za krokom je opísané aj to, ako vygenerovať sudoku s jediným riešením. Ak potrebujete krížovku namiesto osemsmerovky, pozrite si, ako vygenerovať švédsku krížovku s tajničkou.