Van elte informatikai tanar ismerosom, de semmit nem tud arrol, hogy az eternityII-n ennyire nagy felhajtas lett volna. Esetleg ha a nyugdijba ment tanarra adnanak olyan utalast, amibol aki ismeretes arra az felismeri de mas nem, akkor kiderulhetne, hogy tenyleg ment-e nyugdijba (akarmilyen okbol). Mas kerdes, hogy en konkretan annak az elteteam nevu nicknek nem hiszem el, hogy o eppen ismerne megoldast...
Igen, én is így értettem. De ez még nem elégséges, csak szükséges feltétele a megoldásnak. Elégseges akkor lesz, ha megfelelően tudjuk kiszűrni a hibás ágakat. Szerintem Te is ezt írtad, úgyhogy kutassuk tovább a lehetőségeket, függetlenül attól, hogy esetleg már kirakhatta valaki, mert hát ennek is meg van az esélye. De ezt vagy nem szeretném, vagy nem akarom elhinni.
Sajnos kevés ELTE-s tanárnak lenni egy ilyen probléma megoldásához. Nincs olyan tudás, amit az ELTE-n tudnak, de más országok egyetemein nem. Abból, hogy az első évben nem érkezett be helyes megoldás, gyanítható, hogy a probléma nehézsége meghaladja a jelenlegi "lehetőségeket". Mást nem nagyon tehetünk, kiváncsian várjuk a szilvesztert.
Röviden annyi, hogy a vizsgálat szempontjából bizonyos "jó" állapotokat letárolsz, amit nem kell újra generálni. Ha az állapot(ok) mégsem jó(k), akkor visszalépés.
Nem egészen értem a postodat. A megoldás ellenőrzése sokkal könnyebb, mint a megtalálása. Amúgy, ha az ELTE-re járnál akkor tudnád, hogy kirakták. Volt olyan tanár aki inkább nyugdíjba ment, hogy a problémán dolgozzon.
Már több mindenki állította magáról, hogy kirakta. Mennyire biztos, hogy az ELTE csapata valóban kirakta? És ez vajon, hogy tud összefüggni a termék jelenlegi árával? Ha kirakták és beküldték, a boríték akkor sincs felbontva, így nem lehetnek biztosak benne, hogy a megoldás jó. Ezért nem hiszem, hogy elkezdene csökkeni az ára. Szeintem a világ minden tájáról értkezhetett 480 pontos megfejtés (már az első évben is), de az más kérdés, hogy lesz-e köztük jó. Bár ilyen alapon egyáltalán nem csökkenhetne a termék ára, mert nem tudhatják, hogy van-e valóban jó megoldás.
Lehet, hogy igazad van, de azért folytatom a megoldás keresést, mert mi van, ha mégsem rakták ki?
Egyetértünk. Már csak az a kérdés megválaszolása hiányzik, hogy milyen ellenőrzéssel lehetne az esetek nagy részét már a bejárás elején kiszűrni. Aki erre egy jó algoritmust talál, annak van igazán esélye megnyerni a 2 millió dollárt.
Az sem lenne baj, ha az algoritmus a jelenlegi idő akár 1000-szeresét veszi el, ha estek száma ennél nagyobb arányban csökken. Ezért elképzelhető, hogy egy egész bonyolult algoritmus vezet majd célra. Ha egyszerű is elég lenne, akkor már az első évben kirakta volna valaki mind a 256 elemet.
A permutációval magával tisztában vagyok. Aki tanulta, annak a legelső iskolapélda a kombinatorika "Hello World!"-je az a példa, hogy adott 5 doboz 5 ajándék. Hényféleképpen lehet becsomagolni.
Amit korábban írtam, abban az esetben nem is brute force-on magán van a hangsúly. Szerintem a jelenlegi algoritmusok 80-90%-a valamilyen szinten használja is. Én inkább az esetszétválasztásra helyezném a hangsúlyt. Hogy a backtrack minél hamarabb észrevegye, hogy neki vissza kell lépkednie. Továbbá, ha kialakult egy új pattern a táblán, akkor gyorsabban lehessen ellenőrizni azt, hogy az a megoldáshoz vezet, avagy sem. Igyekezzen az algoritmus minél gyorsabban bejárni a gyökérhez közeli szinteket a fában (ha egy ág a lerakott elemek permutációját jelenti, mint állapotot). Így feltehetően hamarabb jut megoldásra, mint, ha folyamatosan mindent kirakok végig.
A Brute force esetén mások által elvégzett számítás szerint 10^600-n lehetőséget kell végignézni. Ha csak illeszkedő elemet raksz le, akkor korábban már levezetett becslésem szerint 10^91 lehetőség van. De ügyes eset szűréssel ez kevesebb is lehet.
Erre hadd adjak egy másfajta példát:
Egy ezer mezőből álló sort kell kirakni az 1 és 1000 közötti számokkal úgy, hogy az előző mindig 1-gyel kevesebb a következőnél.
Ha erre programot írunk, akkor Brute force-szal 1000 faktoriális esetet kell végignézni. De ha az első helyre 1000 számot teszünk, akkor utána már mindig csak 1 szám felel meg, tehát csak 1000 eset marad. Ha még ügyesebbek vagyunk, akkor rájövünk, hogy az 1-s csak az első mezőben lehet, tehát csak egyetlen eset ven.
Tehát a Brute force ebből a például kiindulva nagyon gazdaságtalan. Egyébként én is ezen az algoritmuson gondolkozom, amivel az esetek számát tovább lehetne csökkenteni. Sajnos amikor kitalálok egy elméletet, akkor azt fáradságos hosszantartó munkával lehet csak beprogramozni, aztán vagy jó, vagy nem, de eddig még egy sem volt jó. Az újabb és újabb program egyre bonyolultabb és egyre több ideig tart megírni.
Én csak most nyáron kezdtem, (és már akkor 2100 forintért lehetett a játékot megvásárolni), de aki már másfél éve írja a programjait azzal szemben lényeges hátrányban vagyok.
Egyébként érdekes a munka, de ha nem lenne nyeremény, nem írnám meg a programokat. Igaz, hogy élvezetes, de ilyen alapon az Eternity1-t is programozhatnám. Szerintem ez ma már senkinek sem jutna eszébe.
Sikerült! Az általad jacasolt beállításokat elvégeztem. Ygy most már az Excal Macro Visual Basic 100%-kos processzor kihasználtsággal fut. Ez igazán remek, 2-szer gyorsabb lett a program. Nagyon köszönöm.
"... Egy csomó dolgot rendkívül olcsón kiárusítanak, többek között a 256 db-os Eternity II-t is. Jelenleg nálunk 780 Ft-ba, azaz Hétszáznyolcvan forintba kerül. ..."
Nem a kulcspuzzle-t? Mert azt en se akartam megvenni, de mikor ugy ezres korul meglattam, gondoltam a gyerekeknek jo lesz. Gyakorolhatjak kicsit a backtrack-et:) annak mas nehezsege nincsen [6 es 7,5 evesek].
A prog.hu-n van egy bejegyzés, miszerint az egyik gazdaságos áruházban < 1k Ft-ért látta a hozzászóló. Azóta én is megnéztem a helybeliben. Sajnos nem volt. Ennyit még én is adtam volna érte.
Szintén zenész. Amikor megjelent már akkor elkezdtem programot írni, de akkor idő hiányában abbamaradt. Aztán most újra elővettem de valószínű most sem lesz kódolás belőle. Egy pár bejegyzést végigfutottam a fórumon. Érdekes okfejtések születtek, hogy hogyan lehetne a feladatot megoldani. Az egyik bejegyzés szerint elmebeteg, aki brute force alapján akar nekiállni. Nekem is kapásból ez az elmebeteg ötletem támadt. De, ha minden lehetésges esetet figyelembe veszünk, akkor 4*256! állapota lehet a táblának. Persze ebben az esetben a szélső elemeket nem különböztetjük meg. Pfff. Ha lesz időm azért összekalapálom a kódot. Vannak elképzeléseim. Brute force + backtrack + 1-2 optimalizálás (esetszétválasztás), ami jelentősen felgyorsíthatja az algoritmust. A feleslegesen futott köröket eleve kizárnám.
Nem gondolom, hogy lenne olyan ember, aki meveszi a játékot és nekilát a konyhaasztalon kirakni. Ez egyértelműen az a történet, hogy ki tud gyorsabban algoritmust adni a táblára. png-ben az eredeti darabjai: http://www.headsoft.com.au/index.php?category=pc&page=eternityii Mellesleg tök mindegy, hogy milyen táblát rak ki az ember, ha 256 darabos és 23 különböző típusú negyed van a játékban.
Az algoritmuson folyamatosan gondolkozom. Elsősorban nekem is agytorna, de nem jönne rosszul a fődíj egy töredéke vagy a fődíj maga.
Azzal azert nem ertek egyet, hogy nem lehetne ertekesiteni - szvsz aki nagyon akarta, a jatek megvasarlasa nelkul hozzajutott az elemlistahoz gepi kitolteshez, es ha megvan a megoldas eleg csak akkor megvenni a teljeset a jelentkezesi lapert... a nagyobb reszet szerintem a gyujtogetokon kivul (de azok mar 1 eve megvettek) ajandekba vagy valoban rakosgatni veszik meg, nem a nyeremenyert. Persze tevedhetek, csak velemeny!
A játék elvileg megy. Az, hogy van-e megoldás, csak dec 31. után derül ki.
De abban teljesen igazad van, hogy vannak olyan árulkodó jelek, amelyek arra utalnak, hogy esetleg megtalálták a megoldást. Ilyen pl. az, amit írtál is, hogy nincs új adat, infó, stb. a honlapokon. Másrészt időnként akciósan vásárolható a játék az eredeti ár töredékéért. De biztosat nem lehet tudni, mert a megoldás nyilvánosságra hozatalát ügyes üzleti fogással letilltották. Ha már most lehetne tudni, hogy vége, akkor a játékot egyáltalán nem lehetne értékesíteni.
OFF: A 2,8GHz-es Intel Pentium4-esek közül több széria is rendelkezik HyperThreading-gel. Ha a BIOS-ban be van kapcsolva, akkor szintén kétmagosnkat látja a processzort az operációs rendszer. Ha Windows-t használsz és előhívod a feladatkezelőt, akkor a teljesítmény grafikonoknál is két CPU terheltségét lehet látni. Ha mégsem így van, akkor vagy tényleg egymagos a processzor vagy a Feladatkezelő / Nézet / CPU előzmények / Külön grafikon minden CPU-hoz nincs bekapcsolva. Véleményem szerint ha tényleg 50%-os terheltséget látsz, akkor szinte biztosra lehet venni hogy a futó program csak az egyik végrehajtó egységet terheli a kettőből.
Köszönöm a segítséget. De szerintem itt nem ez a helyzet. A számítógép tulajdonságok: Intel(R) Pentium(R) 4 CPU 2.80 Ghz. Nem írja, hogy több magos lenne. Ha jól értem, akkor 100%-kon kéne mennem. Lehetőségem volt 4 gépen kipróbálni. Csak egyiken fut 100%-kal. De nem tudni, miért. Az igaz, hogy ez a leggyengébb gép, amin 100%-kal megy, de egyik sem több magos.
Egyébként mindenkinek ajánlom az iPuzzler-t. Ez egy ingyenes puzzle kirakó. Sajnos az Eternity elemeket nem tartalmazza, úgy kell feltölteni. Én megtettem, de a szerzői jog nem engedi, hogy ezt átadjam, mert az Eternity2 le van védve. Nyilván ezért nem adják a programhoz sem.
De érdemes kipróbálni, az iPuzzler egy másik kirakós játékát is, ami az Eternity2-höz teljesen hasonló, csak a minták mások. Ebből tökéletesen meg lehet érteni, amit írtam, miért akad el mindenképp az ember a végén. Esetleg a kirakáshoz írt programhoz ötletindítónak is jó. Van benne solver is, de kezdő elemet nem tudja kezelni, tehát arra ne akarja haszálni senki sem.
Sajnos csak megerősített az Eternity2 feladvány nehézségében.
Azért egy kis számítással javíthatok mindenki kedélyén. Közel sincs olyan sok variáció, mint amennyit a Brute-force-szal számolva kapunk.
Egy becslést engedjetek meg:
A 139-es kező elemet egészítsük ki egy plusz jellé. Ha a következő elem átlagosan 64 féleképp csatlakozhat, akkor ez 31^16 féleképp lehet. De ezutnán minden további elem lerakása már meglévő két oldalelemhez kell, hogy csatlakozzon. Ha átlagosan 2 elem illeszkedhet, akkor ez 2^224, de lehet, hogy csak 1,5^224.
És ezzel kész a képlet:
31^16 x 2^224
A 31-t 32-nek véve ez kb. 2^304. 2^10-t 10^3-nek véve ezkb. 10^91.
Tudom, hogy ez is nagy szám, de nagyságrendekkel kisebb a Brute-forca szerinti számnál. Úgyhogy nem kell csüggedni, a feladat úgy van elkészítve, hogy nehéz legyen, de az továbbra is kérdés, hogy elég nehéz-e. Szerintem van arra esély, hogy valaki megfejti. Ugyanis ez a szám tovább csökkenthető ügyes esetkizárásokkal.
OFF ketprocis ill. ketmagos gepen a nem kulon ilyen kornyezetre optimalizalt programok nem tudjak mind a kettot egyszerre kihasznalni (ugyebar nem mindegy a sorrend ket muvelet kozott, plane ha az egyik mar a masik eredmenyet hasznalna', akkor ok elvileg se parhuzamosithatok), ettol az 50% max. Egymagoson ugyanaz 100% lesz... ON
Csak nem tudom, hogy lehetne ezt kihasználni. Ugyanis a szabályoknak megfelelő feladványt nem nehéz gyártani. Én is készítettem egyet. A kezdő elem változatlan, a többi éleket meg véletlen generátorral feltöltöttem. Csak arra kellett ügyelni, hogy két puzzle-elem ne legyen azonos. Ezt elkeverve viszont a feladat ugyanolyan nehézségű. Tehát valószínűleg még ebből a plusz infóból, hogy van egy fix határoló terültet, amelyen belül több elrendezés is lehetséges, ebből kiindulva sem jutunk előbbre.
Nekem egyébként olyan gondom is van, hogy Microsoft Excel macro Visual Basic-ben írom, és ez csak a processzor 50%-t használja ki. Láttam már olyan gépet, ahol ez 100%, de akármit állítok be, nem sikerül 50%fölé vinni. Az Interneten más angol nyelvű fórumokon is volt hasonló panasz, de seholsem találtam olyan választ, ami megoldaná.
Sebesség és kombinációk, mindez az idő tényezőt befolyásolja. Most elég borúsan látom annak lehetőségét, hogy ki lehetne rakni. Az ugyanis a baj, hogy akárhogy is kezdem el, az utolsó elemeknél a véletlen dönti el, hogy belepasszolnak-e a környezetükbe. Innentől kezdve, hogy véletlen, máris esélyekkel kell számolni, ami egy lottó 5-ösnél is kisebb. Most nem akarnék én is számolgati, és a kapott valószínűségre nagy mínusz kitevőket írni. Ehhez valami átütő ötlet kell, amire a játék kitalálója sem gondolt, és köztük az Eterenity1 megoldója sem, ugyanis őt is bevonták az Eternity2 készítésébe. Nehéz nagy koponyáknál még okosabbnak lenni. Marad a vak szerencse, de ilyen alapon tényleg inkább lottózni érdemes. Talán csak azért mégis inkább ez, mert ez érdekesebb.
Lehetséges, sőt valószínűnek tartom, hogy van olyan elhatárolt terület, akár 4x4-es is, amelyiken belül ugyanazokaz az elemeket másképp összerakva, ugyanaz a határoló oldal sorozat jön ki. Azért valószínű ez, mert ezzel majd be tudnák mutatni, hogy nem csak egyetlen megoldás volt.
Egyébként szerintem az Eternity megalkotói sem tudják, hogy az ilyen trükkös módon generált több megoldáson felül van-e más megoldás. Úgy tudom, hogy előzetesen 8 évet dolgoztak a puzzle kitalálásán, de azt mégsem hiszem, hogy a 8 év alatt az akkor még gyengébb számítógépekkel találhattak volna megoldást, mikor a világ sok programozója az eddig eltelt 1,5 alatt egyet sem talált.
Egyébként én annak vagyok híve, hogy középről kiindulva kell kirakni a puzzle-t. Írtam rá programot, de még nagy eredményem nincs, az első hiba 164. elemnél van, és az összes elemet lerakva csupán csak 435 egyezőségem van. Ez jóval elmarad a tavalyi nyertes 467 elemétől.
Kíváncsi lennék másnak más módszerekkel milyen eredményei vannak.
Én próbálkoztam ilyesmivel. Nagyon kevés ilyen egyezőség van. 4x4-es mező esetén olyan 1:10.000.000 körül volt az arány. Nagyobb terület esetén (5x5) javulna, de azt már nem tudtam kiszámoltatni ( csak a sarkok és oldalak mellett ).
Van valakinek erről statisztikája, vagy gondolkozott erről?
Kiválasztod egyenként az összes 4x4 mezőcsoportot (16 db x), pld. Elsőnek a bal alsó sarkot. Itt veszed az összes lehetséges variációt. Van-e legalább két egyforma lerakás, ahol az külső élek (a-h) teljesen megegyeznek, és a kirakáshoz felhasznált elemek (x) teljesen ugyanazok?
abcd xxxxe xxxxf xxxxg xxxxh
Tehát ugyanabból a tetszőlegesen kiválasztott 16 elemből lehet-e két vagy több azonos külső élet előállítani?
