Hele, ale to by mohla byt celkem genialni myslenka?
Proste za na zacatku nejakym total randomem zamycham seznam kosticek, a budu skladat tak, ze tam vzdy dam tu prvni co pujde .. a pokud se nekde zaseknu, tak jedu uplne odznova.
Pak by na zamichani celeho listu stacilo mene nez 256! zamychani (ale i to je dost, co)?

To je podle mě jen backtracking v bledě modrém, protože vykoušení jiné alternativy při záseku jen nahradíš tím, že se na to celé vykašleš a začneš znovu od začátku s jiným setříděním kostiček. Z hlediska složitosti je to myslím +/- stejné.

Alg. pravda neni tezky, napsal jsem si 1 ve starem dobrem Pascalu:)) a pole 16x16 (nahodne vygenerovane, pac hru E2 nevlastnim) vyresi za 22min. Problem je ovsem v tom, ze tato doba silne zavisi na poctu ruznych symbolu ve hre obsaženych; zde tomu odpovida 30 symb.+symbol hranice. S klesajicim poctem symbolu se bude doba, za kterou projde compl vsechny pripustne kombinace, nadexponencielne prodluzovat (nic to ovsem nevypovida o dobe nalezeni reseni, ta by se naopak mela pri dosti malem poctu symbolu zase zkracovat..). Z toho take plyne, ze ciselny odhad vsech moznych kombinaci, ktery neuvazuje pocet techto ruznych sumbolu ve hre, nemuze byt verohodny - v lepsim pripade je jen velmi hrubou aproximaci.
Rad bych Vas proto poprosil, jestli by mi nekdo sdelil tento pocet ruznych symbolu (vyjma sedeho pole hranice), abych si tokovy odhad mohl vypocist. Srdecne dekuji!

ho3: regni se a jukni do jedne sekce

A usefull program to play eternity ii on computer:
http://www.intellisol.hu

There's a E2 edge pattern set (not the piece set) available somewhere on the net for this program.

Nevím jestli už to víte, ale wikipedie se odkazuje na článek http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf, podle kterého je daný problém NP-úplný. Z toho plyne (za předpokladu, že P nerovná se NP, což ale není dokázané), že každý algoritmus řešící daný problém bude mít exponenciální složitost. Tím pádem pokud je to puzzle šikovně udělané, tak na to prostě žádný použitelný algoritmus nevymyslíte a nalezení řešení bude jen a jen otázkou štěstí.

Nicméně tohle je také zajímavé: http://www.daimi.au.dk/dKS/torsdag.ppt

Tohle jsem taky četl a E2 nepochybně NP-úplný problém je. Souhlasím, že je to hlavně otázka štěstí, asi tak z 99%. No a to zbylé procento je schopnost to dobře naprogramovat, optimalizovat a taky mít odpovídající HW. Ne každý holt má k dispozici tohle http://www.llnl.gov/asc/computing_resources/bluegenel/bluegene_home.html

Tak sem premyslel a nic noveho svetoborneho me nenapadlo... porad mam jen jedinou realnou faktickou myslenku a to ze musi existovat nejakej vzajemnej vstah mezi nekterejma dilkama... Napadlo me reseni typu ala predchozi eternity... to znamena:

1) zkusit najit nejake anomalie ktere tam jsou (jestli tam jsou)... to znamena treba dohledat ze (priklad) kosticka 253,236 a 194 musi byt u sebe, protoze jina kombinace jak obsadit kosticku 236 z obou stran neexistuje....

2) Na zaklade najitych anomalii seskladat nejakou zakladni skladacku a k te pak zkouset dosazovat zbytek

Mam vygenerovany varianty 2x2 je to nejakejch 4 096 000 kombinaci (+/-) ale nezkoumal sem jestli treba nektera z kosticek neni obsazena pouze v nekterem z dilku (to znamena ze sem nezkoumal jeji vstaznou zavyslost na jine kosticky)... asi to nebude jednoduche neco takoveho odhalit, protoze rekneme ze treba kosticka 236 muze sousedit s sesti ruznymy kostkamy ze strany A ale pokud pouzijeme nekterou z peti moznosti, prestane nam pasovat zase varianta k nektere jine kosticce... Uvedu priklad:
Kostka 110 ma z prava 3 moznosti (111,112,113)
Kostka 111 ma z prava 3 moznosti (110,112,113)
Kostka 112 ma z prava 3 moznosti (110,111,113)
kostka 113 ma z prava 3 moznosti (111,112,113)
Pak podle tohohle je jednoznacna zavislost... Nezkousel nekdo nejakym zpusobem analyzovat tentle problem? Je temer jiste ze na zaklade tohohle vede cesta k usnadneni... problem je ten ze tech paru je tam daleko vic... ale zrovna tohle je jednoznacne, nebot je dejme tomu 26 kostek urciteho symbolu... coz dela 26 kosticek a pro kazdou 25 moznych jinych kostek...
Nezkouseli jste to nekdo touhle cestou a co si o tom myslite?