Kassa György LOGI TOLI játékának célja: cseréljük meg a citromsárga bábukat a narancssárga bábukkal. A bábuk mozgástere korlátozott, csak a játéktábla síkjában és azon belül is az egy bábu szélességnyi folyosókban haladhatnak. A középen látható egy bábu hosszúságnyi beugró szakaszt mindenképpen ki kell használni, hiszen nélküle legfeljebb az azonos színű bábuk egymás között cserélgethetnének helyet, a különböző színűek nem.

A LOGI TOLI játékot eredetiben már nem könnyű beszerezni, ezért az Olvasó rendelkezésére bocsátjuk egy azonnal kinyomtatható, majd 3+3 pénzérmével játszható otthoni változatát. Bátran ajánlható a kezdő játékosok figyelmébe is, a sikerélmény csak idő kérdése.

A játék egy korábbi változata – 3+3 helyett 4+4 bábuval – a már többször hivatkozott Dudeney egy évszázaddal ezelőtti könyvében is szerepel motor-garage puzzle néven.

A LOGI TOLI a sorozatos mozgatáson alapuló játékok családjába tartozik, azon belül pedig a csúsztatható elemek (5.3) osztályába sorolható. Alapelvét tekintve tehát közeli rokona a Cserebere játékoknak.

Ahogy az Olvasó is tapasztalta – vagy hamarosan tapasztalni fogja –, nem különösebben nehéz játékkal van dolgunk. Rendelkezik azonban egy kiváló tulajdonsággal, ami alkalmassá teszi arra, hogy elbíbelődjünk még vele pár percet, ez pedig a modellezhetőség. Látni fogjuk, hogy a játék lehetséges állásait meg lehet feleltetni egy gráf csúcsainak, amelyben két csúcsot akkor kötünk össze éllel, ha az egyik állásból egyetlen bábu mozgatásával el tudunk jutni a másik állásba. A feladatot így átfogalmazhatjuk egy klasszikus gráfelméleti problémára: olyan uta(ka)t, azaz élek egymást követő sorozatát keresünk, amely egy adott csúcsból indul és egy szintén adott csúcsba jut el. Gyakran még arra is kíváncsiak vagyunk, hogy az ilyen utak közül melyik a legrövidebb, azaz a legkevesebb élt – az eredeti feladat megfogalmazásában: lépést – tartalmazó.

Az egyszerűbb szöveges jelölés kedvéért mostantól helyettesítsük a citromsárga bábukat X betűvel, a narancssárgákat pedig O-val. A játékban összesen 10 bábunyi hely (mező) van, ezeket számozzuk be az alábbi ábra szerint:

Először is tisztázzuk, hogy mit értünk a játék állásai alatt. A 10 mezőből 3+3-at tudunk elfoglalni, a maradék 4 mező mindig üresen marad. Első megközelítésben ez (10 alatt 3)*(7 alatt 3) = 4200 lehetőség, de ennél szerencsére lényegesen kevesebb állással is elegendő lesz foglalkozni. Ahogy a matematikusok mondják, az általánosság megszorítása nélkül feltehető, hogy

• az 5. mező mindig üres;
• ha az 1., 2., 3. és 4. mezőn összesen 3 bábu áll, akkor a 4. mező üres;
• ha az 1., 2., 3. és 4. mezőn összesen 2 bábu áll, akkor a 2. és 4. mezők üresek;
• ha az 1., 2., 3. és 4. mezőn összesen 1 bábu áll, akkor a 2., 3. és 4. mezők üresek;
• ha az 1. és 3. mezőn álló bábuk különböző színűek, akkor elegendő azt az esetet vizsgálni, amikor X van felül és O alul;

és a fentiek analógiájára:

• ha a 7., 8., 9. és 10. mezőn összesen 3 bábu áll, akkor a 7. mező üres;
• ha a 7., 8., 9. és 10. mezőn összesen 2 bábu áll, akkor egyrészt a 7. és 9. mezők üresek;
• ha a 7., 8., 9. és 10. mezőn összesen 1 bábu áll, akkor a 7., 9. és 10. mezők üresek;
• ha az 8. és 10. mezőn álló bábuk különböző színűek, akkor elegendő azt az esetet vizsgálni, amikor X van felül és O alul.

 Ezen egyszerűsítésekkel már csak az egyes állások szöveges jelölésében kell megegyezni: soroljuk fel a mezők sorszámának sorrendjében a rajtuk álló bábukat úgy, hogy az üresen álló mezőket – például az 5. mező mindig ilyen tulajdonságú lesz – megfelelő helyet egyszerűen kihagyjuk, a 6. mezőn álló bábut/betűt viszont külön is megjelöljük egy pár függőleges elválasztó vonallal. Például a kiinduló állapot az XXX||OOO-val, a célállapot az OOO||XXX-szel jelölhető, egy közbülső lehetséges állapot pedig az XOXO|X|O:

Ez utóbbi jelölés első ránézésre több állapotot is megvalósíthat, hiszen a jobb oldali O bábut akárhová tehetjük a 7., 8., 9. és 10. mezők közül. Ugyanakkor ezek lényegében megegyeznek, hiszen az egy szem O bábu áttolása például a 7. mezőről a 8. mezőre magától értetődő. Pontosan ezért soroltuk fel a fenti egyszerűsítő megfontolásokat, hogy tényleg csak a lényegesen különböző állapotokkal kelljen egyenként is foglalkozni.

Kombinatorikai feladatnak sem hangzik rosszul meghatározni az immáron lényegesen különböző állások számát, de itt mindjárt fel is soroljuk mind a 78-at, amelyeket a gráf csúcsaiként ábrázolunk. A következő feladatunk az, hogy minden egyes álláshoz megnézzük, mely állások érhetők el belőle egyetlen lépéssel, azaz egyetlen bábu mozgatásával. Figyeljük meg, hogy csak azok a bábumozgatások lesznek érdekesek, amelyek áthaladnak az 5. mezőn. Az egymásból egy lépéssel elérhető állásokat a gráfban úgy jelenítjük meg, hogy a két csúcsot éllel kötjük össze. Egy állapotból 2,3,4 vagy 5 további állapot érhető el, azaz a gráfban bármely csúcs fokszáma ezen értékek valamelyike.

Ha a gráf elkészült, egyetlen feladatunk maradt: megkeresni a legrövidebb uta(ka)t az XXX||OOO csúcsból az OOO||XXX csúcsba.

Mivel a játék tengelyesen szimmetrikus, nem lepődünk meg azon, hogy két legrövidebb
– 17 lépéses – út is található, melyek egyikét zöld színnel jelöltük. Egy másik megoldást, ami már 19 lépést igényel, pedig kék színnel. Az ábra kattintással nagyítható.

Felmerül a kérdés, érdemes-e ennyi energiát fordítani egy ilyen egyszerű feladat modellezésébe, hiszen maga a megoldás (vagy legalábbis egy megoldás) sokkal rövidebb idő alatt megtalálható, mint felírni az összes állapotot és felrajzolni a gráfot, majd abban legrövidebb utakat keresni. Ha a feladat megoldásán kívül az alábbi kérdések és célok közül legalább egy érdekel bennünket, akkor a válasz igen:

– Hány megoldása van a játéknak? – Megmutattuk, hogy kettő 17 lépéses megoldás van. És még számos olyan, ami ennél több lépést igényel.

– Meg lehet-e 17-nél kevesebb lépéssel oldani a feladatot? – Nem, hiszen a legrövidebb utak 17 hosszúságúak.

– Elérhető-e bármelyik állásból az összes többi állás? – Igen, ugyanis a felrajzolt gráf összefüggő, azaz bármelyik csúcsból elérhető az összes többi csúcs. Ez sok játék esetében nem teljesül, vagyis az állások felsorolásakor olyanokat is felírhatunk, amelyek nem érhetők el a megadott kiindulási állásból. Ekkor a gráfunk nem összefüggő, hanem több részre esik szét és a különböző részek között nincs átmenet. Például ha a Rubik-kocka megoldott állapotában az egyik sarokkockát elforgatjuk, az megoldhatatlanná varázsolja a játékot. Kevésbé, vagy legalábbis később fog gyanút a megtréfálásra kiszemelt áldozatunk, ha utána össze is keverjük (de most már a szabályos forgatásokkal) és úgy nyújtjuk át, hogy rakja ki.

– Használható-e ez a technika más játékok megoldására, modellezésére? – Természetesen! A sorozatos mozgatáson alapuló játékok mindegyike modellezhető a fenti gráfos ötlettel,  legalábbis elméletben. Szerencsére sok esetben a gyakorlatban is kiválóan működik.
A lehetséges állások száma jellemzően jóval több, mint 78 és az állások közötti átmenetekből is lehet nagyon sok, ezért a gráf konstrukciója önmagában is programozást igényelhet. Ismert, hogy a 3×3×3-as Rubik-kocka állásainak száma 4.3×10¹⁹, ami a 78 egymilliószorosának az egymilliószorosának az egymilliószorosának nagyjából a fele. Egy ennyi csúcsot és a csúcsok között futó éleket tartalmazó gráfot kezelni egyáltalán nem könnyű. Óriási eredmény, hogy több mint három évtizedes kutatás után 2010-ben sikerült megmutatni, hogy akárhogy is keverjük össze a Rubik-kockát, legfeljebb 20 forgatásból vissza lehet állítani a kirakott állapotába. Emlékezzünk vissza: a LOGI TOLI játékban is 17 lépés kellett a megoldáshoz, pedig annak csak 78 állapota volt.

Bozóki Sándor