Hat dieses Spiel eine Lösung

Question

Ich entwickle ein einfaches Spiel mit Java Swing. Ich möchte wissen, ob dieses bestimmte Spiel im folgenden Szenario eine Lösung hat. Wenn ich überzeugt bin, dass theoretisch an dieser Stelle keine Lösung gefunden werden kann, werde ich eine Benachrichtigung an den Nutzer schicken.

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

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

Das Ziel dieses Spiels ist Zahlen zu füllen 1 bis 8 (oder 1 bis 15) mit der einen Raum zur Verfügung zu Push die Zahlen zu diesem leeren Raum. Jedes Mal, wenn ich mit der oben gezeigten Kombination komme. Ich möchte mich nur selbst davon überzeugen, dass es aus dem obigen Szenario keine Möglichkeit gibt, die richtige Lösung zu finden. Bitte helfen Sie.

EDIT: Lösung wurde bei here und here

Answer 1

Ja und nein gepostet. Wenn Sie die Zahlen zufällig generieren, glaube ich, dass es eine Situation geben kann, die dazu führt, dass das Puzzle unlösbar wird. Die Art und Weise, wie ich vorschlagen würde, ein Puzzle zu erstellen, beginnt mit dem gelösten Puzzle und führt eine Anzahl von Rückwärtsbewegungen aus (basierend auf dem Schwierigkeitsgrad). Auf diese Weise weißt du, dass das Ende-Puzzle lösbar ist.

Answer 2

Diese Diskussion von The 15 Puzzle wird Ihnen wahrscheinlich die Antwort geben. Ich vermute, dass die Analyse der Permutationen in diesem Puzzle auf dein kleineres Puzzle angewendet wird.

Answer 3

Von der französisch wikipedia auf der "Taquin" (The 15 Puzzle):

Anecdote

Position initiale du taquin de Sam Loyd
Loyd Affirma qu'il avait «rendu le monde entier fou »avec un taquin modifié. Dans la configuration proposée, les carreaux 14 et 15 etéient inversés, espace vide étant place en bas à droite. Loyd prétendait avoir promis 1 000 USD à celui qui reméttrait les carreaux dans l'ordre, más la récompense n'aurait jamais été réclamée.
La resolution de ce problème ist unmöglich. D'une part, il faut en effet échangère les places des carreaux 14 et 15, und das auf der monteur que cette opération nécessite un nombre impairment de glissements. Der Teil, der auf der Rückseite der Fall ist, ist ein Ort der Initiierung, der Operation qui, quant elle, nécessite un nombre pair de glissements. Il est toutefois möglich d'ordonner les chiffres de 1 à 15 à la case vide est initiative en haut à gauche.

---

Anecdote

Anfangsposition von 15 Puzzle Sam Loyd
Loyd sagte, er habe mit einem modifizierten 15 Puzzle "die Welt verrückt gemacht". In der vorgeschlagenen Konfiguration wurden die Kacheln 14 und 15 umgedreht, wobei der leere Raum unten rechts angeordnet ist. Loyd behauptete, 1 000 USD für jemanden versprochen zu haben, der die Fliesen in Ordnung bringen würde, aber die Belohnung wurde nie beansprucht. Lösung dieses Problems ist unmöglich.Auf der einen Seite muss es in der Tat die Plätze der Kacheln 14 und 15 tauschen, und es kann gezeigt werden, dass diese Operation eine ungerade Anzahl von Dias erfordert. Auf der anderen Seite muss der leere Raum in seine ursprüngliche Position zurückkehren, eine Operation, die eine gerade Anzahl von Dias erfordert. Es ist möglich, die Nummern 1 bis 15 zu bestellen, wenn der Leerraum anfangs oben links ist.

---

Ressourcen:

• fr.wikipedia - Taquin