Puzzle hra: Může se stát, že nemá řešení?

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).

Ano. Každé druhé zadání nemá řešení. Ale platí, že vždy lze hru dohrát buď do cílového stavu:
, nebo skoro cílového (liší se záměnnou jedné dvojice)

Přečti si odstavec Solvability na http://en.wikipedia.org/wiki/15_puzzle (stejný argument platí i pro velikost 3x3)

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.

Pro velikost liché velikosti je to rozebrané v tomto článku: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

„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

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.

Bubák:
Dyk je to Peta :)

Bubák: Ja vim. Chtel jsem poukazat na to, ze napad dobry, ale chybny. Ale, co resi vase posledni komentare, to nechapu :)