Hogyan generáljunk szókeresőt rejtett megfejtéssel

Rejtett megfejtésű szókeresőt úgy generálhat, hogy egy üres rácsba véletlenszerű szavakat tesz a szótárból, amíg pontosan annyi szabad mező marad, ahány betűs a megfejtés. Ezeket aztán kitölti a megfejtéssel balról jobbra és fentről lefelé. Telefonon ez néhány milliszekundum, és nem kell hozzá backtracking, vagyis visszalépés korábbi döntésekhez, amikor a generátor elakad.

A szókereső egy betűrács, amelyben a játékos egy lista szavait keresi meg és húzza ki. A megfejtés a kihúzás után megmaradó betűkből olvasható ki. A generátornak tehát teljesen kitöltött rácsot kell összeraknia, amelyben a szavak kihúzása után pontosan a megfejtés marad. Az alábbi módszerrel készülnek a szókeresők a keresztrejtvényes és szókeresős alkalmazásunkban (App Store, Google Play).

#A rács szabályai

Mielőtt nekikezd, döntse el, mit kell teljesítenie a kész rácsnak. Az alkalmazásunkban ezek a szabályok:

• A szavak nyolc irányban futnak: vízszintesen, függőlegesen és mindkét átló mentén, mindegyik irányban visszafelé is.
• Két szónak legfeljebb egy közös betűje lehet.
• Egyetlen szó sem haladhat át a megfejtés mezőjén.
• A rácsnak tele kell lennie. Az üres mező hiba.
• A megfejtést balról jobbra és fentről lefelé olvassuk az összes ki nem húzott betűből.

#1. lépés: Készítse elő a szótárt

A szótárt egyszer, az elején ossza csoportokba szóhossz szerint. Így egy adott hosszúságú véletlen szó kiválasztása egyetlen véletlen index. Ha minden szónál a teljes szótárt szűri, a generálás érezhetően lelassul, mert egy rácshoz több száz szót próbál ki.

A szlovák szótárunk 16 713 szót tartalmaz 3 és 21 betű között, a legtöbb hét- és nyolcbetűs. Néhány gyakorlati tanács:

• Hagyja a szótárban a tulajdonneveket és rövidítéseket is. Így a rácsban felbukkan például HOUSTON vagy MAINE. Rövid és „furcsa” szavak nélkül a rácsot nem lehet elég sűrűn kitölteni.
• A trágár szavakat külön listával szűrje, amelyet ki lehet kapcsolni, ha a játékos felnőtt tartalmat szeretne.
• Több nyelv esetén csak azt töltse be, amelyen épp játszanak. Az angol szótárban több mint 414 000 szó van. Ha az alkalmazás indulásakor mind a négy nyelvet egyszerre tölti be, egy gyengébb telefon akár 11 másodpercre is lefagy.

#2. lépés: Válassza ki a megfejtést

A megfejtésnek legalább annyi betűből kell állnia, amekkora a rács oldala, és legfeljebb néggyel többől. A rövidebb elveszik a rácsban, a hosszabb túl sok lyukat igényel.

Az alkalmazásunkban a megfejtés egy vicc csattanója. A játékos kihúzza a szavakat, és a maradék betűkből olvassa ki, hogyan végződik a vicc. A megfejtést a vicc végéről állítjuk össze: hátulról teljes szavakat fűzünk hozzá, amíg a hossza ebbe a tartományba nem esik.

Az alábbi képek a „Two snakes walk into a bar. Turns out they were lizards.” angol viccet használják (Két kígyó bemegy egy bárba. Kiderül, hogy gyíkok voltak.), 10×10-es rácson. A megfejtés WERELIZARDS, 11 betű. A képeken szereplő szavak az angol szótárból származnak, a gyakori szavakra szűkítve, hogy olvashatók legyenek.

#Miért ne a megfejtéssel kezdjen

Az első ötlet az, amit ceruzával csinálnánk: a megfejtés betűit olvasási sorrendben véletlenszerű mezőkre szórni, aztán köréjük építeni a szavakat.

Ez ésszerűnek tűnik, amíg el nem jön a vége. A generátor kiválaszt egy üres mezőt, megpróbál rajta keresztül szót elhelyezni minden irányban és eltolással, és amikor a rács besűrűsödik, elszigetelt lyukak maradnak. Egyetlen lyukat két megfejtésbetű között semmi sem tölthet ki, mert a legrövidebb szó hárombetűs, és a megfejtésen szó nem haladhat át.

200 darab 10×10-es rácson ez a megközelítés csak az esetek 28 %-ában adott teli rácsot, átlagosan 1-2 lyuk maradt. Utólag foltozni őket nehéz. Ezért a megfejtést addig ne tegye a rácsba, amíg a szavak el nem készülnek.

#3. lépés: Töltse a rácsot, amíg pontosan N lyuk marad

A kitöltés egy egyszerű greedy algorithm: minden szót azonnal letesz, amint elfér, és többé nem veszi ki. A generátor egyetlen számot követ: hány mező üres még. Csak akkor tesz le egy szót, ha utána nem marad kevesebb üres mező, mint ahány betűs a megfejtés (N).

üres = sorok × oszlopok
amíg üres > N és próbálkozás < 2000:
    szó = véletlen szó a választott hosszal
    legfeljebb 50-szer ismételd:
        kezdet = véletlen mező, irány = véletlen a 8-ból
        ha a szó elfér a rács szabályai szerint:
            új = hány üres mezőt töltene ki a szó
            ha üres - új >= N:
                tedd le a szót
                üres = üres - új
                folytasd a következő szóval
ha üres != N: dobd el a rácsot és kezdd elölről

Az első szavak szabadon kerülnek az üres rácsba:

Ahogy a rács telik, a szavak egyre többször osztoznak betűkön. Ez kifejezetten jó, mert minden közös betű eggyel kevesebb kitöltendő mezőt jelent:

Amikor az üres mezők száma N-re csökken, a kitöltés véget ér. Hogy hol vannak a lyukak, mindegy. Bárhol szétszórva lehetnek, mert a megfejtésnek nem kell rajtuk keresztül összefüggő utat alkotnia:

#4. lépés: Sorsolja okosan a szóhosszt

A hosszú szavak teszik érdekessé a szókeresőt, a rövidek segítenek befejezni. Ezért a hosszt két normális eloszlásból sorsolja (normális eloszlású véletlenszámokat például a Box-Muller-transzformáció ad):

A hossz mindig legalább 3 és legfeljebb a rács oldala. Ehhez két szabály kell, különben a generátor a végén elakad:

• A végén kényszerítse ki a pontos hosszt. Ha a célig 5 vagy kevesebb mező hiányzik, pontosan a hiányzó hosszúságú szót keressen (legalább 3). Különben a generátor a végtelenségig próbálkozik hatbetűs szavakkal, amelyek már nem férnek el.
• A hárombetűs szavakat adagolja. Egy rács első három próbálkozásában egy sem lehet, a 4-6. próbálkozásban egy, a következő háromban kettő, és így tovább. A hárombetűs szótári szavak gyakran rövidítések, például DNA vagy CPU, és a rejtvényben olcsón hatnak. Csak akkor engedje őket, ha másként nem megy.

#5. lépés: Öntse a megfejtést a lyukakba

Járja be a rácsot balról jobbra és fentről lefelé, és minden üres mezőbe írja a megfejtés következő betűjét. Mivel pontosan N lyuk van, a megfejtés maradék nélkül elfér.

A játékos csak ezt látja:

#Ha a rács nem sikerül

Ha a generátor 2000 próbálkozás alatt sem éri el pontosan az N üres mezőt, dobja el az egész rácsot, és kezdje elölről, legfeljebb 100-szor. Nincs lyukfoltozás. Ez durva megoldás, de 12×12-es rácsig bőven elég. Nagyobb rácsokhoz több próbálkozás kell, ahogy a lenti táblázat mutatja.

#Sikerarány és sebesség rácsméret szerint

A generátor méretenként 300 rácson futott, valódi viccekkel és a szlovák szótárral (Node.js 22 szerverprocesszoron, a telefon lassabb lesz; a képek az angol, a számok a szlovák szótárral készültek, mert az kisebb, így szigorúbb teszt). Az „első próbálkozásra” azt jelenti, hogy az első kitöltési kör teli ráccsal ért véget.

Mit jelent ez egy saját generátornál:

• Az átlagos szó 4,7 betűs, pedig a cél 6 körül van. A hosszú szavak egyszerűen gyakrabban nem férnek bele a sűrű rácsba.
• A mezők kb. 9-10 %-án két szó osztozik. Ezt nem kell beállítani, a „legfeljebb egy közös betű” szabályból adódik.
• Kevesebb átló lesz, mint amire számít. Az irányt egyenletesen sorsoljuk a nyolcból, így az átlóknak a szavak felét kellene kitenniük. Kis rácsban viszont az átlós szó sokkal gyakrabban lóg ki a szélén. 8×8-on az átlók a szavak 24 %-át adják, 15×15-ön már 33 %-át. Ha több átlót szeretne, adjon nekik nagyobb súlyt az irány sorsolásakor.

#Tipp: ugyanaz a rács minden futtatáskor

Az áruházi képernyőképekhez minden alkalommal pontosan ugyanarra a rácsra van szükség. Ebben a módban cserélje le a szokásos véletlenszám-generátort egy egyszerű lineáris kongruens generátorra rögzített seeddel (például a nyelvből származtatva). Ha minden számítás abban a tartományban marad, amelyet a JavaScript számai pontosan ábrázolnak, az eredmény minden eszközön azonos. Ugyanezzel a trükkel készültek a cikk képei is.

Ha hasonló problémán dolgozik, rejtvényeket generál, vagy mobilalkalmazásra van szüksége, írjon nekünk. Rövid videókat a fejlesztésből a YouTube csatornánkon is megosztunk. Ugyanígy lépésről lépésre olvasható az is, hogyan generáljunk egyértelmű megoldású sudokut. Ha szókereső helyett keresztrejtvényre van szüksége, olvassa el, hogyan generáljunk svéd rejtvényt megfejtéssel.