Ördöglakat

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

Friss topikok

  • Gál Péter F.: @b.pal: Elég hosszú a zsinór? A fotó csalóka, próbáld hosszú zsinórral! (2018.11.29. 10:04) Mozgó csomó – filléres ördöglakat
  • 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

Egymillió £ egy ördöglakatért? - Eternity 1.

2011.07.16. 10:39 Gál Péter F.

Van aki hajlandó több mint 300 millió forintot fizetni egy ördöglakat megoldásáért? Van aki képes kockára tenni az összes vagyonát és a többszáz éves családi örökséget, annyira bízik abban, hogy a feladványát nem tudja senki megoldani? És vannak akik hónapokig éjt-nappallá téve dolgoznak egy teljesen bizonytalan, elsőre lehetetlennek tűnő vállalkozás sikeréért? Szerencsére vannak ilyen emberek! Ezért (is) szép és érdekes ez a (játékos) világ.

De lássuk egy kicsit részletesebben a történetet!

  

Az összerakós logikai játékoknak egy nagyon kedvelt csoportját alkotják a kombinatorikus összerakók. E játékok elemei valamilyen viszonylag szabályos alakzatok egymáshoz illesztésével keletkeznek. A pentominók négyzetekből állnak,a hexiamondok háromszögekből, a tetrahexek pedig hatszögekből. De nemcsak szabályos sokszögekből lehet érdekes elemeket készíteni, a "vonalzós" összerakó pl. 30-60-90 fokos háromszögekből épül fel. Ez utóbbi már igen nehéz játék, pedig csak 14 elemből áll. Javaslom az olvasónak, hogy próbálja ki, jobban át tudja érezni a most ismertetendő játék bonyolultságát is.

Három "vonalzóból" 14-féle alakzat állítható össze. Négyből 64-féle, ötből 237-féle..., nyolcból pedig 17705-féle. Ez azért kicsit sok egy játékhoz :)

Christopher Monckton - angol nemes, politikus, újságszerkesztő és főleg játékmániás - érdeklődését is a vonalzókból álló alakzatok keltették fel. Ő nem engedélyezett minden alakzatot, figyelembe vette a gyártási nehézségeket és a rakosgatás közbeni kellemetlenségeket. Így kizárta a nagyon hegyes elemeket (vagyis amiknek 30 fokos szögük van) és a sérülékenyeket is (ahol csak a rövid oldalon érintkeznek a háromszögek), viszont 12 háromszöget is engedett összeerősíteni. Ezeknek a feltételeknek is több mint 50 ezer alakzat felelt meg.

Két viszonylag egyszerű példa közülük:

Ugyanez a két elem rajzban, hogy jobban látszódjon a háromszögek elhelyezkedése:

Monckton pontosan tudta, hogy 50000 elemből nem lehet játékot készíteni. Azt is felmérte, hogy érdemes valami "szép", esetleg szabályos alakzatot kitűzni célul. Így esett a választása egy viszonylag nagy 12 szögre:

Ennek területe 2508 háromszögnyi. Bár pontosan nem tudjuk Monckton módszerét, de valószínűleg próbálgatással választotta ki a több mint 50000-ből azokat az elemeket, amikkel kirakható a 12-szög. Arra ügyelt, hogy nagyon egyszerűek ne legyenek köztük, így se tengelyes-, se forgásszimmetrikus sokszögeket nem válogatott be. Így született meg az Eternity puzzle 209 eleme.

Moncton némileg jártas volt a játékmegoldó programok terén is. Tudta, hogy egy viszonylag egyszerű program kb. 20-25 elemből álló kirakóval birkózik meg egy PC-n pár nap alatt. Nagy gépen, vagy hálózatra kapcsolt rendszerekkel 50-60 sőt, 100 elemű játékokat is oldottak meg. Ennél nagyobb, hasonló játékmegoldások nem voltak ismertek akkoriban. Jogosan gondolta, hogy a 209 elem hatalmas kihívás lesz akár a legmodernebb számítógépes rendszereknek is.

Gondolt egy merészet és felajánlott 1 millió angol fontot annak, aki egy éven belül először megoldja a játékot. Azt hitte, hogy nem kockáztat sokat.

Rengetegen próbálkoztak a kirakással. Sokan megvették a boltban kapható változatot és bíztak benne, hogy próbálgatással is eredményre jutnak. Hamarosan játékos körök alakultak, internetes fórumokon osztották meg tapasztalataikat egymással. Később bekapcsolódtak a programozók majd a matematikusok is.

Ők nem akartak belenyugodni a játék megoldhatatlanságába, meg persze a pénzdíj is nagy vonzerőt jelentett. Hamar rájöttek, hogy a szokásos megoldó algoritmusokkal nem érhetnek el sikert, de sok speciális tulajdonságát fedezték fel a játéknak. Például rájöttek arra a meglepő tényre, hogy Monckton túl nagyot akart, túl sok elemet használt. Sokkal nehezebb lett volna a játék 100-nál csak kicsit több elemmel. Ennek a furcsa ténynek az az oka, hogy általában egy nagyobb játéknak több megoldása is van. Ha az elemeket véletlenszerűen helyezzük fel a táblára, nagyon kicsi az esélye, hogy pont egy megoldást kapjunk. Ha több megoldás is létezik, kicsit nagyobb az esély. Kiszámolható, hogy az elemek számának növekedésével egy ideig csökken a véletlen lerakásokhoz képest a megoldások aránya, majd egy minimum elérése után újra nőni kezd. A 209 elem bőven túl van ezen a minimumon. A sok elemből viszonylag egyszerű kisebb területeket lefedni, ezeket a részmegoldásokat eltárolni és később ilyen részmegoldásokból összerakni az egészet. Még sok, a valószínűségszámítást erősen használó ötlet segíthet megoldani a megoldhatatlannak hitt feladványt. Viszonylag hamar találtak olyan „majdnem megoldásokat”, amikor 207 majd 208 elemet sikerült lerakni, ekkor már többen érezték, hogy Moncktonnak hamarosan mélyen a zsebébe kell nyúlnia.

Végül két cambridge-i matematikus, Alex Selby és Oliver Riordan 7 hónap elméleti és számítógépes munkával rábukkant egy megoldásra. Így az első határidő lejárta előtt elnyerték a pénzdíjat. Érdekes, hogy utánuk pár héttel egy német matematikus Günter Stertenbrink is talált egy másik megoldást. Sőt, mint később kiderült, ő már egy hónappal a játék megjelenése után eljutott 208 elem lerakásáig, de eredményeit, módszerét titokban tartotta.

Monckton becsületére legyen mondva, tartotta szavát. El kellett adnia kastélyát, de kifizette az egymillió fontot. Annyira nem szegte kedvét a kifizetett hatalmas összeg, hogy új, még nagyobb pénzdíjas játék kifejlesztésébe kezdett. Ennek a játéknak, az Eternity 2-nek a megalkotásába már elméleti matematikusokat is bevont, úgyhogy valószínűleg ez tényleg sokkal nehezebb. Az is bizonyítja, már több mint három éve piacon van, egyelőre mégsincs megoldása.

Az Eternity 1. megoldását közzétette Selby és Riordan, ennek alapján készült el az én változatom. (Az elemek szerzői joggal védettek, csak Monckton engedélyével árusíthatók!)

Még úgyis féltem nekiállni a kirakásnak, hogy rendelkeztem a megoldás rajzával. Nagyon-nagyon-nagyon nehéz beazonosítani az elemeket és megtalálni a végső helyüket. Végül két (nagyjából) önként jelentkező segítő nekiállt és 4 órás munkával kirakta a 12 szöget!

Munka közben:

Az utolsó elem behelyezése közös erővel:

És kirakva:

 

 

6 komment

Címkék: fejtörő eternity 2d összerakó kombinatorikus összerakó kirakó megoldhatatlan

A bejegyzés trackback címe:

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

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.

Gál Péter F. · http://ordoglakat.blog.hu/ 2011.07.21. 10:21:29

@Zsiros László Róbert:
Szerintem is :)

És örülök, hogy Te is olvasod a blogot!

G. M. E. · http://duplapluszjo.hu 2011.11.07. 21:19:26

Amit boltban árulnak, azon van valami minta az egyik oldalon, mint a hagyományos puzzlökön?

Gál Péter F. · http://ordoglakat.blog.hu/ 2011.11.07. 21:24:09

@Gáspár Merse Előd: Dehogy! Az is egyszínű.
A minta nagyon megkönnyítené.
De talán már nem is árulják.

G. M. E. · http://duplapluszjo.hu 2011.11.08. 07:00:17

Persze a feladvány kitűzése előtt nem volt. De utána rakhattak volna rá valami szépet.

Galopp 2013.12.06. 17:03:06

Ebből parketta mutatna igazán szépen. Mondjuk max 3 kicsit különböző színű elemekből.