Végteleníthetõ tantrix-minták

"A feladat a teljes tantrix-készlet felhasználásával olyan színhelyes elrendezés elõállítása, amely végteleníthetõ, azaz amelynek eltolt példányaival színhelyesen "kiparkettázható" a teljes sík. Ehhez az kell, hogy a minta teteje színhelyesen csatlakozzon az aljához, a bal oldala pedig a jobb oldalához."

Szobonya László, 2004. január 10.

 

Bevezetés

Nagyjából egy éve annak, hogy ez a probléma komolyan foglalkoztatni kezdett, és akkor egy intenzív hetet töltöttem azzal, hogy megpróbáljak végteleníthetõ tantrix-mintákat keresni. Miután ez elég hamar sikerült (már a legelsõ programommal is kb. fél napos munka után találtam megoldást), elkezdtem arra törekedni, hogy minél elegánsabb megoldás(oka)t találjak. Utólag visszagondolva a végeredmény megtalálása eléggé természetesnek tûnik számomra, de azért emlékszem, hogy komoly fejtörést okozott minden egyes új lépés megtétele a végleges megoldás felé. A következõ leírás tehát ennek az egy hétnek a sûrített (és remélem, az érdekesebb részleteit kiragadó) összefoglalása lesz. Elõször azonban nem árt azt tisztázni, hogy mi is pontosan a feladat:

 

A feladat a teljes tantrix-készlet felhasználásával olyan színhelyes elrendezés elõállítása, amely végteleníthetõ, azaz amelynek eltolt példányaival színhelyesen "kiparkettázható" a teljes sík. Ehhez az kell, hogy a minta teteje színhelyesen csatlakozzon az aljához, a bal oldala pedig a jobb oldalához.

 

A megoldás keresése során, ha találtam egy új, az addigiaknál elegánsabb megoldást, akkor azt szinte azonnal feltettem a sokak számára jól ismert Tantrix Fórumba, így egyrészt a többiek rögtön értesültek a fejleményekrõl, másrészt pedig nekem is komoly motivációt adott a többiek támogatása. Az ott látható képek némelyike különbözik az itt láthatóaktól, mert most, hogy elkezdtem ezt az összefoglalót írni, a programokat egységes keretbe foglaltam, ami esetleg befolyásolta futás során a keresési sorrendet, tehát ne lepõdjön meg senki, ha nem ugyanazokat a képeket találja ott és itt.

 

A módszerrõl általában

A feladatnak rengeteg megoldása van, és igen nagy szabadság mutatkozik abban is, hogy hogyan álljunk neki ezek megkeresésének. Módszerem lényege az volt, hogy elõször lerögzítettem egy 56 lapka méretû, paralelogramma vagy téglalap alakú, egyelõre üres táblát. Ennek mezõit beszámoztam 1-tõl 56-ig és ebben a táblában egyesével próbáltam a lapkákat elhelyezni. Például az elsõ próbálkozásomkor használt tábla 4x14-es paralelogramma alakú (röviden döntött) tábla volt, a következõ számozással:

1. ábra: Az elsõ módszer táblája és kitöltési terve

A módszer alapja a matematikai algoritmusokban használt mélységi keresés volt (aki nem ismeri, az se ijedjen meg, a lényegét egyszerû megérteni). A mélységi keresés úgy mûködik, hogy "mohó" módon próbáljuk kitölteni a táblát, azaz elõször az 1. helyre betesszük az 1-es lapkát, egyelõre nem elforgatva. Ezután a 2. mezõre elhelyezzük a legelsõ olyan, még fel nem használt lapkát, ami szabályosan mellé illeszthetõ, majd ezt így folytatjuk tovább. Amíg nem akadunk el, ezt folytatjuk, de elõbb-utóbb bekövetkezik még az 56. lapka elhelyezése elõtt, hogy az éppen aktuális szabad helyet már nem tudjuk kitölteni.

Ilyenkor (megint csak mohó módon) egyet visszalépünk, és az elõzõ mezõt vizsgálva vesszük az ott lévõ lapka következõ elforgatását, ha pedig ezt már teljesen körbeforgattuk, akkor vesszük a soron következõ lapkát, ami oda illik. Mindössze ezzel a két elemi lépéssel (elõre- és visszalépés) folytatjuk tovább a kitöltést. Könnyû végiggondolni, hogy így minden teljes kitöltést meg fogunk találni. Célszerû továbbá feltennünk, hogy a bal felsõ sarokban mindig az 1-es sorszámú lapka van (esetleg elforgatva), hisz ha már meglenne a keresett végtelen kitöltésünk, akkor abból ki tudnánk vágni úgy 1 periódust, hogy az 1-es lapka a bal felsõ sarokba kerüljön.

Ha nem követnénk semmilyen kitöltési elvet, hanem csak szisztematikusan végignéznénk az összes esetet, azaz az 56 lapka minden lehetséges sorrendjét (és forgásirányát!) is végigpróbálnánk, akkor évmilliárdok alatt se végeznénk (sõt…). Ezért fontos szerepe van a kitöltés hatékony megszervezésének. Nézzük, hogy tettem ezt az elsõ esetben (senki ne lepõdjön meg, ha kötelezõ helyek is fel fognak bukkanni…).

 

1. módszer (4x14-es, döntött tábla)

Ahhoz, hogy pontosabban lássuk, miképpen is megy a kitöltés, érdemes elõször végiggondolni, hogy hogyan is illeszkedjenek egymáshoz a szomszédos táblák. Vízszintesen kézenfekvõ az elhelyezés, tegyünk azonos magasságban balra és jobbra 1-1 táblát (2. ábra, szürkével). Az egymás alatt levõ táblák egymáshoz képesti elcsúsztatása már érdekesebb kérdés (2. ábra, pirossal), mert ha a kézenfekvõ elhelyezést választanánk, azaz azt, amellyel 2 egymás alatti tábla egy nagy (8x14-es) paralelogrammát alkotna, akkor nem tudnánk hatékonyan megoldást keresni, mert nem alakulnának ki automatikusan kötelezõ helyek. De miért is lenne fontos ez? Rögtön meglátjuk, ha 1-gyel eltoljuk egymáshoz képest a függõlegesen egymás alatt levõ táblákat. Ekkor a második oszloptól kezdve csupa kötelezõ helyet kell kitölteni, mint ahogy ez az ábrán is látható (az elsõ 4 lapka lerakása után az 5-ös mezõ egy kötelezõ hely, mégpedig a 2-es, 1-es, és 4-es lapkák által):

 

2. ábra: a táblák egymáshoz képesti eltolása

Kötelezõ helyek kialakításával elérjük, hogy egy adott helyre legfeljebb 6 lapkát kell odapróbálni, ellentétben az 56-tal, ami szervezés nélkül lenne, vagy a kb. 18-20-szal, ami akkor lenne, ha nem csúsztatnánk el egymáshoz képest a táblákat. (pl. eltolás nélkül az 1-es és 2-es mezõ nem 3, hanem csak 2 oldalát határozná meg az 5-ösnek). Az 5-ös lapka elhelyezése után a 6-os is kötelezõ hellyé alakul, és ez így megy végig, biztosítva azt, hogy minden lapkánál csak kevés számú elágazás legyen. Sõt, a végén az 53-56. lapkák már teljesen, mind a 6 oldalról meg vannak határozva, ami tovább csökkenti a lehetõségek számát. A program megírása és elindítása után pár másodperccel elõ is állt az elsõ megoldás, mely a 3. ábrán látható:

 

3. ábra: 4x14-es, döntött minta

 

2. módszer: (4x14-es, téglalap elrendezés)

Az eredmény, noha igen örömteli volt, mégsem tetszett igazán. Két problémám is volt vele: az egyik, hogy a 4x14-es elrendezés "túl lapos", emiatt szerintem nem túl elegáns (ennyi erõvel akár 2x28-as, vagy igen extrémnek számító 1x56-os kitöltéseket is vizsgálhattam volna), a 7x8-as minták sokkal szimpatikusabbak voltak számomra kezdettõl fogva. Viszont ez utóbbiakat lényegesen bonyolultabb is kezelni, mint azt látni fogjuk. A másik problémám pedig az volt ezzel az elsõ megoldással, hogy ha valaki szeretné például háttérnek használni a 3. ábrán látható megoldást, és 1 táblát tesz a képre, majd Mozaik módot választ, akkor az egymás alatti táblák nem jó helyre fognak kerülni, és csúnya (sõt helytelen) eredményt kapunk. Ezt a második problémát küszöböltem ki a második módszeremmel, melynél a következõ beszámozott táblát használtam:

4. ábra: 4x14-es téglalap elrendezés és számozás

Ennek az elrendezésnek nagy elõnye, hogy az egymás fölötti táblák nem tolódnak el egymáshoz képest (a 4-es pl. az 1-es és 5-ös lapka közé ékelõdik be). A gyors kitöltés érdekében az elõzõhöz képest felcseréltem a 2. és 3. sor kitöltési sorrendjét, amivel megint elértem, hogy az elsõ 4 lapka lerakása után a többi lapka más kötelezõ helyre kerüljön. Futtatás után az elsõ kiadódó megoldás a következõ volt:

5. ábra: 4x14-es, álló minta

Ez a trükk minden további módszeremben alkalmazható, úgyhogy ezentúl nem szükséges az "álló" megnevezés, mert minden további megoldás ilyen lesz, azaz mindegyik alkalmas pl. háttérképnek.

 

3. módszer: (7x8-as téglalap elrendezés)

Ezen a ponton megvolt tehát kétféle 4x14-es minta, de még mindig nem éreztem úgy, hogy a probléma meg lenne oldva, hiszen, mint mondtam, egy 7x8-as megoldást sokkal elegánsabbnak tartottam volna. Úgyhogy meg is tettem az elsõ lépést ezen az úton, elõször nem sok sikerrel… 

Az elõzõ módszert futtattam változtatás nélkül, csupán a tábla méretét átírva, azaz a következõ táblát próbáltam kitölteni:

 

6. ábra: 8x7-es kitöltõtábla

Ezzel a táblával az volt a gond, hogy 3 nap alatt nem találtam vele egyetlen megoldást se. Futott volna tovább is, csak éppen nem volt türelmem megvárni. Ez a kísérlet tehát egyelõre kudarcot vallott, de kiindulópontja volt a javított és sikeresebb keresési módszereimnek. A 2. és a 3. módszer között az lehet a (méretekbõl adódó) lényeges különbség, hogy itt az elsõ 8 lapka az, ami sok elágazást okoz az elõzõ módszer mindössze 4 lapkájához képest, amivel megnõ a keresés futásideje. És emellett az is megnehezíti egy megoldás megtalálását, hogy a 49-52. lapkák már 4, míg az 53-56. lapkák már mind a 6 oldalról meg vannak határozva, ami azt eredményezi, hogy igen kis gyakorisággal jutunk csak el az 55., vagy valami csoda folytán az 56. lapkáig (megjegyzem, hogy azért a 3 nap alatt, amíg ez a verzió futott, kb. 10 percenként talált olyan elrendezést, amikor mindössze az utolsó lapka nem stimmelt, de egy olyan se akadt, amikor mind az 56 a helyén lett volna). A 3 napos futtatás a munkahelyem egyik ritkán használt 1600 MHz-es gépén történt, úgyhogy közben tudtam haladni a módszer csiszolásában, így született meg a

 

4. módszer: (7x8-as szimmetrikus módszer)

A nagy számításigényen úgy próbáltam segíteni, hogy gondolatban vízszintesen középen félbevágtam a táblát, és egy fél készletbõl próbáltam meg a felsõ részt kitölteni, majd a maradék fél készletbõl ennek mintájára az alsó felét. Az volt az ötletem, hogy az ábra felsõ felét abból a 28 lapkából rakom ki, melyekben egyszerre szerepel kék és sárga is. Ezután a felsõ ábra minden kék ívét pirosra és viszont, valamint minden sárga ívét zöldre (és viszont) cserélem ki, és a kapott táblát a felsõ rész alá teszem. Ekkor alulra pont a készlet maradék fele fog kerülni, ezt könnyen végig lehet gondolni. Ilyenkor figyelni kell viszont arra, hogy a 4x7-es tábla kitöltésének keresésénél az alsó "kilógó" ívvégek színének nem megegyeznie kell a felsõ kilógó végek színével, hanem ezeknek éppen színpároknak kell lenniük, ezáltal lesz színhelyes a végsõ kapcsolódás (nem mondtam, de a kitöltési tábla ugyanaz, mint amit a 2. módszernél (4x14-es, álló) használtam, csak 56 lapka helyett mindössze 28-at használva).

Amikor anno ezt a verziót megírtam, akkor került bele egy kisebb hiba, ami miatt kihagytam néhány megoldás vizsgálatát. Emiatt elõször nem is találtam megoldást. Csak úgy sikerült egy - az itt láthatónál kevésbé szimmetrikus - mintát elõállítanom, hogy amikor 27 lapkát sikerült elhelyeznem, csak a 28.-at nem, akkor megpróbáltam azt a párjával pótolni, és ez elég hamar sikerült is. Azonban az azóta kijavított programot újrafuttatva fél percen belül megszületett ez a minta (érdekessége, hogy nincsenek benne vonalak, minden színbõl hurkok alakultak ki - színenként 4, illetve 5 darab):

 

7. ábra: 8x7-es, szimmetrikus minta

 

5. módszer: (7x8-as, "extraszimmetrikus" módszer)

Az elõzõ módszerbõl nyert megoldás már tetszett, de ekkor már vérszemet kaptam, és nem akartam itt megállni. Ez az 5. módszer lett aztán a végleges, melyben minden szín teljesen egyenrangú, azaz a megoldásban teljesen azonos alakú mintázatot követnek a színek. Véleményem szerint az ebbõl a megoldásból kapott minták a legszebbek, ráadásul messze ez a program bizonyult a leggyorsabbnak, úgyhogy miután lefutott, befejezettnek tekintettem a feladat megoldását. De nézzük, hogyan is mûködik ez az utolsó módszer (azután kedvenc mintám következik):

8. ábra: A színeltolás ötlete

A 8. ábrán az ötletem lényege látható, amit színeltolásnak neveztem el. Egy lapka színeltoltját úgy kapom, hogy minden ívének a színét "eltolom" a következõ színre. Elvileg többféle sorrend választható, én a piros → sárga → kék → zöld → piros sorrendet választottam. Ilyenkor bármely lapkából kiindulva 4 lépés után visszajutunk önmagába (8. ábra), ezenfelül igaz az is, hogy mondjuk az elsõ 14 lapkát véve (ezek azok, melyekben nincs zöld ív), és ezeket négyszer eltolva a teljes készlet minden lapkáját pontosan egyszer fogjuk megkapni. Nézzük ezek után, miképpen kerestem "extraszimmetrikus" mintákat:

 

9. ábra: az "extraszimmetrikus" minták táblája

Vettem egy mindössze 2x7-es méretû táblát, és ezt próbáltam a szokásos módon kitölteni. Két dolgot kivéve: az egyik, hogy a 2x7-es minta alja ne ugyanolyan legyen, mint a teteje, hanem éppen a színeltoltja. A másik dolog pedig, hogy nem 14 lapkát próbáltam felülre elhelyezni, hanem mind az 56-ot, viszont ha egy lapkát letettem a táblára, akkor az egyszeres, kétszeres illetve háromszoros színeltoltját is kiszedtem a még felhasználható lapkák közül. Visszalépésnél pedig értelemszerûen nem csak a visszalépésnél felszabadult lapka lett újra felhasználható, hanem mindhárom színeltoltja is.

Ezáltal mire kitöltöttem a felsõ táblát, éppen minden lapka elfogyott. A felsõ 2x7-es tábla egyszeres, kétszeres és háromszoros színeltolásával pedig rendre megkaptam a 2., 3. és 4. negyedét a táblának. Így kis számolással (mindössze 14 lapka nyomon követésével) könnyen tudtam találni (négyszeresen) szimmetrikus kitöltéseket.

 

10. ábra: kedvenc mintám, egy dinó

 

Ezt a programot már lefuttattam végig, és a végén, kb. 10 másodperc alatt 3742 helyes kitöltést (és ezek tükörképeit) kaptam eredményül. Mivel ez kezelhetetlenül nagy szám, ezért tovább specializáltam a keresést: csak olyan megoldásokat tartottam meg, melyeknél a színek periódusonként 42 lapkás (azaz maximális, egy adott színbõl minden lapkát tartalmazó) hurkokat alkotnak. Ezzel a számomra érdekes megoldások száma lecsökkent 224-re (és ugyanennyi tükörképre). Ezek között már nem tudtam különbséget tenni szabályossági alapon, ezért a 10. ábrán kedvencemet, a dinoszauruszt láthatjátok (a jobb láthatóság érdekében 2x2 periódust megjelenítve). Ezzel az ábrával végére is értem összefoglalómnak, remélem, nem volt túlságosan technikai jellegû ahhoz, hogy emellett szórakoztató is legyen. És ha bármi megjegyzésed, ötleted van a problémával kapcsolatban, írj!

 

Szobonya László, 2004. január 10.