Questo gioco ha una soluzione

Question

Sto sviluppando un semplice gioco usando Java swing. Voglio sapere se questo particolare gioco ha una soluzione nel seguente scenario. Se sono convinto che teoricamente non è possibile arrivare a una soluzione a questo punto, invierò una notifica all'utente.

3x3
http://img814.imageshack.us/img814/7449/screenshot20100924at206.png

4x4
http://img39.imageshack.us/img39/1851/screenshot20100924at241.png

L'obiettivo di questo gioco è riempire i numeri da 1 a 8 (o da 1 a 15) utilizzando uno spazio a disposizione di spinta i numeri di quello spazio vuoto. Ogni volta che finisco con la combinazione mostrata sopra. Voglio solo convincermi che non c'è modo di ottenere la soluzione adeguata dallo scenario sopra. Per favore aiuto.

EDIT: soluzione è stata pubblicato su here e here

Answer 1

Sì e no. Se generi i numeri casualmente, credo che ci possa essere una situazione che potrebbe rendere irrisolvibile il puzzle. Il modo in cui suggerirei di generare un puzzle è iniziare con il puzzle risolto, ed eseguire un numero (crescente in base alla difficoltà) delle mosse al contrario. In questo modo sai che il puzzle finale è risolvibile.

Answer 2

Questa discussione di The 15 Puzzle probabilmente vi darà la risposta. Sospetto che l'analisi delle permutazioni in quel puzzle si applicherà al tuo puzzle più piccolo.

Answer 3

Dal wikipedia francese sulla "Taquin" (Il 15 puzzle):

Aneddoto

Posizione initiale du taquin de Sam Loyd
Loyd Affirma qu'il avait «rendu le monde entier fou »avec un taquin modifié. Dans la configurazione proposta, les carreaux 14 et 15 étaient inversés, l'espace vide étant placé en bas à droite. Per saperne di più avoir promis 1 000 USD in tutto il mondo in auto con l'ordine, più la récompense n'aurait jamais été réclamée.
La résolution de ce problème est impossibile. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on peut montrer que cette opération nécessite un nombre impair de glissements. D'autre parte, il faut il caso vide retrouve sa place initiale, opération qui, quant à elle, nécessite un nombre pair de glissements. Questo è il modo più semplice possibile di ordinare per un periodo di tempo.

---

Aneddoto

Posizione iniziale di Sam Loyd 15 puzzle
Loyd ha detto di aver "fatto il pazzo mondo" con un 15 puzzle modificato. Nella configurazione proposta, le tessere 14 e 15 sono state invertite, lo spazio vuoto è stato posizionato in basso a destra. Loyd ha affermato di aver promesso 1 000 dollari a chi avrebbe messo le tessere in ordine, ma la ricompensa non è mai stata rivendicata. La risoluzione di questo problema è impossibile.Da un lato, deve infatti scambiare i posti delle tessere 14 e 15 e si può dimostrare che questa operazione richiede un numero dispari di diapositive. D'altra parte, lo spazio vuoto deve tornare alla sua posizione originale, un'operazione che richiede un numero pari di diapositive. È possibile ordinare i numeri da 1 a 15 se lo spazio vuoto è inizialmente in alto a sinistra.

---

Risorse:

• fr.wikipedia - Taquin