15-Puzzle

Das 15-Puzzle auch Schiebepuzzle genannt, ist ein klassisches Geduldspiel. Ziel des Puzzle-Spiels ist es, die Zahlen 1 bis 15 zu ordnen. In der ersten Reihe sollten also die Zahlen 1 bis 4 liegen, in der nächsten Reihe die Zahlen 5 bis 8 und so weiter. Das leere Feld sollte am Ende unten rechts liegen.

In diesem Artikel möchste ich keine Lösungsstrategie geben, sondern beschreiben wann ein solches Puzzle überhaupt lösbar ist. Schauen wir uns hierfür das folgende Puzzle an.

Nun sind uns zwei Punkte wichtig:

• Das leere Feld befindet sich in Reihe:
  999
• Die Anzahl nicht sortierter Zahlenpaare (eine Auflistung der Paare ist unten zu finden) beträgt:
  999

Die Summe der beiden Werte ist aktuell eine gerade Zahl.


Was können wir nun mit dem Puzzle machen. Es gibt eigentlich nur 2 Möglichkeiten die ich unterscheiden möchte.

1. Eine Bewegung nach links oder rechts.
2. Eine Bewegung nach oben oder unten.

Was passiert beim ersten Fall? Versuch macht klug, also probiere oben beim Puzzle aus, was in diesem Falle mit unseren beiden Zahlen X und Y passiert.
Das leere Feld ändert in diesem Fall nie seine Reihe. Demnach bleibt auch X gleich. Die Anordnung ändert sich ebenfalls nicht, da wir ja nur nach links beziehungsweise rechts schieben. Also bleibt auch die Summe unverändert.

Interessanter ist die zweite Möglichkeit. Auch hier würde ich dich bitten erst einmal selbst zu schauen was passiert. Also ab noch oben ins Puzzle und beobachte was mit unseren beiden Werten passiert.

Fangen wir wieder mit dem leeren Feld an. Entweder es geht um ein Feld nach oben oder um ein Feld nach unten. Für X bedeutet dies eine Veränderung von genau 1.
Was passiert aber mit der Anzahl nicht sortierter Zahlenpaare? Wenn du oben beim Puzzle ein wenig rumprobiert hast ist dir bestimmt aufgefallen das Y sich entweder um 1 oder um 3 ändert. Dies sind auch die einzigen Möglichkeiten die es gibt.
Aber warum gibt es nur diese beiden Änderungen? Nehmen wir hierzu am Besten die Ausgangsstellung (oben einfach auf Reset klicken). Schieben wir nun die 6 eine Reihe nach unten, so ändert sich die Sortierung bei den folgenden drei Paaren:

• 2 und 6 - ist nun richtig sortiert. Y veringert sich um 1.
• 9 und 6 - ist nun falsch sortiert. Y erhöt sich um 1.
• 12 und 6 - ist nun falsch sortiert. Y erhöt sich um 1.

Insgesamt erhöt sich Y um 1. Allgemein gesehen haben verändern wir bei drei Zahlenpaare die Sortierung.

• Alle 3 sind nun richtig sortiert. Y veringert sich um 3.
• 2 sind nun richtig und 1 ist falsch sortiert. Y veringert sich um 1.
• 1 ist nun richtig und 2 sind falsch sortiert. Y erhöt sich um 1.
• Alle 3 sind nun falsch sortiert. Y erhöt sich um 3.

Da sich X um 1 ändert haben wir eine Veränderung der Summe X + Y von einer geraden Zahl (ungerade + ungerade = gerade).

Was bedeutet dies für die Lösbarkeit des Puzzles? Egal wie wir Schieben, die Summe aus X + Y bleibt für das angegebene Puzzle immer gerade. Sollte das Puzzle gelöst sein, so ist Y = 0 und X = 4. Wir haben keine unsortierten Paare und das leere Feld befindet sich in der vierten Reihe.

Ein nicht lösbare Puzzle ergibt sich beispielsweise durch Vertauschung der beiden Zahlen 14 und 15. Hierfür oben einfach auf 14-15 klicken.

• Das leere Feld befindet sich in Reihe:
  X = 4
• Die Anzahl nicht sortierter Zahlenpaare (eine Auflistung der Paare ist unten zu finden) beträgt:
  Y = 1

Die Summe der beiden Werte ist nun eine ungerade Zahl:

X + Y = 5
Egal wie wir nun Schieben bleibt die Summe bei einer ungeraden Zahl. Demnach ist diese Ausgangsstellung nicht l&oum;sbar.