(coz stejne znamena ze jsme stejne od konce stejne daleko)

Napadla mě taková obecná idea jestli by se to nedalo urychlit tím, že by se nějak předpočítaly větší bloky kostiček, ty se umístily do paměti a pak se nějak vybíralo z nich. Máte tady někdo k dispozici stroj s hodně velkou pamětí ? Myslím desítky nebo radši stovky GB.

Imho by na to sel i nejaky rychly disk. Takovych 10-50MB/s je celkem dost a u kosticek ti staci cisla hran. Kdyz se to ulozi bitove a ne cislama, tak 256 znaku v ASCII bude (0-255).

Myslis tedy jako vygenerovat treba tunu kosticek 4x4 a pak je jen skladat k sobe? (s ukladanim i jake kosticky se uz nemohou pouzit)

Jo, něco takového mám na mysli. Snažím se teď spočítat kolik by v rámci bloku 4x4 bylo kombinací. Nedělal jste někdo podobné výpočty ? Myslím, ale přesné výpočty, ne odhady typu faktoriál z 256 apod.

tak předně mi šlo o to rozpoutat flame .. to se podařilo .. aspoň je vidět, že je tu živo ..

Nešlo mi ani tak o to kdo koliv poskládal kostiček (já mimochodem 239), ale o algoritmus. A těmi tu moc nikdo neoplývá .. jde o to, že přece jen backtrackingem s bruteforce je to absolutně nereálné, což dokazují všechny teoretické výpočty počtu možností. Důležité je tedy ne se zaměřit na rychlost testování, ale heuristiku odřezávání větví stromu výpočtu.

Co do větších bloků, toto mně taky napadlo, ale má to několik háčků ... možností jak k sobě napasovat dvě kostky je něco přes 40000. Jak udělat matici 2x2 je těch možností už 4 miliony. Kolik myslíte, že bude těch možností s 4x4 maticí? I kdyby jich byly čtyři miliardy (a to je optimistickej odhad), tak je třeba pokaždé vybrat jen 16 z nich tak, aby se žádná z těch 16 ze kterých jsou poskládány neopakovala. Zjednodušeně, původní bruteforce algoritmus se vlastně jen zesložitil. Nebude potřeba počítat 1E100 puzzlí s jednou kostičkou, ale 1E90 puzzlí s 1E10možnostmi.

Btw nějakej magor obíhá na cz eternity forech s infem, že to vyřešil. Tak jsem zvědav, kdy se ukáže tady.

Tak jsem spočítal, že počet možností jak může vypadat blok 4x4 v levém horním nebo pravém dolním rohu je přesně 26066149651. Nechcete to po mě někdo zkontrolovat? Nejsem si úplně jistý jestli tam nemám chybu. Zajímavé by bylo, kdyby někdo určil kolik bude možností v těch středových 4x4 blocích. Určitě jich bude o několik řádů víc.

Kde co kdo vyřešil, je nějaký link ?

Myslis tohle?
http://forum.pocitac.com/e2-jeden-obrazek-t1590.html (reg).

No kdyz tedy nebudem mluvit o bruteforce .. tak bracha pracuje na jednom alg. co zjistil otoceni (natoceni) vsech kosticek.
Zatim jsou kontrolni soucty. Dneska jsem mu poslal jednu otaceci ficovniku, takze uvidim s cim prijde o vikendu (staci zkusit mene nez "jen" 4^256 moznosti a je to, ale to pujde jeste dost optimalizovat i dopocitavat rucne).

To si nějak neumím představit jak bych určil samotné otočení kostek aniž bych se je současně snažil umísťovat.

Zdravím!

Také přileju trochu svého oleje do ohně... Skládat dílky do dlaždic není dobrá cesta. Zkoušel jsem dlaždice 2x2, takže jsem pak skládal pole 8x8, jenže těch kombinací dlaždic je tolik, že to vyjde nastejno.

Ořezávat backtracking je si myslím také nesmysl, protože dokud algoritmus nedojde do místa, kde už nemá žádný dílek k dispozici, tak nelze s jistotou předpovědět, zda má daná větev smysl. Otázou spíš je, které větve preferovat - a teď babo raď

Mám algoritmus, který vyhledává potřebné dílky téměř v čase O(1) včetně správné rotace, průměrná rychlost je +5 milionů položených dílků. Funguje to celkem spolehlivě, 14x14 vyřeší v průměru za 2 hodiny. Skládám šnekem od kraje. 15x15 jsem radši nezkoušel, na několika serverech jsem rovnou zkusil spustit 16x16, má to za sebou po 6-ti dnech asi 10 bilionů dílků a ani ťuk

Napadá tedy někoho jak řadit větve pro procházení?

Hasan

Napadlo me pouziti ohodnocovani hran. Mysleno ze kazde kosticce se prideli cislo a bude se preferovat nejprve pokladat kosticky s .mensim. ohodnocenim (to proto, aby ty cenejsi zustaly na pozdeji).
Ohodnocovani delat nejspis pres rozrazeni na zaklade cetnosti - v E2 jsou kosticky, kde se jejich hrany uz v zadne kombinaci neopakuji. Naopak jine jsou celkem "bezne". Taky bych dal body navic kostickam, jenz maji hranu, jejihoz typu neni 50.

To hashan :

Souhlas, tudy cesta asi nevede. Zkoušel jsem jenom spočítat, kolik je teoreticky možných bloků 4x4, které jednou stranou přiléhají k okraji. Běželo to celý víkend, zatím jsem napočítal přes 2 Tera možností a ještě to nedoběhlo, takže jsem to rovnou stopnul protože to stejně nemá smysl.

To xsoft :

To ohodnocování zní na první pohled rozumně a naprosto logicky, ale nejsem si tím zas tak jistý, protože pokud zvolím nějaké pořadí umístťování kostiček (např. šnek jak píše hasan) tak takto postavené ohodnocování by celou věc urychlilo jen za předpokladu, že "vzácnost" kostiček je u okrajů v průměru nižší než směrem ke středu, což nevím proč by tak mělo být. Takže to ohodnocování by paradoxně mohlo výpočet naopak zpomalit, protože se díky počátečním volbám méně vzácných kostiček backtracking bude dlouho potácet v úplně špatných větvích vyhledávacího stromu. Kdyžtak mě opravte pokud se vám tato úvaha nezdá správná.

Jinak jak tedy pokladas kosticky? Kdyz mas polozit kostku na misto, ktere uz ma 2 sousedni hrany, tak das prvni co tam jde? Nebo nahodnou .. nebo postupne (od nejnizsi vsechny)?

Ano, mám seznam kostiček v nějakém vlastně úplně náhodném pořadí a vždy použiju první vyhovující volnou. Teprve až když se backtrackingem vrátím na to samé místo použiju druhou atd. V optimálním případě by ty kostičky byly zamíchané v takovém pořadí, že vždy jako první vezmu tu správnou. Bohužel takto spárvě zamíchané to evidentně nemám .