A pentominók és a Penrose parketták kapcsolatáról szóló bejegyzésben szóba kerültek a Wang csempék (más elnevezéssel Wang parketták vagy dominók). Bár eredetileg nagyon komoly matematikai probléma elemzése során kezdtek foglalkozni velük, az alapötletük egészen játékos.
Vegyünk néhány színes négyzetet és ezeket pakoljuk egymás mellé úgy, hogy mindig csak azonos színek találkozzanak. Ilyen játék a színdominó is, csak Wang készletében minden elemből végtelen számú áll rendelkezésre és a teljes síkot le kell velük "parkettázni". Hogyan lehet eldönteni, hogy ez egyáltalán lehetséges-e?
Nézzük pl. a következő csempéket:
Vajon lefedhető ezekkel az egész sík? Tudjuk minden irányban akármeddig növelni a lefedett területet? (A szokásos kirakós játékokkal ellentétben itt most nem szabad sem elforgatni sem tükrözni az elemeket!)
Próbáljon találni az olvasó is egy lehetséges kirakást! Ezeket az elemeket én találtam ki, persze úgy, hogy lehetséges legyen a síkfedés a segítségükkel. De egyáltalán nem vagyok biztos benne, hogy csak egyféle megoldás létezik! Az én kirakásomban először egy nagyobb négyzetet kell összeállítani (ehhez néhány elemet többször is fel kell használni):
Ezeket a nagy négyzeteteket egymás alá lehet helyezni, mivel a tetején megegyeznek a színek az alján találhatókkal.
És egy fél oldallal eltolva egymás mellé is helyezhetők:
Ilyen egymás alá és egymás mellé rakodással akármekkora síkrészt lefedhetünk. Egy többszáz kis négyzetet tartalmazó ábra:
Azért az látható, hogy nem volt túl egyszerű megtalálni egy lehetséges módszert a síkfedésre. (Talán az olvasó ennél egyszerűbbet is észrevesz?)
Wang vizsgálatainak éppen ez állt a középpontjában:
Van-e olyan módszer (algoritmus), amivel tetszőleges csempekészletről eldönthető, hogy lefedhető-e velük a sík? A kérdést nem sikerült egyértelműen megválaszolnia, arra jutott, hogy ha az elemekkel periodikusan fedhető a sík, akkor létezik ilyen módszer. Azt gondolta, hogy minden csempekészlettel csak periodikusan fedhető a sík, így az állítást bizonyítottnak vélte. (A fenti, általam tervezett elemkészlettel is periodikusan lehet csempézni.)
Pár év múlva Berger megmutatta, hogy Wang tévedett, mert léteznek olyan csempék, amikkel lefedhető az egész sík, de csak aperiodikusan. Berger csempekészletének még 20000-nél több eleme volt, de már ő sejtette, hogy ez a szám erősen csökkenthető. Mára 13 darabra sikerült levinni a szükséges elemszámot, ezt a rekordot Karel Culik matematikus állította fel. Hogy mennyi a feltétlenül szükséges elemszám, az ma még megoldatlan probléma. De elképzelhető, hogy pár éven belül pontosan tudni fogjuk ezt a minimális számot.
Berger és Wang eredményeit összevetve pedig kiderült, hogy soha nem fogunk tudni olyan módszert adni, amellyel tetszőleges csempékről eldönthető, hogy fedhető-e velük a sík. Így ez egy megoldhatatlan probléma.
De nézzük Culik elemkészletét:
Ez tehát a ma ismert, legkevesebb négyzetből álló csempekészlet, amivel lefedhető a sík, de csak aperiodikusan.
Próbáltam keresni ábrákat, amin sok-sok Culik elemmel nagy síkrészek lefedése látható, de nem nagyon jártam sikerrel. Úgy tűnik, nem szívesen publikálják az ilyesmivel foglalkozók az ábráikat. Így nekiálltam egy programot írni, ami minél nagyobb területet lefed. Egy viszonylag egyszerű, backtrack algoritmussal egész gyorsan megszülettek az első ábrák. Egy 10 oldalhosszúságú négyzet:
Majd egy nagyobb 19×20-as:
Itt már mintha egy pillanatot gondolkodott volna a számítógép. Aztán megpróbáltam egy 50×50-es négyzetet előállíttatni a programommal, de hosszú órák alatt sem lett eredmény. Akkor megpróbáltam kideríteni, hogy hol vannak az én módszerem határai és azt tapasztaltam, hogy kb. egy 30×40-es téglalap az, amit még ki lehet várni.
Elmeséltem egy kedves kollégámnak is a problémát, fel is keltette az érdeklődését. Sokkal kifinomultabb, ravaszabb módszerrel, többszörös backtrackkel és egyéb remek ötletekkel olyan algoritmust készített, ami egy 70×70-es ábrával is szinte azonnal elkészül. Ez a rajz következik most:
Talán majd egyszer ír egy blogbejegyzést kollégám a programja érdekesebb részleteiről.
Sajnos a blogba nem lehet ennél lényegesen nagyobb képet betenni, így pedig alig látszanak a részletek. De talán ez is elég ahhoz, hogy feltűnjenek fura "ismétlődések", sorozatok.
Kedves Olvasó! Ebben a bejegyzésben nem olyan játékokról volt szó, mint korábban. Nem lesz gyakori, de néha el-el kalandozom olyan területekre is, amik "csak úgy" eszembe jutnak az ördöglakatokról. Remélem másnak is érdekesek ezek az "utazások".
