Kígyókocka készítése

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á.

Ez egy két részből álló blog bejegyzés 1. része. A blog bejegyzés 2. része itt található.

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.

Ez egy két részből álló blog bejegyzés 1. része. A blog bejegyzés 2. része itt található.

“Kígyókocka készítése” bejegyzéshez 12 hozzászólás

    • Láttam a képeket. Valahogy ide is lehet csatolni. Péter mutatta az órán, de nem írtam fel. Hihetetlenül alaposak és türelmesek voltatok. Náray Erika jutott eszembe, ő mondta egyszer: “karácsonykor minden gond nélkül lesütök két raklap mézeskalácsot, de ha kettőt fel kell díszíteni, akkor az ideg széthajít”. Lehet, hogy többet profitáltak belőle a fiúk, mint az utóbbi hetek online gimis technika óráiból.
      Én a JS forráskódot böngésztem, de egyelőre elvesztem a matekban, ahogyan rajzol, de a blogban leírt algoritmust már értem.

      Válasz
  1. Kedvet kaptam:
    – vettem egy 4*4*4-es anakondát. GoPro-val szétszedtem a biztonság kedvéért. Hasznos volt a videó, amikor elakadtam az összerakás közben. Kerestem és találtam hozzá megoldást, de nem teljesen ugyanolyan az én kockámban az útvonal, de nem jött rosszul: https://www.youtube.com/watch?v=L6A4xyyXezc
    – írtam egy getNextNeighbour() függvényt visszalépéses algoritmussal és 3*3*3 esetben jól működik. Szinte minden általános benne, de elakad, amikor megpróbáltam 4*4*4 méretben futtatni. Feltöltöttem ILIAS-ra, Sándor, megnéznéd a következő órára, mitől nem jó?

    Válasz
  2. Tudom, nem kígyókocka, de szívesen olvasnék a ti szemüvegetek keresztül a Rubik-kocka algoritmusairól. Például: CFOP kirakás. Péter: tervezitek, hogy programoztok ilyet és valamikor blogoltok róla?

    Válasz
    • Meglátjuk Nándor.

      Egy Java EE alumni hallgatónk készített pet projektként korábban Rubik-kocka kirakó GUI-t Java 3D-ben, de csak visszalépéses algoritmust implementált. A csakot erősen idézőjelesen írtam, mert ez is kellően összetett volt, de nem külön nevesített, mint amire hivatkoztál. Addig is megpróbáljuk őt meghívni valamelyik következő rendezvényünkre: mutassa be ezt a projektjét.

      Válasz
  3. Kristóf: én is próbálkoztam a visszalépéses algoritmussal. Rájöttem arra, hogy 1-2 visszalépés nem elég és elakad a megoldás. Hány visszalépéshez kellene adatokat tárolni, ami már elég lehet?

    Válasz
    • Endre: erre nincs általános képlet visszalépéses algoritmus esetén. Függ a feladattípus (kígyókocka) paramétereitől (méret: 3x3x3, 4x4x3, 4x4x4). A legrosszabb esetre is fel lehet/kell készülni. Ilyen például az:

      • ha majdnem teljesen vissza kell lépni (n-1 db-ot, sokat), de az kezdőpont marad, vagy
      • ha teljesen vissza kell lépni (n db-ot, mindet), és új kezdőpontot is kell választani.

      Több olyan feladattípus is van (nem a kígyókocka), amelynél nem garantált, hogy a visszalépéses algoritmus terminál (eredményesen vagy sem, de befejeződik).

      Válasz
  4. A 10 éves fiam megtervezte a Cubra Blue-féle kígyókockát labirintusként, 3D-ben. Ilyen lett:

    Cubra Blue-féle kígyókocka

    Keresett hozzá egy fém golyót és megkérte az apját, hogy a golyóhoz méretezve nyomtassa ki neki a nemrég beszerzett 3D nyomtatón. Szóval rendesen inspirálódott a blogból.

    Válasz

Szólj hozzá!