[Pascal] Algoritmus na seřazení čísel v matici (Hra 15)

[Dawn]

Potřeboval bych algoritmus na vyřešení takové té hry (nevím jak se jmenuje), kdy jsou v matici 4x4 čísla 1 až 15 libovolně rozházená. Řeší se to posuváním toho prázdného políčka doleva/doprava/nahoru/dolů. Případně není na to obecný algoritmus pro nxn. Stačí algoritmus, program si už napíšu. Díky!

[Absurdus]

vola sa to vacsinou jednoducho "Hra 15",
tato hra je podla mna tak na hranici toho, ked jednoduchy backtracking straca zmysel a je potrebne pouzit nejaku heuristiku...

obecny algoritmus je teda - backtracking

[Dawn]

vola sa to vacsinou jednoducho "Hra 15",
tato hra je podla mna tak na hranici toho, ked jednoduchy backtracking straca zmysel a je potrebne pouzit nejaku heuristiku...

obecny algoritmus je teda - backtracking

Já jsem právě myslel, že na to je nějaký sofistikovanější algoritmus. Backtrack i s nějakým ořezáváním bude hodně brutální. No zkusím to udělat a uvidíme. Jestli někdo víte, jak to vyřešit lépe, dejte vědět pls.

[Nikes]

Na jeden, mozna lepsi, jsem si vzpomel (delali jsme to ve skole). Tusim ze to fungovalo na principu ocenovani. Pred kazdym krokem jsi spocital sumu vzdalenosti od reseni a podle toho ses rozhodl kam jit. (vlastne takovej chytrejsi backtraking). Pokud bys to chtel vedet detailneji tak rekni, musel bych se kouknout do skript.

[Dawn]

Na jeden, mozna lepsi, jsem si vzpomel (delali jsme to ve skole). Tusim ze to fungovalo na principu ocenovani. Pred kazdym krokem jsi spocital sumu vzdalenosti od reseni a podle toho ses rozhodl kam jit. (vlastne takovej chytrejsi backtraking). Pokud bys to chtel vedet detailneji tak rekni, musel bych se kouknout do skript.

No kdybys mi to mohl popsat trochu podrobněji, tak bych byl moc rád. Dík.

[Absurdus]

sofistikovanejsie algoritmy samozrejme su ale pri nich nemas zarucene, ze sa naozaj dopatras ciela

kazda heuristika (aj spomenute ocenovanie) ma niekde achilovu patu a pre nejake vstupy to moze zlyhat

da sa pouzit aj princip sachovych algoritmov:
strom vsetkych tahov a jeho minmaxove orezavanie podla nejakej hodnotiacej funkcie...

P.S. dufam ze vies, ze nie vsetky pozicie sa nedaju vyriesit?

[Rainbow]

Vyriesit sa to da vtedy, ked to vytvoris posuvanim. Nahodne generovanie je sprostost.

[MaPa]

Mam dojem, ze resitelnost tohodle hlavolamu se dala nejak spocitat podle polohy kostek.

[Absurdus]

je to tak, ze z nahodnej pozicie posunovanim dostanes bud
1, 2, 3, 4,
5, 6, 7, 8,
9,10,11,12,
13,14,15
alebo
1, 2, 3, 4,
5, 6, 7, 8,
9,10,11,12,
13,15,14
(t.j. 15 a 14 vymenene...)

[MaPa]

je to tak, ze z nahodnej pozicie posunovanim dostanes bud
1, 2, 3, 4,
5, 6, 7, 8,
9,10,11,12,
13,14,15
alebo
1, 2, 3, 4,
5, 6, 7, 8,
9,10,11,12,
13,15,14
(t.j. 15 a 14 vymenene...)

Jo jasne, ale ja mel na mysli, ze se to dalo urcit uz z pocatecniho rozlozeni, se scitaly radky nejak nebo co a podle toho se dalo rict ze to je resitelny (ten 1. ripad cos psal) nebo ne (ten 2. pripad).

[Absurdus]

hm, to by ma celkom zaujimalo, vies to niekde najst?

minimalne by sa museli zratat aj riadky aj stlpce, kedze sucty riadkov su v koncovych poziciach rovnake...

[MaPa]

"Výchozí sestava 1, 2, 3, ..., 13, 15, 14 je lichá permutace. Naopak přirozená řada 1, 2, 3, ..., 13, 14, 15 je sudá permutace." Takze nejak z toho vychazet, nejak spocitat, mozna jeste neco najdu. Mrkni sem.. http://www.cut-the-knot.org/pythagoras/history15.shtml

Proste se najak scita pocet kolikrat je nejake cislo driv nez cisla ktera sou nizsi a podle souctu techto pripadu se to deli na resitelny (sudy pocet) a neresitelny (lichy pocet).

[Dawn]

MaPa: Díky za ten odkaz. To jsou docela zajímavý stránky. Hned se pustím do čtení.

[Nikes]

tak jsem se koukal do skript a asi te nepotesim. Konkretne jsme nebrali reseni 15. Pouze jsme si ukazovali obecne pristupy. Jedna se o tzv. informovane metody (heuristika). Dal bych ti link na skripta ale jsou v privat sekci. Myslim ze na netu neco z najdes. V nejhosim to vymyslis sam . Jak se rikal v kazdym kroku zkusis vsechny pohyby (max. 4) a pro kazdy spocitas cenu (sumu vzdalenosti) a pudes tou nejmensi.... (vis jak to myslim ne?).