Ördöglakat

Kétkezi logikai játékok a könnyűtől a szinte lehetetlenig.

Friss topikok

  • Gál Péter F.: @ClownPepito: Felváltva kell lépni, és az veszt, aki már nem tud? Mondjuk, ez lehet egy 2 személye... (2018.06.05. 14:52) Szoliter – Háromszög tábla, kevés bábu
  • Gál Péter F.: @Könyveslány: Köszi, igyekszem. (2018.05.01. 11:20) Fémépítő ördöglakat
  • Gál Péter F.: @bbalint85: Ezekhez az elemzésekhez saját programokat használok. Létezik a BurrTools nevű remek me... (2018.03.04. 22:06) Hasábok félkockákból
  • Gál Péter F.: @Steve Rush: Tisztelt Steve! Nagyon örülök, hogy a matekórákra is betörnek az ördöglakatok! Szív... (2018.01.13. 20:53) Tangram készlet
  • gigabursch: Azt hittem, hogy kipörgetős az ördöglakat, de nem... (2017.09.04. 12:24) Borotvák

Wang csempék

2010.12.29. 17:38 Gál Péter F.

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

25 komment

Címkék: fejtörő 2d összerakó kombinatorikus összerakó kirakó megoldatlan probléma megoldhatatlan penrose

A bejegyzés trackback címe:

https://ordoglakat.blog.hu/api/trackback/id/tr762546535

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

khamul 2010.12.29. 21:49:42

Ha jól értem a szabályt, akkor a legelső ábránál (meg még később is), fentről a 2. sorban a bal 1.-2. csempék nem illenek össze.

hhh. 2010.12.29. 22:49:43

@khamul: bizony, jól érted a szabályt.

www.konyvline.hu · http://konyvline.hu 2010.12.29. 22:51:30

Szerintem lehetne csinálni 100x100 méretben is.

bobbafet 2010.12.29. 22:55:36

Nagyon ott van a poszt... Nagyon szerény, pedig van benne munka, gratulálok!

heliox 2010.12.29. 23:16:52

Nagyon ott van! Szuper. Inkább ez olvasom, mint a sok hülyeséget.

Ördöglakatot folyamatosan a címlapra.

rR 2010.12.30. 00:46:58

"Úgy tűnik, nem szívesen publikálják az ilyesmivel foglalkozók az ábráikat. Így nekiálltam egy programot írni, ami ..."

Na ez a nem mindennapi hozzáállás!
Én is gratulálok a remek munkához és a kiváló leíráshoz.

(off:
Ha már így leírva látjuk a hoZZÁÁLLás szót,
házi feladat: keressünk olyan magyar szavakat,
amelyekben így követi egymást 2-2-2 mással- ill.
magánhangzó.)

pi314 2010.12.30. 04:33:17

Szerintem is nagyon jó a poszt, szívesen olvasnék még ilyeneket.

EmpZoooli 2010.12.30. 06:05:17

szép ez a 70x70-es fedés, de van-e arra garancia, hogy pont ezt a részletet tartalmazza a végtelen fedés is?

Yooha · http://indafoto.hu/yooha/lego_architecture 2010.12.30. 07:23:06

A Culik-készlet miért a legkisebb, amivel lefedhető a sík? Ha pl. 1 elemű a készlet, ahol a csempe mind a 4 része fehér (vagy akármilyen színű) akkor azzal is lefedhető, nem? Vagy van valami feltétel, hogy legalább n-féle szín szerepeljen?

BKV reszelő 2010.12.30. 08:17:13

Az EII-ről kéne írni, úgyis végső határidő lesz pénteken! :)

www.eternityii.com

Gál Péter F. · http://ordoglakat.blog.hu/ 2010.12.30. 08:24:47

@khamul:
Igazad van, bocsánat.
Kijavítottam az ábrákat.
Most már nem fog látszani, hogy miről is szólt a hozzászólásod :)

Gál Péter F. · http://ordoglakat.blog.hu/ 2010.12.30. 08:26:23

@EmpZoooli:
Nagyon jó kérdés!
Fogalmam sincs! Azt hiszem, semmi garancia nincs rá.

szemet 2010.12.30. 10:26:09

Nem kell hozzá backtracking, Culik elemkészlete konstruktív megoldást ad a csempézésre:

citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.5421

Röviden a lényeg:
Egy tetszőleges x_0 = 1/3 és 2 közötti valós számból kiindulva, a következő (mindkét irányban) végtelen sorozatot kell előállítani:

x_(i+1) = x_i * 3 ha 1/3 < x < 2/3
x_(i+1) = x_i / 2 ha 2/3 < x < 2

Ehhez a sorozathoz egyértelműen hozzárendelhető egy, az egész síkot lefedő aperiodikus csempézés az ominózus 13 csempével. (Egy 13 átmenetes állapotgépen kell lépkedni a sorozatnak megfelelően, részletekért lásd a cikket. ;)

Gál Péter F. · http://ordoglakat.blog.hu/ 2010.12.30. 10:49:56

@Yooha: Az egy elemű tiszta fehér csempével is fedhető a sík, de periodikusan (is). A Culik készlettel meg csak nem periodikusan. Az ilyenek közül a legkisebb.

Gál Péter F. · http://ordoglakat.blog.hu/ 2010.12.30. 10:53:28

@szemet:
Köszönöm. Erről nem tudtam. Elolvasom, értelmezem és majd módosítani fogom a bejegyzést a cikknek megfelelően.
Egyébként már izgatott, hogy hogyan lehet bizonyítani, hogy tényleg lefedhető ezzel a készlettel a sík. De azt hittem, csak egy egzisztencia-bizonyítás létezik, nem pedig konstruktív.

sebcsaba 2011.01.01. 14:44:27

Én arra a bizonyításra lennék kíváncsi, ami azt mutatja meg hogy periodikusan nem fedhető, de aperiodikusan mégis. Ilyen jellegű bizonyítással ugyanis még nem találkoztam a matematikai tanulmányaim során.

Gál Péter F. · http://ordoglakat.blog.hu/ 2011.01.01. 14:49:39

@sebcsaba:
A szemet által belinkelt oldalról letölthető cikk ezt a bizonyítást is tartalmazza, de nem egy egyszerű, újévi olvasmány :)

Bongolo 2011.01.16. 22:11:41

@rR: Először angolt találtam: bookkeeping. De azért lett néhány magyar is, csak némelyik kicsit erőltetett: hippiillat, hobbiizzó, jukkaallergia, flottaattasé.

Bongolo 2011.01.16. 22:19:28

@EmpZoooli: Teljesen biztos, hogy ez a csempézés egy az egyben nem lehet része a teljes sík lefedésének, mert akkor sikerült volna 71x71-eset is csinálnom gyakorlatilag 0 plusz idő alatt.
Persze ha néhány sort vagy oszlopot lehagyunk róla (backtrack), úgy már valószínű tovább folytatható a végtelenig, de a kombinatorikai robbanás miatt odáig már nem jutottam el.

Bongolo 2011.01.16. 22:39:42

@szemet: Teljesen igazad van, most csináltam is olyan programot, ami nem backtrack-kel, hanem direktben generálja a csempézéseket. Néhány képet felraktam ide: kep.tar.hu/bongolo/50689063#2
A 40x40-es meg 70x70-es backtrack-kel keletkezett. A 100x100-as, a 160x90-es (jól illeszkedik a HD monitorhoz) és a 200x200-as generálva van. (A 160x90-esnél a kiinduló x=pi/2 volt 100 tizedes pontossággal.)

Csináltam 1000x1000-est is, de az már olyan nagy, hogy a kep.tar.hu be se fogadta, egyébként is szinte csak egy nagy zöld folt látszott belőle :)

Egyébként amit írtál az automatán való lépkedésről, azt szerintem csak backtrack-kel lehet csinálni, mert az automata úgy nemdeterminisztikus, hogy az output-ok is különböznek a párhuzamos ágakon. Direktben generálni a Beatty sorozat számolásával lehet. Ez elméletileg egyszerű dolog, gyakorlatilag az bonyolítja, hogy nagy pontosságú tört aritmetika kell hozzá. Én 1024 biteset csináltam, azzal max. nagyjából 1000 oldalút csempézést lehet csinálni.

Bongolo 2011.01.16. 22:44:43

@sebcsaba: Ahogy Péter írta, a fenti Culik cikk is tartalmazza a bizonyítást, de Jarkko Kari (ő találta ki az egész aritmetikai módszert, Culik egy pici módosítást adott hozzá) egyik egyetemi előadásának anyagában sokkal érthetőbben van leírva (legalábbis számomra) : users.utu.fi/jkari/tilings/part3.pdf (a PDF közepe felé keresd)

Gál Péter F. · http://ordoglakat.blog.hu/ 2011.01.17. 11:44:17

@Bongolo:
Megérne ez egy külön cikket is!
Nem akarsz írni?