Ako vygenerovať švédsku krížovku s tajničkou

Švédsku krížovku s tajničkou vygenerujete v dvoch fázach: najprv lokálnym prehľadávaním nájdite masku, teda rozmiestnenie políčok s legendami a políčok na písmená, a potom ju vyplňte slovami zo slovníka ako úlohu s obmedzeniami (CSP) s backtrackingom. Tajničku do mriežky nevkladajte vopred. Až keď je krížovka hotová, hľadajte vtip, ktorého pointa sa v nej dá prečítať zľava doprava a zhora nadol.

Takto vznikajú švédske krížovky v našej aplikácii s krížovkami a osemsmerovkami (App Store, Google Play). Jedna mriežka stojí niekoľko až desiatky sekúnd procesorového času, preto ich generujeme vopred na výkonnejšom počítači a do aplikácie ich pribalíme. Osemsmerovka sa generuje úplne inak a jednoduchšie, postup je v článku Ako vygenerovať osemsmerovku s tajničkou.

#Čo musí švédska krížovka spĺňať

Švédska krížovka nemá čierne políčka. Každé políčko je písmeno alebo legenda so šípkou doprava či nadol. Z toho vyplývajú tvrdé podmienky:

• Každé písmeno patrí vodorovnému aj zvislému slovu. Písmeno, ktoré kríži len jedno slovo, sa nedá skontrolovať a v krížovke pôsobí ako chyba.
• Každé slovo má aspoň dve písmená a pred ním je legenda. Preto je prvý riadok a prvý stĺpec vždy celý z legiend.
• Písmená tvoria jeden súvislý celok, žiadne odtrhnuté ostrovy.
• Každé slovo musí byť v slovníku a mať aspoň jednu legendu. Žiadne slovo sa v mriežke neopakuje.

K tomu mäkké kritériá kvality: málo dvojpísmenových slov, žiadne legendy, ktoré neukazujú na nič, a čo najmenej veľmi dlhých slov, ktoré sa ťažko plnia. Problém je výpočtovo ťažký. Engel a kol. (2012) ukázali, že už samotné plnenie masky slovami je NP-úplné.

#Prečo nestačí plniť mriežku slovo po slove

Prvý nápad je postupovať ako človek s ceruzkou: rozdeliť tajničku na slová, položiť ich do riadku ako v novinách, cez každé jej písmeno preložiť krížiace slovo a zvyšok mriežky dopĺňať greedy algoritmom. Greedy algorithm v každom kroku vyberie možnosť, ktorá vyzerá najlepšie práve teraz, a rozhodnutie už nikdy neprehodnotí. Kde nič nepasuje, ostane diera. A keďže sa greedy plnenie nevie vrátiť, zlých prvých desať slov zvyšok mriežky už nezachráni.

Lepšia heuristika výberu slov pomôže len trochu. Môžete skúšať dĺžky krížiacich slov od stredných, okolo piatich písmen, ku krajným. Alebo použiť evolučný prístup: populácia rozpracovaných krížoviek, z každej päť potomkov s jedným slovom navyše, ohodnotenie podľa počtu zaplnených políčok, počtu samohlások a rovnomernosti písmen a do ďalšej generácie postúpia len najlepšie. Výsledky sú o niečo hustejšie, ale diery ostanú, lebo heuristika vidí len najbližší krok.

Riešenie prináša bakalárska práca Jakoba Engela z TU Mníchov (2009), ktorý je aj prvým autorom spomínaného článku. Úlohu rozdeľte na dve nezávislé fázy: najprv nájdite dobrú masku bez ohľadu na slová, potom ju plňte. Engel na masku použil evolučný algoritmus. My používame jednoduchšie lokálne prehľadávanie s náhodnými otrasmi, opísané v nasledujúcom kroku.

#Krok 1: maska cez hill climbing

Maska je mriežka, v ktorej je každé políčko buď legenda, alebo písmeno. Na jej hľadanie stačí hill climbing: lokálne prehľadávanie, ktoré robí malé zmeny a ponechá tie, ktoré riešenie nezhoršia.

Začnite náhodne, s legendami asi na 22 % vnútorných políčok. Každú masku ohodnoťte pokutou. Tvrdé porušenia (príliš krátke slovo, písmeno bez krížiaceho slova, odtrhnutý ostrov) nech stoja zväčša 1 000 bodov, mäkké nedostatky (dvojpísmenové slová nad rozpočet, legenda, ktorá neukazuje na žiadne slovo, zhluky legiend) 50 až 500.

Potom v cykle zmeňte jedno políčko z legendy na písmeno alebo naopak, prípadne posuňte legendu o políčko šikmo. Zmenu ponechajte, ak sa pokuta nezvýšila, inak ju vráťte. Polovicu zmien namierte na políčka s najvyššou pokutou, potom hrubé chyby zmiznú rýchlo:

Hill climbing ľahko uviazne v lokálnom minime. Keď sa 2 000 krokov nič nezlepší, mriežku „zatraste“: v najlepšej doteraz nájdenej maske náhodne prehoďte päť políčok a hľadajte ďalej. Na grafe sú to špičky. Ak ani po troch zatraseniach nie je lepšia maska a nemá tvrdé porušenia, skončite.

Výsledná maska má zvyškovú pokutu 200 za mäkké nedostatky, ale žiadne tvrdé porušenie:

Pokuty za legendu bez slova a za odtrhnutý ostrov sa oplatí mať v maske od začiatku. Na veľkom súbore hotových krížoviek bez nich malo 13,2 % legiend neukazujúcich na žiadne slovo a 23,5 % mriežok odtrhnutý ostrov písmen. S nimi je to 5,0 % a 0 %.

#Krok 2: plnenie slovami ako CSP

Z masky vznikne zoznam slotov, teda miest na slová so známou dĺžkou a kríženiami. Plnenie je klasická úloha s obmedzeniami (constraint satisfaction problem, CSP): každý slot je premenná, jeho doména sú slová, ktoré sa doň zmestia, a obmedzenia sú zhodné písmená v kríženiach. Rieši sa backtrackingom, teda prehľadávaním, ktoré sa pri slepej vetve vráti o krok späť a skúsi inú možnosť:

pre každý slot: doména = všetky slová danej dĺžky
kým nie sú všetky sloty vyplnené:
    vyber slot s najmenšou doménou (pri zhode ten s najviac kríženiami)
    pre každé slovo z domény, od najlepšieho:
        polož slovo
        zúž domény krížiacich slotov na slová so zhodným písmenom
        ak niektorá doména ostala prázdna: vráť zmenu, skús ďalšie slovo
        inak pokračuj ďalším slotom
    ak žiadne slovo nevyhovuje: vráť sa o slot späť
po 50 000 krokoch to vzdaj

V literatúre sa tieto heuristiky volajú MRV (minimum remaining values, najprv slot s najmenej možnosťami) a forward checking (po každom položení zúžiť domény susedov, aby sa slepá vetva odhalila hneď, nie o desať slov neskôr). Slovník si predpočítajte podľa dĺžky, pozície a písmena. Slová so „Š na treťom mieste“ sú potom jeden prienik množín, nie prechod celým slovníkom.

Dôležité je aj poradie slov. Prednosť dajte slovám, ktoré majú v slovníku viac rôznych legiend. Je to jednoduchý ukazovateľ bežného krížovkárskeho slova. Bez neho sa mriežka zaplní neznámymi skratkami.

#Krok 3: tajnička až v hotovej mriežke

Pri plnení ešte neviete, aká bude tajnička. Prečítajte písmená hotovej mriežky zľava doprava a zhora nadol a hľadajte vtip, ktorého pointa je v tomto reťazci podpostupnosťou. Písmená teda idú v správnom poradí, ale nemusia byť vedľa seba. Ak sa nájde, rozmiestnite písmená tajničky čo najrovnomernejšie po mriežke, aby sa pointa nedala uhádnuť z jedného slova.

Toto poradie (najprv mriežka, potom vtip) zásadne zvyšuje počet hotových krížoviek. Jedna mriežka 12×12 v našom meraní pasuje v priemere na 86 vtipov zo slovenského zoznamu (5 960 vtipov). Vždy sa teda nájde taký, ktorý ešte v danej veľkosti nebol použitý.

#Prečo nevkladať tajničku vopred ako v novinách

V novinách je tajnička zvyčajne pokope, v jednom riadku a rozdelená na slová. Dá sa to dosiahnuť dvoma spôsobmi a oba dávajú veľmi málo výsledkov.

Prvý spôsob je vložiť tajničku do mriežky vopred. Vtedy sa do nej musí zmestiť. Pointa má u nás v priemere 10,3 písmena a 2 slová. Takto vyzerá podiel vtipov zo slovenského zoznamu, ktoré sa do danej veľkosti vôbec dajú položiť:

S tajničkou vloženou vopred uspeje plnenie pri malých mriežkach približne rovnako často ako bez nej. Pri 15×15 to bolo 5 zo 60 pokusov oproti 8 bez tajničky, pri 18×18 ani jeden zo 60. Každá taká mriežka navyše slúži jedinému vtipu a pri malých veľkostiach sa väčšina vtipov nedá ani položiť.

Druhý spôsob je nechať mriežku vzniknúť voľne a pointu v nej hľadať ako súvislý úsek. Na vzorke 2 200 hotových slovenských krížoviek (200 z každej veľkosti od 8×8 po 18×18) sa celá pointa ako súvislý úsek v jednom riadku alebo stĺpci našla len v 81 mriežkach (3,7 %). Keď môže každé slovo pointy ležať inde, je to 443 mriežok (20 %), a to ešte bez podmienky, že slová budú pri sebe. Pri čítaní v poradí sa vtip našiel v každej z nich. Za cenu tajničky roztrúsenej po mriežke dostanete rádovo viac krížoviek.

#Výkon generátora a prečo nebeží v telefóne

Generátor bežal 60 pokusov pre každú veľkosť so slovenským slovníkom, v jednom vlákne (JavaScript v Node 22, serverový procesor Intel Xeon 2,8 GHz v cloude). Pokus je jedna maska a jedno plnenie. „Úspešné plnenie“ znamená, že CSP našiel riešenie do 50 000 krokov.

Čo z meraní vyplýva:

• Malá mriežka nie je ľahká. V 8×8 je veľa krátkych slotov s veľkým počtom krížení a málo voľnosti, plnenie uspeje len v 5 % pokusov. Jedna vyplnená mriežka stojí v priemere asi 10 sekúnd procesora pri 8×8, 4 sekundy pri 12×12 a 18 sekúnd pri 18×18.
• Väčšina pokusov skončí neúspechom. Pokusy preto spúšťajte paralelne na všetkých jadrách a berte prvý dosť dobrý výsledok.
• V telefóne to nemá zmysel. Hráč nechce pri otvorení obrazovky čakať desiatky sekúnd a aplikácia by musela niesť celý slovník s legendami. Generátor v aplikácii navyše musí často púšťať UI k slovu, inak aplikácia zamŕza.

#Generovanie vo veľkom

Generátor preto patrí na počítač s viacjadrovým procesorom. U nás má každé jadro vlastné vlákno so slovníkom načítaným raz pri štarte. Mriežka je hotová, keď niektoré vlákno vráti výsledok s dostatočne malým počtom nevyužitých políčok. Nepretržitý režim generuje dookola jednu krížovku z každej veľkosti v každom jazyku. Takto vzniklo vyše 14 000 krížoviek v štyroch jazykoch (slovenčina, čeština, angličtina, nemčina) a jedenástich veľkostiach od 8×8 po 18×18. Každý vtip je v danej veľkosti a jazyku najviac raz.

Pri takom objeme rozhodujú dve veci:

• Formát. Úplný zápis má okolo 28 kB na krížovku a celý korpus 390 MB. Väčšina sa dá dopočítať (súradnice, typy políčok, čísla legiend). Kompaktný zápis s mriežkou ako jedným reťazcom má okolo 2 kB, celý korpus 15 MB a v inštalačnom balíku aplikácie asi 7 MB.
• Meranie kvality. Podiel legiend bez slova a mriežok s ostrovmi merajte po každom generovaní a nechajte kontrolu zlyhať, ak sa čísla zhoršia.

#Čo riešenie nepokrýva

• Legendy bez slov. Priemerná krížovka má stále 2,7 legendy, ktoré neukazujú na nič. Ľavý horný roh je taký vždy.
• Slovník bez frekvencií. Nemecký slovník z Wiktionary má na väčšinu slov jedinú legendu, takže poradie podľa počtu legiend skoro nerozlišuje a do mriežky sa dostávajú zriedkavé slová. Pomohol by frekvenčný slovník, zatiaľ ho nemáme.
• Tajnička nie je pokope. Kto je zvyknutý z novín, môže ju hľadať v riadku. Je to kompromis, nie ideál.

Ak riešite podobný problém s generovaním obsahu alebo potrebujete mobilnú aplikáciu, napíšte nám.