warum-ist-das-15er-puzzle-unlosbar

Warum ist das 15er-Puzzle unlösbar

Das „15er-Puzzle“, auch bekannt als das „15-digitale Problem“, ist nicht unlösbar, sondern der Zielzustand kann in bestimmten Ausgangslagen nicht erreicht werden.

Spielbeschreibung

Das „15er-Puzzle“ ist ein Schiebepuzzle, bei dem das Spielbrett ein 4x4-Raster mit 15 Schiebern, beschriftet von 1 bis 15, und einem Leerfeld ist. Das Ziel des Spielers ist es, die Schieber in der Reihenfolge von links nach rechts und von oben nach unten zu bewegen, was zu einer geordneten Folge von 1 bis 15 führt, wobei das Leerfeld in der unteren rechten Ecke steht.

Unlösbare Fälle

Die Situation kann nicht legal auf den Zielzustand verschoben werden, wenn und nur wenn die Anzahl der invers geordneten Paare im Ausgangsstand ungerade ist. Ein invers geordnetes Paar ist ein Zahlenpaar in einer Reihe, das als invers geordnetes Paar bezeichnet wird, wenn ihre vorderen und hinteren Positionen in umgekehrter Größenordnung liegen, d. h. die vordere Zahl größer ist als die hintere Zahl. Beispielsweise sind in der Reihe 2, 4, 3, 1 die inversen Paare (2, 1), (4, 3), (4, 1), (3, 1), insgesamt vier.

Beweis.

Die Bewegung der Schieber auf dem Brett lässt sich als Transformation der Anordnung dieser Schieber betrachten. Jedes Mal, wenn ein Schieber bewegt wird, wird tatsächlich ein Leerfeld mit einem benachbarten Schieber ausgetauscht. Und diese Tauschvorgänge ändern die Parität des Inversionslogs der Anordnung. Das Inversionslog des Zielzustands ist 0, was gerade ist. Wenn das Inversionslog des Ausgangsstands ungerade ist, kann es, egal wie oft es bewegt wird, nicht in einen geraden Wert geändert werden, und der Zielzustand kann nicht erreicht werden.

Wenn Sie auch gerne Puzzles ball spielen, ist es völlig kostenlos, spaßig und einfach.