Jak vygenerovat švédskou křížovku s tajenkou

Švédskou křížovku s tajenkou vygenerujete ve dvou fázích: nejdřív lokálním prohledáváním najděte masku, tedy rozmístění políček s legendami a políček na písmena, a potom ji vyplňte slovy ze slovníku jako úlohu s omezeními (CSP) s backtrackingem. Tajenku do mřížky předem nevkládejte. Teprve když je křížovka hotová, hledejte vtip, jehož pointa se v ní dá přečíst zleva doprava a shora dolů.

Takto vznikají švédské křížovky v naší aplikaci s křížovkami a osmisměrkami (App Store, Google Play). Jedna mřížka zabere několik až desítky sekund procesorového času, proto je generujeme předem na výkonnějším počítači a přibalíme je do aplikace. Osmisměrka se generuje úplně jinak a jednodušeji, postup je v článku Jak vygenerovat osmisměrku s tajenkou.

#Co musí švédská křížovka splňovat

Švédská křížovka nemá černá políčka. Každé políčko je písmeno, nebo legenda se šipkou doprava či dolů. Z toho plynou tvrdé podmínky:

• Každé písmeno patří vodorovnému i svislému slovu. Písmeno, které kříží jen jedno slovo, nejde zkontrolovat a v křížovce působí jako chyba.
• Každé slovo má aspoň dvě písmena a před ním je legenda. Proto jsou první řádek a první sloupec vždy tvořené jen legendami.
• Písmena tvoří jeden souvislý celek, žádné odtržené ostrovy.
• Každé slovo musí být ve slovníku a mít aspoň jednu legendu. Žádné slovo se v mřížce neopakuje.

K tomu měkká kritéria kvality: málo dvoupísmenných slov, žádné legendy, které nikam neukazují, a co nejméně velmi dlouhých slov, která se těžko plní. Problém je výpočetně těžký. Engel a kol. (2012) ukázali, že už samotné plnění masky slovy je NP-úplné.

#Proč nestačí plnit mřížku slovo po slově

První nápad je postupovat jako člověk s tužkou: rozdělit tajenku na slova, položit je do řádku jako v novinách, přes každé její písmeno vést křížící slovo a zbytek mřížky doplňovat greedy algoritmem. Greedy algorithm v každém kroku vybere možnost, která vypadá nejlépe právě teď, a rozhodnutí už nikdy nepřehodnotí. Kde nic nesedí, zůstane díra. A protože se greedy plnění neumí vrátit, špatných prvních deset slov zbytek mřížky už nezachrání.

Lepší heuristika výběru slov pomůže jen trochu. Můžete zkoušet délky křížících slov od středních, kolem pěti písmen, ke krajním. Nebo použít evoluční přístup: populace rozpracovaných křížovek, z každé pět potomků s jedním slovem navíc, hodnocení podle počtu zaplněných políček, počtu samohlásek a rovnoměrnosti písmen a do další generace postoupí jen ty nejlepší. Výsledky jsou o něco hustší, ale díry zůstanou, protože heuristika vidí jen nejbližší krok.

Řešení přináší bakalářská práce Jakoba Engela z TU Mnichov (2009), který je i prvním autorem zmíněného článku. Úlohu rozdělte na dvě nezávislé fáze: nejdřív najděte dobrou masku bez ohledu na slova, potom ji plňte. Engel na masku použil evoluční algoritmus. My používáme jednodušší lokální prohledávání s náhodnými otřesy, popsané v dalším kroku.

#Krok 1: maska přes hill climbing

Maska je mřížka, ve které je každé políčko buď legenda, nebo písmeno. K jejímu hledání stačí hill climbing: lokální prohledávání, které dělá malé změny a ponechá ty, které řešení nezhorší.

Začněte náhodně, s legendami asi na 22 % vnitřních políček. Každou masku ohodnoťte pokutou. Tvrdá porušení (příliš krátké slovo, písmeno bez křížícího slova, odtržený ostrov) ať stojí většinou 1 000 bodů, měkké nedostatky (dvoupísmenná slova nad rozpočet, legenda, která neukazuje na žádné slovo, shluky legend) 50 až 500.

Potom v cyklu změňte jedno políčko z legendy na písmeno nebo naopak, případně posuňte legendu o políčko šikmo. Změnu ponechte, pokud se pokuta nezvýšila, jinak ji vraťte. Polovinu změn zamiřte na políčka s nejvyšší pokutou, pak hrubé chyby zmizí rychle:

Hill climbing snadno uvízne v lokálním minimu. Když se za 2 000 kroků nic nezlepší, mřížkou „zatřeste“: v nejlepší dosud nalezené masce náhodně přehoďte pět políček a hledejte dál. V grafu jsou to špičky. Pokud ani po třech zatřeseních není maska lepší a nemá tvrdá porušení, skončete.

Výsledná maska má zbytkovou pokutu 200 za měkké nedostatky, ale žádné tvrdé porušení:

Pokuty za legendu bez slova a za odtržený ostrov se vyplatí mít v masce od začátku. Na velkém souboru hotových křížovek bez nich mělo 13,2 % legend, které neukazovaly na žádné slovo, a 23,5 % mřížek odtržený ostrov písmen. S nimi je to 5,0 % a 0 %.

#Krok 2: plnění slovy jako CSP

Z masky vznikne seznam slotů, tedy míst na slova se známou délkou a kříženími. Plnění je klasická úloha s omezeními (constraint satisfaction problem, CSP): každý slot je proměnná, jeho doména jsou slova, která se do něj vejdou, a omezení jsou shodná písmena v kříženích. Řeší se backtrackingem, tedy prohledáváním, které se ve slepé větvi vrátí o krok zpět a zkusí jinou možnost:

pro každý slot: doména = všechna slova dané délky
dokud nejsou všechny sloty vyplněné:
    vyber slot s nejmenší doménou (při shodě ten s nejvíc kříženími)
    pro každé slovo z domény, od nejlepšího:
        polož slovo
        zuž domény křížících slotů na slova se shodným písmenem
        pokud některá doména zůstala prázdná: vrať změnu, zkus další slovo
        jinak pokračuj dalším slotem
    pokud žádné slovo nevyhovuje: vrať se o slot zpět
po 50 000 krocích to vzdej

V literatuře se tyto heuristiky jmenují MRV (minimum remaining values, nejdřív slot s nejméně možnostmi) a forward checking (po každém položení zúžit domény sousedů, aby se slepá větev odhalila hned, ne o deset slov později). Slovník si předpočítejte podle délky, pozice a písmene. Slova se „Š na třetím místě“ jsou pak jeden průnik množin, ne průchod celým slovníkem.

Důležité je i pořadí slov. Přednost dejte slovům, která mají ve slovníku víc různých legend. Je to jednoduchý ukazatel běžného křížovkářského slova. Bez něj se mřížka zaplní neznámými zkratkami.

#Krok 3: tajenka až v hotové mřížce

Při plnění ještě nevíte, jaká bude tajenka. Přečtěte písmena hotové mřížky zleva doprava a shora dolů a hledejte vtip, jehož pointa je v tomto řetězci podposloupností. Písmena tedy jdou ve správném pořadí, ale nemusí být vedle sebe. Pokud se najde, rozmístěte písmena tajenky co nejrovnoměrněji po mřížce, aby se pointa nedala uhodnout z jednoho slova.

Toto pořadí (nejdřív mřížka, potom vtip) zásadně zvyšuje počet hotových křížovek. Jedna mřížka 12×12 se podle našeho měření v průměru hodí pro 86 vtipů ze slovenského seznamu (5 960 vtipů). Vždy se tedy najde takový, který ještě v dané velikosti nebyl použit.

#Proč nevkládat tajenku předem jako v novinách

V novinách je tajenka obvykle pohromadě, v jednom řádku a rozdělená na slova. Dá se toho dosáhnout dvěma způsoby a oba dávají velmi málo výsledků.

První způsob je vložit tajenku do mřížky předem. Pak se do ní musí vejít. Pointa má u nás v průměru 10,3 písmene a 2 slova. Takto vypadá podíl vtipů ze slovenského seznamu, které se do dané velikosti vůbec dají položit:

S tajenkou vloženou předem uspěje plnění u malých mřížek přibližně stejně často jako bez ní. U 15×15 to bylo 5 z 60 pokusů oproti 8 bez tajenky, u 18×18 ani jeden z 60. Každá taková mřížka navíc slouží jedinému vtipu a u malých velikostí se většina vtipů nedá ani položit.

Druhý způsob je nechat mřížku vzniknout volně a pointu v ní hledat jako souvislý úsek. Na vzorku 2 200 hotových slovenských křížovek (200 z každé velikosti od 8×8 po 18×18) se celá pointa jako souvislý úsek v jednom řádku nebo sloupci našla jen v 81 mřížkách (3,7 %). Když smí každé slovo pointy ležet jinde, je to 443 mřížek (20 %), a to ještě bez podmínky, že slova budou u sebe. Při čtení v pořadí se vtip našel v každé z nich. Za cenu tajenky roztroušené po mřížce dostanete řádově víc křížovek.

#Výkon generátoru a proč neběží v telefonu

Generátor běžel 60 pokusů pro každou velikost se slovenským slovníkem, v jednom vlákně (JavaScript v Node 22, serverový procesor Intel Xeon 2,8 GHz v cloudu). Pokus je jedna maska a jedno plnění. „Úspěšné plnění“ znamená, že CSP našel řešení do 50 000 kroků.

Co z měření plyne:

• Malá mřížka není snadná. V 8×8 je hodně krátkých slotů s velkým počtem křížení a málo volnosti, plnění uspěje jen v 5 % pokusů. Jedna vyplněná mřížka stojí v průměru asi 10 sekund procesorového času u 8×8, 4 sekundy u 12×12 a 18 sekund u 18×18.
• Většina pokusů skončí neúspěchem. Pokusy proto spouštějte paralelně na všech jádrech a berte první dost dobrý výsledek.
• V telefonu to nedává smysl. Hráč nechce při otevření obrazovky čekat desítky sekund a aplikace by musela nést celý slovník s legendami. Generátor v aplikaci navíc musí často pouštět ke slovu UI, jinak aplikace zamrzá.

#Generování ve velkém

Generátor proto patří na počítač s vícejádrovým procesorem. U nás má každé jádro vlastní vlákno se slovníkem načteným jednou při startu. Mřížka je hotová, když některé vlákno vrátí výsledek s dostatečně malým počtem nevyužitých políček. Nepřetržitý režim generuje dokola jednu křížovku z každé velikosti v každém jazyce. Takto vzniklo přes 14 000 křížovek ve čtyřech jazycích (slovenština, čeština, angličtina, němčina) a jedenácti velikostech od 8×8 po 18×18. Každý vtip je v dané velikosti a jazyce použitý nejvýš jednou.

Při takovém objemu rozhodují dvě věci:

• Formát. Úplný zápis má kolem 28 kB na křížovku a celý korpus 390 MB. Většina se dá dopočítat (souřadnice, typy políček, čísla legend). Kompaktní zápis s mřížkou jako jedním řetězcem má kolem 2 kB, celý korpus 15 MB a v instalačním balíčku aplikace asi 7 MB.
• Měření kvality. Podíl legend bez slova a mřížek s ostrovy měřte po každém generování a nechte kontrolu selhat, pokud se čísla zhorší.

#Co řešení nepokrývá

• Legendy bez slov. Průměrná křížovka má pořád 2,7 legendy, které nikam neukazují. Levý horní roh je takový vždy.
• Slovník bez frekvencí. Německý slovník z Wiktionary má u většiny slov jedinou legendu, takže řazení podle počtu legend skoro nerozlišuje a do mřížky se dostávají vzácná slova. Pomohl by frekvenční slovník, zatím ho nemáme.
• Tajenka není pohromadě. Kdo je zvyklý na tajenky z novin, může ji hledat v řádku. Je to kompromis, ne ideál.

Pokud řešíte podobný problém s generováním obsahu nebo potřebujete mobilní aplikaci, napište nám.