Kígyókockát készítünk

Kígyókockát készítünk

KígyókockaA kígyókocka (snake cube, chain cube) 27 egyforma méretű, egymáshoz képest mozgatható/forgatható kockából áll. A kockákat összeköti egy rugalmas fonal/gumi. Az első és az utolsó kocka egy-egy lapján egy-egy lyuk van. A közbenső kockák hat lapjából kettő lyukas. Fából és műanyagból is készülhetnek. Általában kétféle színnel színezettek a kockák. A cél, hogy a 27 kockát kígyózva „összehajtogatva” a kígyó (lánc) összeálljon egy nagyobb 3x3x3 méretű kockává.

A színek – a játék gyártóitól függően – nehézségi szinteket jelölhetnek (zöld, kék, piros, narancs, lila). Léteznek könnyebben és nehezebben megoldható kígyókockák. Előbbieknél többször fordul elő két egymással szemben lévő lyukas lap a közbenső kockákon, utóbbiaknál gyakoribbak az egymással szomszédos lapokon lévő lyukak. Másképpen: előbbiben több a három hosszú egyenes rész, utóbbi szinte állandóan tekereg. Általában a kocka egyik csúcsából kezdjük a megoldást, de az igazán nehéz játékok esetében a kígyó indulhat akár a kocka egyik lapjának (3×3) középső kockájától is.

Vannak olyan kígyókockák, amelyeknek több megoldása is van, azaz többféleképpen is összeállítható kockává. Ezek részletes ismertetése (típusok, gyártók, színek), a megoldások (statikusan és dinamikusan), irányokat mutató jelölésrendszer (Front, Left, Up, Back, Right, Down) elérhető Jaap Scherphuis – holland puzzle rajongó – weboldalán: Jaap’s Puzzle Page.

Kígyókocka

Olyan Java programot készítünk, amely véletlenszerű kígyókockát állít elő.

Tervezés

Szükséges egy háromdimenziós tömb adatszerkezet a kocka tárolására. Több okból is hasznos, ha a tömb mérete 5x5x5. Egyrészt így indexek 0-tól 4-ig futnak és a tömb közepén lévő 3x3x3-as kocka elemei kényelmesen – mátrixszerűen – indexelhetők 1-től 3-ig. Másrészt a tömb közepén lévő 3x3x3-as kocka minden elemére igaz, hogy egységesen van 26 db érvényesen indexelhető szomszédja. A 125 tömbelemből a széleken lévő 98 elem negatív számokkal feltölthető.

A szokásos i, j, k egységvektor rendszerben (koordináta-rendszerben) gondolkodva, i és j a képernyő síkját, k pedig a mélységet jelenti. A k-val 0-tól 4-ig „szeletelve” a tömböt, öt db négyzetet/mátrixot kapunk az alábbiak szerint. A színes tömbelemek negatív számokkal kerülnek feltöltésre, a kígyó útját határolják mindhárom irányból:

Kígyókocka tervezés

A belül lévő – fehér színű – 3x3x3-as kocka/tömb elemeit kezdőértékként célszerű 0-val feltölteni.

A szomszédos kockák kiválasztása során csak a középen lévő kocka 6 db lapszomszédját kell figyelembe venni. A középen lévő (a következő ábrán nem látszó) kocka három tengely szerinti 2-2-2 szomszédos kockája különböző színekkel jelölt.

Kígyókocka tervezés

Él- és csúcsszomszédság esetén nem tud tekeredni a kígyó. A forduláshoz/tekeredéshez legalább 3 – a kígyóban egymás utáni – kocka szükséges. Az aktuális kockának – pozíciójától függően – legfeljebb 6 lapszomszédja lehet. Ezt csökkenti, ha a kocka valamelyik csúcsban helyezkedik el, illetve menet közben is – ahogyan egyre hosszabb lesz a kígyó – folyamatosan csökken a még szabad elemek száma.

A megoldás során a belül lévő – fehér színű – 3x3x3-as kocka/tömb elemeit kell sorszámozni 1-től 27-ig, jelölve ezzel a kígyó útját. A kezdetben 0-val jelölt szabad elemek végül elfogynak.

Megállapodunk abban, hogy a kígyó az útját az (1, 1, 1) pozícióban kezdi és az 1 sorszámot kapja. Addig kell újabb szomszédos kockákat – egyesével haladva – kiválasztani módszeresen vagy véletlenszerűen próbálkozva, vagy akár visszalépéses algoritmussal is, amíg mind a 27 kiválasztásra kerül.

Megvalósítás

Létre kell hozni a háromdimenziós tömböt példányváltozóként:
int[][][] cube=new int[5][5][5];

A cubeInit() metódus kezdetben feltölti a tömb elemeit. A széleken lévő elemekbe különböző negatív értékek kerülnek, hogy jól megkülönböztethető legyen, melyik ciklus melyik pozíciókért felel. Másképpen is lehetne: például kezdetben minden elem -1, utána a belül lévők felülírhatók 0-val.

Hasznos a cubePlot() metódus, amellyel megjeleníthetők a konzolon a tömb elemei (állapota):

A getNextNeighbour() függvény egydimenziós tömbként ( int[]) visszaadja a paramétereként átvett – x, y, z koordinátával jelölt – kocka egyik kiválasztott szomszédját, amely a kígyó útját jelöli. A kiválasztás történhet módszeresen vagy véletlenszerűen próbálkozva, vagy akár visszalépéses algoritmussal is. A metódus forráskódját most nem részletezem. A metódus felelős a kígyó helyes útvonaláért, azaz a kiválasztás során a kígyó nem rekedhet meg zsákutcában, másképpen nem haraphatja meg saját magát.

A vezérlést a run() metódus végzi el az alábbiak szerint:

Addig fut a ciklus, amíg a kígyó nem tölti ki a 3x3x3-as kockát (másképpen: amíg a kígyó nem éri el a maximális hosszúságot). A tömb állapotát kezdetben és lépésenként is kiíratja a vezérlő metódus a konzolra.

Konzolos eredmény

A konzolos eredmény előállításánál fontos volt, a tömb változásait tudjuk követni. Az összes negatív szám elhagyható lehet a kiírásból, ha meggyőződtünk az implementált algoritmus helyes működéséről. Átlátva a problémát, a megoldás könnyen elállítható egy grafikus és/vagy egy irányokat mutató jelölésrendszer szerint is, például:

Kígyókocka tervezés

Hivatkozások

A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

A feladat a Java SE szoftverfejlesztő tanfolyam tematikájához kötődik. Több alkalommal is tudunk ezzel a feladattal foglalkozni, attól függően, hogy a getNextNeighbour() függvény működését hogyan tervezzük és implementáljuk:

  • A 13-16. óra: Tömbök témakör esetén a szomszédos kockák közül módszeresen – azonos sorrendben haladva a legfeljebb 6 lehetséges szomszéd közül – választjuk ki mindig az elsőt. Ekkor mindig ugyanazt az egyetlen helyes megoldást kapjuk meg.
  • A 17-28. óra: Objektumorientált programozás témakör esetén atipikusan a kivételkezelést használhatjuk vezérlésre úgy, hogy a lehetséges szomszédos kockák közül mindig véletlenszerűen választunk. Ekkor a kígyó önmagába harapását úgy előzzük meg, hogy tömb túlindexelésekor keletkező kivételt benyeljük és újrakezdjük a feladatot mindaddig, amíg találunk egy olyan megoldást, aminek lépései közben nem keletkezik kivétel.
  • Az orientáló modul 9-12. óra: Mesterséges intelligencia témakör esetén véletlenszerű kocka kiválasztási stratégiával rendelkező visszalépéses algoritmust specifikálhatunk és implementálhatunk. Ez lényegesen összetettebb feladat és mindig helyes megoldást ad több lehetséges megoldás közül.

Szólj hozzá!