Feladat

Négy darab színes (egy lapon egy szín, 1x1x1 méretű) kockát helyezzük el úgy egy 4x1x1 hasábban, hogy a hasáb bármelyik 4x1 hosszú lapján 4 különböző színt lássunk.

Zirc, 2008. Karácsony

Így néz ki kiterítve a kocka (önkényes jelölés):

Számokkal:

1
5 2 6
3
4

Irányokkal:

T
W S E
B
N
Tehát ha összerakom, a kezembe veszem, és csak egyik lapját látom, akkor:

Színek:

Ez a négy kockánk van:

A színek sorrendje a fent leírt jelöléssel a számok sorrendjében:
  1. Z K Z S K P
  2. P S K Z S S
  3. S K Z P Z P
  4. Z S P P S K
Remélem jól írtam fel.

Megoldás

Feltevések

A kockák sorrendje indifferens a színkülönbözőségi probléma megoldása szempontjából, mert a 4 db kocka 4! (=24) permutációja 4!-szorosára növelné az állapotteret is és a megoldások számát is. Az ésszerűség kedvéért én csak azt vizsgáltam, hogy milyen megoldások vannak, ha a kockák sorrendje a hasábban megegyezik a fenti sorrenddel (1.-4.).

Tegyük fel, hogy a kockák úgy helyezkednek el, hogy E és W lapjukkal érintkeznek egymással, illetve ezek vannak letakarva. Tehát majd a T, B, S, N lapokat kell vizsgálni, hogy itt különböző színek legyenek.

Feltételezve, hogy a lapok egyedileg azonosíthatók, egy kockát 24 féleképpen tehetek le magam elé. Erre kétféleképpen is rájöhetünk (3. akinek van türelme, próbálja ki :) ):

  1. Ha leteszem az asztalra, a 6 lap bármelyike lehet fölül (vízszintesen), és bármelyik van fölül, 4 különböző lap nézhet felém (függőlegesen). 6x4=24
  2. Ha az egyik sarkát nézem, akkor 3 lapot látok. 8 sarok van és 3 féleképpen lehet csavarni ezt a nézetet. 8x3=24
Ezek eddig tények, de mi ebben a feltevés? Hát az, hogy én feltettem, hogy mind a 4 kocka mind a 24 állapotát vizsgálni kell. Így 24^4 = 331776 eset a teljes állapottér.

Persze így kijönnek olyan megoldások, amik bizonyos szempontból ekvivalensnek tekinthetők, de ez felfogás kérdése.

  1. Pl. lehet ekvivalensnek tekinteni két megoldást, ha úgy eljuthatunk egyikből a másikba, hogy a hasábot az 1x1 lapok középpontjait (átlóinak metszéspontjait) összekötő egyenes tengelyénél elforgatjuk 90 fok többszörösével. Pl. egy 180 fokos fordulatnál, ami fönt volt, az lentre kerül. Ha ezeket ekvivalensnek tekintjük, az 1/4-re ritkítja a kapott megoldások számát.
  2. Pl. azt is tekinthetjük ekvivalensnek, ha minden egyes kockát elforgatunk 180 fokkal úgy, hogy a vizsgált (4x1) lapok felé mutatott színek ne változzanak, csak ezek közül kettő helyet cseréljen. Ha ezeket ekvivalensnek tekintjük, az 1/2-re ritkítja a kapott megoldások számát.
Ha az előbb említett mindkét transzformációt úgy tekintjük, hogy ezek kombinációval egyik megoldásból a másikba jutunk, és e két megoldást ekvivalensnek tekintjük, akkor 1/2 x 1/4 = 1/8 -ra csökkentettük a megoldások számát. Az egyszerűség kedvéért a programom nem vizsgálja, hogy egy korábban talált megoldással (az előbb leírt felfogással) ekvivalensnek tekinthető megoldásra jutott-e, szóval 8x annyi megoldást talál, amint amennyi akkor van, ha azt mondjuk, hogy a fenti kétféle forgatás kombinációjával nem juthatunk egyik megoldásból új megoldásra. Tehát felteszem, hogy ezek NEM ekvivalens megoldások.

Technológia, módszer

Néhány osztályból álló, teljesen OO Java megoldás készült. Bactrackre (és semmilyen állapottér vágásra) nincs szükség, mert egy számítógépnek nagyon olcsó a teszteset (forgassuk be a kockákat a lehetséges esetek valamelyikébe) előállítás és a vizsgálat (T, B, S, N lapok mindegyikén 4 különböző szín van-e) is. Minden egyéb trükközés, elővizsgálat csak bonyolítaná, és valószínűleg lassítaná.

És végre, a várva várt megoldás...

S P K K Z Z | K S P Z S S | Z Z S P K P | P K Z S P S | 
S K K P Z Z | K Z P S S S | Z P S Z P K | P S Z K S P | 
K P S K Z Z | P S K Z S S | S Z Z P P K | Z K P S S P | 
K K S P Z Z | P Z K S S S | S P Z Z K P | Z S P K P S | 
K K P S Z Z | Z P S K S S | P S Z Z P K | S Z K P S P | 
K S P K Z Z | Z K S P S S | P Z Z S K P | S P K Z P S | 
P K K S Z Z | S P Z K S S | Z S P Z K P | K Z S P P S | 
P S K K Z Z | S K Z P S S | Z Z P S P K | K P S Z S P | 
331776 eset megvizsgalva
8 megoldas
63 millisec alatt futott le.

Szúrópróba szerű ellenőrzés

Nézzük pl. a tetejét (T - 1. betű) az első esetnek: S K Z P - különbözőek, jó. Nézzük pl. az alját (B - 3. betű) az első esetnek: K P S Z - különbözőek, jó

Az ellenőrzéssel nem foglalkoztam sokat, remélem, hogy lehetséges helyzetbe vannak forgatva a kockák.

Vélemény

Szóval ez egy elég rohadék feladat egy embernek. Lehet, hogy némi intuícióval, heurisztikával lehet ügyeskedni, de ha csak a 41472 negyedét (mert valaki mázlista vagy ráérez), azaz 10368 esetet kell ellenőrizni és mondjuk átlag 2 másodperc alatt beforgatunk és ellenőrzünk egy esetet (ez azért nem könnyű), az is majdnem 6 óra kemény munka!