Java forráskód - címke - Oldal 13 a 13-ből

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

2023. január 1.2017. március 26. Szerző: Kaczur Sándor

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

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:

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.

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

private void cubeInit() {

//k=0, k=4

for(int i=0; i<=4; i++)

for(int j=0; j<=4; j++) {

cube[0][i][j]=-1;

cube[4][i][j]=-1;

}

//i=0, i=4

for(int j=0; j<=4; j++)

for(int k=1; k<=3; k++) {

cube[k][0][j]=-2;

cube[k][4][j]=-2;

}

//j=0, j=4

for(int i=1; i<=3; i++)

for(int k=1; k<=3; k++) {

cube[k][i][0]=-3;

cube[k][i][4]=-3;

}

//kocka belseje

for(int k=1; k<=3; k++)

for(int i=1; i<=3; i++)

for(int j=1; j<=3; j++)

cube[k][i][j]=0;

cube[1][1][1]=1;

}

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

private void cubePlot(String message) {

System.out.println(message);

for(int i=0; i<=4; i++) {

for(int j=0; j<=4; j++) {

for(int k=0; k<=4; k++)

System.out.print(String.format("%3d", cube[j][i][k]));

if(j<4)

System.out.print(" |");

}

System.out.println();

}

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:

private void run() {

cubeInit();

cubePlot("1. lépés:");

int count=1, i=1, j=1, k=1;

while(count<27) {

int[] rN=getNextNeighbour(i, j, k);

i=rN[0]; j=rN[1]; k=rN[2];

count++;

cube[i][j][k]=count;

cubePlot(count+". lépés:");

}

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

1. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

2. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

3. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

4. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

5. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

6. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 0 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

7. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 0 0 -3 | -3 0 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

8. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 0 0 -3 | -3 8 0 0 -3 | -3 0 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

9. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 0 0 -3 | -3 8 0 0 -3 | -3 9 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

10. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 0 0 -3 | -3 8 0 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

11. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 0 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

12. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 0 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

13. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 0 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

14. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

15. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 0 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

16. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 0 0 -3 | -3 3 16 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

17. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 0 0 -3 | -3 2 17 0 -3 | -3 3 16 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

18. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 0 -3 | -3 2 17 0 -3 | -3 3 16 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

19. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 0 -3 | -3 3 16 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

20. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

21. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

22. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 0 -3 | -3 4 15 22 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

23. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 0 -3 | -3 5 14 23 -3 | -3 4 15 22 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

24. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 24 -3 | -3 5 14 23 -3 | -3 4 15 22 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 0 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

25. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 24 -3 | -3 5 14 23 -3 | -3 4 15 22 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 25 -3 | -3 8 11 0 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

26. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 24 -3 | -3 5 14 23 -3 | -3 4 15 22 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 25 -3 | -3 8 11 26 -3 | -3 9 10 0 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

27. lépés:

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 1 18 19 -3 | -3 2 17 20 -3 | -3 3 16 21 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 6 13 24 -3 | -3 5 14 23 -3 | -3 4 15 22 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -3 7 12 25 -3 | -3 8 11 26 -3 | -3 9 10 27 -3 | -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -2 -2 -2 -2 -2 | -1 -1 -1 -1 -1

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:

Hivatkozások

Hogyan lehet megoldani az egyik kígyókockát? (képek+videó)
A feladat általános megoldhatóságának izgalmas levezetése (gráfelmélet, Hamilton-kör):
Bent Hamilton Cycles in d-Dimensional Grid Graphs (2002),
Finding a Hamiltonian Path in a Cube with Specified Turns is Hard (2013)
Haskell nyelvű megoldás: Solving the Snake Cube Puzzle in Haskell
Aki online vásárolna kígyókockát webáruházakból:
Fakopáncs, Amazon1, Amazon2, AliExpress
JavaScript kígyókocka
Aki saját maga barkácsolna kígyókockát
4x4x3-as kígyókocka
4x4x4-es kígyókocka (anakonda)

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

CHOO + CHOO = TRAIN

2023. július 5.2017. február 5. Szerző: Kaczur Sándor

Most nem a híres kisvonatról van szó, hanem egy ismert kriptoaritmetikai feladványról. Ebben a feladattípusban egyszerű matematikai műveletek szerepelnek és a különböző betűk különböző számjegyeket jelölnek. Általában többféleképpen megoldhatók: intuíció, ötlet, módszeres próbálkozás, következtetés, kizárás vagy klasszikus behelyettesítés. Ha van megoldás és meg is találunk egyet, akkor a következő kérdés az, hogy van-e még, illetve összesen hány megoldás van?

Íme a feladat:

Érdemes minden megoldás során figyelembe venni a minden számjegyet 0-9-ig végigpróbáló lépések helyett legalább az alábbi öt feltételt:

C >= 5, hiszen CHOO olyan négyjegyű szám, aminek a kétszerese ötjegyű szám,
T = 1, mivel két négyjegyű szám összege 10000 < TRAIN < 20000 (ebben az esetben),
O >= 6, hiszen maradéknak képződnie kell, mert I és N különbözik,
2 <= N < I és
I >= 3 és szintén a maradékképződés miatt.

Esetleg még tovább gondolkodva, felfedezhetünk egyéb összefüggéseket, illetve kizárhatunk egyéb értékeket, így jelentősen csökkenthető egy-egy Java implementáció lépésszáma.

1. megoldás

Ez adatszerkezet nélküli megoldás, így eléggé összetett feltétellel valósul meg a művelet teljesülése (megfelelő helyiértékek használatával) és a különbözőségek vizsgálata.

public static void chooChooTrain1() {

for (int c = 5; c <= 9; c++)

for (int h = 0; h <= 9; h++)

for (int o = 6; o <= 9; o++)

for (int r = 0; r <= 9; r++)

for (int a = 0; a <= 9; a++)

for (int i = 3; i <= 9; i++)

for (int n = 2; n < i; n++)

if((1000*c+100*h+10*o+o)*2 == 10000+1000*r+100*a+10*i+n &&

c!=h && c!=o && c!=1 && c!=r && c!=a && c!=i && c!=n &&

h!=o && h!=1 && h!=r && h!=a && h!=i && h!=n &&

o!=1 && o!=r && o!=a && o!=i && o!=n &&

r!=1 && r!=a && r!=i && r!=n &&

a!=1 && a!=i && a!=n &&

i!=1 && i!=n &&

n!=1)

System.out.println(

" "+c+h+o+o+"\n+ "+c+h+o+o+"\n------\n "+1+r+a+i+n+"\n");

}

2. megoldás

Itt az ellenőrzési feltétel egyszerűbb, mert a különbözőség/egyediség tesztelését áthárítottam a halmazszerűen működő HashSet generikus kollekcióra, építve annak beépített képességére.

public static void chooChooTrain2() {

HashSet<Integer> hs=new HashSet<>();

for (int c = 5; c <= 9; c++)

for (int h = 0; h <= 9; h++)

for (int o = 6; o <= 9; o++)

for (int r = 0; r <= 9; r++)

for (int a = 0; a <= 9; a++)

for (int i = 3; i <= 9; i++)

for (int n = 2; n < i; n++) {

hs.add(c); hs.add(h); hs.add(o);

hs.add(1); hs.add(r); hs.add(a); hs.add(i); hs.add(n);

if(hs.size()==8 &&

(1000*c+100*h+10*o+o)*2 == 10000+1000*r+100*a+10*i+n)

System.out.println(

" "+c+h+o+o+"\n+ "+c+h+o+o+"\n------\n "+1+r+a+i+n+"\n");

hs.clear();

}

Mit gondolsz, melyik megoldás hajtódik végre gyorsabban? Miért?

Mivel a két megoldásnál a ciklusok szervezése megegyezik, így a használt adatszerkezet dönt (hiszen annak konstrukciós és szelekciós, azaz karbantartási műveletei vannak). Az 1. megoldás a gyorsabb, mert nem használ adatszerkezetet. A 2. megoldás lényegesen lassabban fut, mert a generikus kollekció műveletei miatt az automatikus szemétgyűjtő tevékenység erősen igénybe vett. A különbség nagyságrendileg 15-szörös.

A feladatnak két megoldása van: 5466 + 5466 = 10932 és 5488 + 5488 = 10976.

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

Akinek kedve támadt, lásson hozzá hasonló feladatokhoz:

SEND + MORE = MONEY
6 * KAYAK = SPORT
2 * MOST = TOKYO
CROSS + ROADS = DANGER
FORTY + TEN + TEN = SIXTY
mathsisfun.com – Algebra Puzzles
cryptarithms.awardspace.us – Crack-a-Puzzle Online – Puzzles Menu
www.campusgate.co.in – Cryptoarithmetic problem with explanation

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalomhoz, illetve a 21-24. óra: Objektumorientált programozás, 2. rész alkalomhoz kötődik.

Euler állatos feladata

2023. január 1.2017. január 2. Szerző: Kaczur Sándor

Valaki sertést, kecskét és juhot vásárolt, összesen 100 állatot, pontosan 100 aranyért. A sertés darabja 3 és fél arany, a kecskéé 1 és egyharmad, a juhoké fél arany. Hány darabot vehetett az egyes állatokból?

A lépésszám 252.

Akinek még van kedve tovább próbálkozva csökkenteni a lépésszámot, íme néhány ötlet:

Az s maximális értéke könnyen csökkenthető 16-ra, ekkor a k legfeljebb 60-3*s és j adódik, így egyszerűsíthető lehet a 6*s+5.0/3*k==100 feltétel, valamint az eredmény kiírásánál j helyett 100-s-k. Ekkor a lépésszám 88.
Az s osztható öttel, így a ciklusa megszervezhető for(int s=5; s<=15; s+=5)-ként, amivel a lépésszám 14.
A k is adódik (100-6*s)*3/5.0-ként és a módosított k==Math.round(k) feltétellel a lépésszám 3.

Próbálkozhatunk egy kis matematikával is!

Néhány ötlet:

Egyszerű műveletekkel könnyen adódik, hogy 21s+8k+3j=600 és j=100-s-k, illetve s<600/21 és k<600/8-21s. Ezeket az összefüggéseket felhasználva is írhatunk programot.
Klasszikus diofantoszi (diofantikus) többismeretlenes algebrai egyenletrendszerként is megoldhatjuk a feladatot.
Egyebek: következtetés, kizárás, egyenlőtlenségek, becslések, kongruencia, szorzattá (hatvánnyá) alakítás, illetve az sem rossz ötlet, hogy „ránézek és kész”.

Végül a feladat megoldásai

5 db sertés és 42 db kecske és 53 db juh
10 db sertés és 24 db kecske és 66 db juh
15 db sertés és 6 db kecske és 79 db juh

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

Ez a feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek, illetve 9-12. óra: Metódusok, rekurzió alkalmához, valamint minden tanfolyamunk orientáló moduljának 1-4. óra: Programozási tételek alkalmához kapcsolódik.