Hogyan generáljunk svéd rejtvényt megfejtéssel

Svéd rejtvényt megfejtéssel két fázisban generálhat: először lokális kereséssel keresse meg a maszkot, vagyis a kérdésmezők és a betűmezők elrendezését, aztán töltse ki a szótár szavaival kényszerkielégítési feladatként (CSP), backtrackinggel. A megfejtést ne tegye be előre a rácsba. Csak amikor a rejtvény kész, keressen egy viccet, amelynek a csattanója balról jobbra és fentről lefelé olvasva kiolvasható belőle.

Így készülnek a svéd rejtvények a keresztrejtvényeket és szókeresőket tartalmazó alkalmazásunkban (App Store, Google Play). Egy rács néhány másodperctől néhány tíz másodpercig tartó processzoridőbe kerül, ezért a rejtvényeket előre, erősebb számítógépen generáljuk, és az alkalmazással együtt szállítjuk. A szókeresőt egészen másképp és egyszerűbben lehet generálni, erről a Hogyan generáljunk szókeresőt rejtett megfejtéssel című cikk szól.

#Minek kell megfelelnie egy svéd rejtvénynek

A svéd rejtvényben nincsenek fekete mezők. Minden mező vagy betű, vagy jobbra, illetve lefelé mutató nyíllal ellátott kérdésmező. Ebből kemény feltételek következnek:

• Minden betű egy vízszintes és egy függőleges szóhoz is tartozik. Az a betű, amelyet csak egy szó keresztez, nem ellenőrizhető, és hibának hat.
• Minden szó legalább kétbetűs, és kérdésmező áll előtte. Ezért az első sor és az első oszlop mindig csupa kérdésmező.
• A betűk egyetlen összefüggő területet alkotnak, leszakadt szigetek nélkül.
• Minden szónak szerepelnie kell a szótárban, és legalább egy meghatározással kell rendelkeznie. Egy szó sem ismétlődik a rácsban.

Ehhez jönnek a lágy minőségi szempontok: kevés kétbetűs szó, ne legyen sehová sem mutató kérdésmező, és minél kevesebb nagyon hosszú szó, mert ezeket nehéz kitölteni. A feladat számításilag nehéz. Engel és társai (2012) megmutatták, hogy már a maszk szavakkal való kitöltése is NP-teljes.

#Miért nem elég szóról szóra kitölteni a rácsot

Az első ötlet az, hogy úgy járjunk el, mint egy ember ceruzával: a megfejtést szavakra bontjuk, újságszerűen egy sorba rakjuk, mindegyik betűjén átvezetünk egy keresztező szót, a rács többi részét pedig greedy algorithm tölti ki. A greedy algorithm minden lépésben azt választja, ami éppen akkor a legjobbnak látszik, és a döntést soha nem vizsgálja felül. Ahol semmi sem illik, lyuk marad. Mivel a greedy kitöltés nem tud visszalépni, ha az első tíz szó rossz, a rács többi része ezt már nem hozza helyre.

Egy jobb szóválasztási heurisztika csak keveset segít. Kipróbálhatja a keresztező szavak hosszát a középsőktől, nagyjából öt betűtől haladva a szélsők felé. Vagy választhat evolúciós megközelítést: félkész rejtvények populációja, mindegyikből öt utód egy-egy újabb szóval, értékelés a kitöltött mezők, a magánhangzók száma és a betűk egyenletessége alapján, és csak a legjobbak jutnak a következő generációba. Az eredmények valamivel sűrűbbek lesznek, de a lyukak maradnak, mert a heurisztika csak a következő lépést látja.

A kiutat Jakob Engel 2009-ben, a Müncheni Műszaki Egyetemen írt szakdolgozata mutatja meg; ő a fent említett cikk első szerzője is. Bontsa a feladatot két független fázisra: előbb keressen jó maszkot a szavakra való tekintet nélkül, aztán töltse ki. Engel a maszkhoz evolúciós algoritmust használt. Mi egyszerűbb, véletlen rázásokkal kiegészített lokális keresést használunk, ezt a következő lépés írja le.

#1. lépés: a maszk hill climbinggel

A maszk olyan rács, amelyben minden mező vagy kérdésmező, vagy betű. A megtalálásához elég a hill climbing: olyan lokális keresés, amely apró változtatásokat végez, és azokat tartja meg, amelyek nem rontanak az eredményen.

Induljon véletlenszerűen, a belső mezők nagyjából 22%-án kérdésmezővel. Minden maszkot pontozzon büntetőpontokkal. A kemény szabálysértések (túl rövid szó, keresztező szó nélküli betű, leszakadt sziget) többnyire 1000 pontba kerüljenek, a lágy hiányosságok (a megengedett számon felüli kétbetűs szavak, semmilyen szóra nem mutató kérdésmező, egymás mellé zsúfolt kérdésmezők) 50 és 500 pont közé.

Ezután ciklusban alakítson egy mezőt kérdésmezőből betűvé vagy fordítva, esetleg toljon egy kérdésmezőt átlósan egy mezővel arrébb. A változtatást tartsa meg, ha a büntetés nem nőtt, különben vonja vissza. A változtatások felét irányítsa a legnagyobb büntetésű mezőkre, így a durva hibák gyorsan eltűnnek:

A hill climbing könnyen elakad egy lokális minimumban. Ha 2000 lépésen át semmi sem javul, „rázza meg” a rácsot: az eddigi legjobb maszkban fordítson át öt véletlen mezőt, és keressen tovább. A grafikonon ezek a csúcsok. Ha három rázás után sincs jobb maszk, és nincs benne kemény szabálysértés, álljon le.

A kész maszk maradék büntetése 200 a lágy hiányosságokért, de kemény szabálysértés nincs benne:

A szó nélküli kérdésmezőért és a leszakadt szigetért járó büntetés legyen a maszkban kezdettől fogva. Egy nagy, kész rejtvényekből álló gyűjteményben ezek nélkül a kérdésmezők 13,2%-a nem mutatott egyetlen szóra sem, és a rácsok 23,5%-ában volt leszakadt betűsziget. Velük ezek az értékek 5,0% és 0%.

#2. lépés: kitöltés szavakkal CSP-ként

A maszkból slotok listája lesz, vagyis ismert hosszúságú és ismert keresztezésű szóhelyek. A kitöltés klasszikus kényszerkielégítési feladat (constraint satisfaction problem, CSP): minden slot egy változó, a tartománya a belé illő szavak, a kényszerek pedig az egyező betűk a keresztezéseknél. Backtrackinggel oldható meg, vagyis olyan kereséssel, amely zsákutcás ágban egy lépést visszalép, és más lehetőséget próbál:

minden slotra: tartomány = az adott hosszúságú összes szó
amíg nincs minden slot kitöltve:
    válaszd a legkisebb tartományú slotot (egyezésnél a legtöbb keresztezésűt)
    a tartomány minden szavára, a legjobbtól kezdve:
        írd be a szót
        szűkítsd a keresztező slotok tartományát az egyező betűjű szavakra
        ha valamelyik tartomány kiürült: vond vissza, próbáld a következő szót
        különben folytasd a következő slottal
    ha egyik szó sem jó: lépj vissza egy slotot
50 000 lépés után add fel

A szakirodalom ezeket a heurisztikákat MRV-nek (minimum remaining values, először a legkevesebb lehetőséggel rendelkező slot) és forward checkingnek nevezi (minden beírás után szűkítsük a szomszédok tartományát, hogy a zsákutcás ág azonnal kiderüljön, ne tíz szóval később). Indexelje a szótárt előre hossz, pozíció és betű szerint. Így „a harmadik helyen Q betűt tartalmazó szavak” egyetlen halmazmetszetet jelentenek, nem a teljes szótár átnézését.

A szavak sorrendje is számít. Részesítse előnyben azokat a szavakat, amelyekhez a szótárban több különböző meghatározás tartozik. Ez egyszerű jele annak, hogy gyakori rejtvényszóról van szó. Enélkül a rács ismeretlen rövidítésekkel telne meg.

#3. lépés: a megfejtés a kész rácsban

Kitöltés közben még nem tudja, mi lesz a megfejtés. Olvassa ki a kész rács betűit balról jobbra és fentről lefelé, és keressen olyan viccet, amelynek csattanója ennek a karakterláncnak részsorozata. A betűk tehát a helyes sorrendben követik egymást, de nem kell egymás mellett lenniük. Ha talál ilyet, a megfejtés betűit ossza el a lehető legegyenletesebben a rácsban, hogy a csattanót ne lehessen egyetlen szóból kitalálni.

Ez a sorrend (előbb a rács, aztán a vicc) jelentősen megnöveli a kész rejtvények számát. Méréseink szerint egyetlen 12×12-es rácsba átlagosan 86 vicc illik a szlovák gyűjteményből (5960 vicc). Így mindig akad olyan, amelyet az adott méretben még nem használtunk.

#Miért ne helyezzük el előre a megfejtést, mint az újságokban

Az újságokban a megfejtés általában egy helyen, egy sorban és szavakra bontva áll. Ezt kétféleképpen lehet elérni, és mindkettő nagyon kevés eredményt ad.

Az első módszer, hogy a megfejtést előre elhelyezzük a rácsban. Ekkor bele kell férnie. A csattanóink átlagosan 10,3 betűből és 2 szóból állnak. Ekkora a szlovák gyűjtemény azon vicceinek aránya, amelyek egyáltalán elhelyezhetők az adott méretben:

Előre elhelyezett megfejtéssel a kis rácsok kitöltése nagyjából ugyanolyan gyakran sikerül, mint nélküle. 15×15-nél 60 próbálkozásból 5 sikerült a megfejtés nélküli 8-cal szemben, 18×18-nál 60-ból egy sem. Ráadásul minden ilyen rács egyetlen vicchez tartozik, és kis méretekben a viccek többsége el sem helyezhető.

A második módszer, hogy a rács szabadon alakul ki, és a csattanót összefüggő szakaszként keressük benne. 2200 kész szlovák rejtvényből álló mintán (mind a 8×8-tól 18×18-ig terjedő méretekből 200-200) a teljes csattanó összefüggő szakaszként egy sorban vagy oszlopban mindössze 81 rácsban fordult elő (3,7%). Ha a csattanó minden szava máshol lehet, 443 rácsban (20%), és ez még a szavak egymás mellett állásának feltétele nélkül. Olvasási sorrendben mindegyikben akadt vicc. A rácsban szétszórt megfejtés árán nagyságrendekkel több rejtvényt kap.

#A generátor teljesítménye, és miért nem fut a telefonon

A generátor méretenként 60 próbálkozást futtatott a szlovák szótárral, egy szálon (JavaScript, Node 22, Intel Xeon 2,8 GHz-es szerverprocesszor a felhőben). Egy próbálkozás egy maszk és egy kitöltés. A „sikeres kitöltés” azt jelenti, hogy a CSP 50 000 lépésen belül megoldást talált.

Mit mutatnak a mérések:

• A kis rács nem könnyű rács. A 8×8-as rácsban sok a rövid, sokszorosan keresztezett slot, és kevés a mozgástér, a kitöltés a próbálkozások mindössze 5%-ában sikerül. Egy kitöltött rács átlagosan körülbelül 10 másodperc processzoridőbe kerül 8×8-nál, 4 másodpercbe 12×12-nél és 18 másodpercbe 18×18-nál.
• A legtöbb próbálkozás kudarccal végződik. Ezért futtassa a próbálkozásokat párhuzamosan az összes magon, és vegye az első elég jó eredményt.
• A telefonon ennek nincs értelme. A játékos nem akar több tíz másodpercet várni a képernyő megnyitásakor, és az alkalmazásnak a teljes, meghatározásokat tartalmazó szótárt magával kellene vinnie. Az alkalmazáson belüli generátornak ráadásul gyakran át kell adnia a vezérlést a felhasználói felületnek, különben az alkalmazás lefagy.

#Generálás nagy mennyiségben

A generátor helye ezért egy többmagos processzorú számítógép. Nálunk minden mag saját szálat kap az indításkor egyszer betöltött szótárral. A rács akkor kész, amikor valamelyik szál elég kevés kihasználatlan mezőt tartalmazó eredményt ad vissza. Folyamatos üzemmódban körbe-körbe generál egy-egy rejtvényt minden méretben és minden nyelven. Így készült több mint 14 000 rejtvény négy nyelven (szlovák, cseh, angol, német) és tizenegy méretben 8×8-tól 18×18-ig. Minden vicc méretenként és nyelvenként legfeljebb egyszer szerepel.

Ekkora mennyiségnél két dolog számít:

• Formátum. A teljes rekord rejtvényenként körülbelül 28 kB, a teljes gyűjtemény 390 MB. Ennek nagy része kiszámítható (koordináták, mezőtípusok, kérdésmezők számai). A rácsot egyetlen karakterláncként tároló tömör formátum körülbelül 2 kB, a gyűjtemény 15 MB, az alkalmazás telepítőcsomagjában pedig nagyjából 7 MB.
• Minőségmérés. Minden generálás után mérje a szó nélküli kérdésmezők és a szigetes rácsok arányát, és az ellenőrzés jelezzen hibát, ha a számok romlanak.

#Amit a megoldás nem fed le

• Szó nélküli kérdésmezők. Az átlagos rejtvényben még mindig 2,7 kérdésmező mutat a semmibe. A bal felső sarok mindig ilyen.
• Gyakorisági adatok nélküli szótárak. A Wikiszótárból származó német szótárban a legtöbb szóhoz egyetlen meghatározás tartozik, így a meghatározások száma szerinti rangsor alig különböztet, és ritka szavak kerülnek a rácsba. Egy gyakorisági lista segítene, egyelőre nincs ilyenünk.
• A megfejtés nem egy helyen áll. Aki az újságokhoz szokott, egy sorban keresheti. Ez kompromisszum, nem ideális megoldás.

Ha hasonló, tartalomgenerálással kapcsolatos problémán dolgozik, vagy mobilalkalmazásra van szüksége, írjon nekünk.