Autor Zpráva
Malek
Profil *
Zdravím,
tvořím hru, jako je tato:


Zatím je vše bez problémů, až na jednu věc. Čísla generuji náhodně, v posledním řádku a sloupci je vždy prázdné místo, na které lze přesunout vedlejší čísla. Účelem je poskládat čísla takto:
1 2 3
4 5 6
7 8 -

Ale napadlo mě - může se stát, že by hra neměla řešení? A jak by se tomuto dalo zabránit - nějaká podmínka jak zjistit, jestli má řešení?
janbarasek
Profil
Malek:
Jedná se o typ hry, která se dá řešit například rekurzivně, podobně jako hra Hanojské věže (nebo třeba Královská jízda). Hry tohoto typu mají vždy nějaké řešení, někdy je ale natolik obtížné, že ho nemá smysl hledat, protože by to trvalo šíleně dlouho (třeba i několik let). Proto spíše vymysli nějaký algoritmus, co udělá zadání, které se dá nějak vyřešit. Spíše bych to udělal tak, že bych čísla jako první uložil ve správném tvaru a pak udělal náhodných x tahů, aby se to "promíchalo", podobně jako karty. Pak bude jistota, že to lze řešit právě na X tahů, takže bude řešení relativně jednoduché (a navíc půjde obtížnost libovolně nastavit).
juriad
Profil
Ano. Každé druhé zadání nemá řešení. Ale platí, že vždy lze hru dohrát buď do cílového stavu:
1 2 3
4 5 6
7 8 -
, nebo skoro cílového (liší se záměnnou jedné dvojice)
1 2 3
4 5 6
8 7 -



Přečti si odstavec Solvability na http://en.wikipedia.org/wiki/15_puzzle (stejný argument platí i pro velikost 3x3)
Chamurappi
Profil
Reaguji na Malka:
může se stát, že by hra neměla řešení?
Může. Viz Solvability of the Tiles Game, tam je i popsaný postup určení, zda řešení existuje.
Mimochodem, kategorie Jak něco udělat na diskusi o tvorbě webových stránek je určená pro dotazy z oblasti tvorby webových stránek.
juriad
Profil
Pro velikost liché velikosti je to rozebrané v tomto článku: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
peta
Profil
„může se stát, že by hra neměla řešení?“
Nemuze.
Muze se stat, ze nema reseni, kdyz pouzijes nespravny postup, treba nahodne rozhazeni. U takoveho postupu nemuzes zarucit, ze povede k reseni. Totez treba, kdyz delas labyrint a take bys jej nahodne vygeneroval, tak muze a nemusi vzniknout cesta skrz. U nahodneho rozhazeni je treba zamenit 14 a 15 pro 4x4, kdyz to nema reseni.
http://mujweb.cz/peter.mlich/hry/shuffle2.htm
Bubák
Profil
peta:
Muze se stat, ze nema reseni, kdyz pouzijes nespravny postup, treba nahodne rozhazeni.
Dyk to Malek píše už na začátku, jaký postup postup ke generování hlavolamu použil.
Kcko
Profil
Bubák:
Dyk je to Peta :)
peta
Profil
Bubák: Ja vim. Chtel jsem poukazat na to, ze napad dobry, ale chybny. Ale, co resi vase posledni komentare, to nechapu :)

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: