15-Puzzle

Spielprinzip und Lösbarkeit

Das 15-Puzzle ist ein Geduldsspiel mit 15 durchnummerierten Kacheln auf einem Vier-mal-vier-Feld. Ein Feld bleibt als „Loch“ frei. Nur eine horizontal oder vertikal benachbarte Kachel darf in dieses freie Feld geschoben werden. Das übliche Ziel ist, die Zahlen 1 bis 15 zeilenweise aufsteigend anzuordnen, mit dem freien Feld unten rechts.

Nicht jede beliebige Anfangsstellung ist zu diesem Ziel lösbar. Beim klassischen 15-14-Puzzle sind nur die Kacheln 14 und 15 gegenüber der geordneten Stellung vertauscht; das freie Feld liegt unten rechts. Diese Stellung kann durch erlaubtes Verschieben nicht in die geordnete Stellung mit freiem letzten Feld überführt werden. Wird stattdessen das erste Feld frei gelassen, ist die Aufgabe lösbar.

Moderne Ausgaben werden meist bereits geordnet ausgeliefert und haben verzahnte, nicht herausnehmbare Kacheln. Der Spieler mischt sie daher durch Verschieben; diese so erzeugten Stellungen sind garantiert wieder in den Ausgangszustand zurückführbar.

Anordnungen und Varianten

Beim ursprünglichen „Gem Puzzle“ wurden die Steine herausgenommen und beliebig wieder eingesetzt. Mit 16 Positionen gibt es 16! = 20922789888000 ≈ 2,1 ⋅ 10^{13} mögliche Startanordnungen, wenn das leere Feld nicht zwingend unten rechts liegt. Genau die Hälfte lässt sich in eine aufsteigende Reihenfolge mit leerem Feld unten rechts bringen; die andere Hälfte lässt sich in eine entsprechende Reihenfolge mit leerem Feld oben links bringen.

Ist eine bestimmte Anordnung erreichbar, dann ist ihre horizontale oder vertikale Spiegelung sowie ihre Drehung um 90° nicht erreichbar. Eine Drehung um 180° und eine diagonale Spiegelung sind dagegen erreichbar. Auch eine Stellung, bei der nur zwei benachbarte Steine vertauscht sind, ist nicht erreichbar.

Neben Zahlenpuzzles gibt es Versionen mit Bildern, Buchstaben, Buchstabengruppen oder römischen Zahlen. Bei Textversionen können gleiche Kacheln vorkommen. Sind am Ende zwei Kacheln vertauscht, kann der Tausch eines Paars gleicher Buchstaben oder gleicher Buchstabengruppen die Aufgabe lösbar machen. Andere Größen sind das 8-Puzzle auf einem Drei-mal-drei-Quadrat und das 31-Puzzle auf einem Vier-mal-acht-Rechteck.

Parität als Lösbarkeitskriterium

Ob eine Stellung lösbar ist, lässt sich mit einer Invariante prüfen: einer Größe, deren gerade oder ungerade Parität sich bei jedem erlaubten Zug nicht ändert. Dazu zählt man zunächst den Unordnungsparameter N₁. Er ist die Zahl aller ungeordneten Zahlenpaare: Eine kleinere Zahl steht in der von links nach rechts gelesenen Folge hinter einer größeren Zahl. Zwischen den beiden Kacheln dürfen weitere Kacheln liegen.

Beim 4×4-Puzzle kommt der Reihenparameter N₂ hinzu, die Nummer der Reihe des leeren Feldes. Für eine gerade Spaltenzahl betrachtet man N = N₁ + N₂. Seine Parität bleibt erhalten: Ein horizontaler Zug verändert weder N₁ noch N₂. Bei einem vertikalen Zug ändert sich N₂ um +1 oder −1; zugleich ändert sich N₁ um einen ungeraden Wert, nämlich +3, +1, −1 oder −3. Insgesamt verändert sich N daher stets um einen geraden Wert.

In der geordneten Endstellung gilt N = 0 + 4 = 4, also gerade. Bei der Stellung mit vertauschten 14 und 15 gilt N = 1 + 4 = 5, also ungerade. Deshalb kann sie nicht gelöst werden. Allgemein bleibt bei einer ungeraden Spaltenanzahl die Parität von N₁ erhalten; bei einer geraden Spaltenanzahl bleibt die Parität von N₁ + N₂ erhalten. Damit kann höchstens die Hälfte aller denkbaren Stellungen von einer Ausgangsstellung aus erreicht werden. William Woolsey Johnson und William E. Story zeigten 1879, dass genau diese Hälfte erreichbar ist; Aaron F. Archer gab 1999 einen modernen Beweis dafür.

Magische Quadrate als Ziel

Eine weitere Aufgabe ist, die übliche geordnete Startanordnung mit dem leeren Feld unten rechts in ein magisches Quadrat zu überführen. Das leere Feld zählt dabei als Zahl 0. Die magische Summe, also die Summe jeder Zeile, Spalte und Diagonale, beträgt 30.

Unter Berücksichtigung von Drehungen und Spiegelungen gibt es 880 ⋅ 8 = 7040 magische Quadrate auf einem 4×4-Feld. Genau 3520 davon sind aus der üblichen Startanordnung erreichbar. Kociemba bestimmte die minimale Zugzahl für jedes dieser Quadrate: Mindestens 35 Züge sind nötig, und nur ein einziges magisches Quadrat ist in 35 Zügen erreichbar.

Algorithmen und Komplexität

Das 8-Puzzle und das 15-Puzzle sind wichtige Testprobleme für Suchalgorithmen der Künstlichen Intelligenz. Adrian Brüngger, Ambros Marzetta, Komei Fukuda und Jurg Nievergelt zeigten 1999 mit einem Intel-Paragon-Parallelrechner mit 64 Knoten, dass jede lösbare Startstellung des 15-Puzzles in höchstens 80 Zügen gelöst werden kann.

Richard E. Korf und Peter Schultze ermittelten 2005 durch Breitensuche für jede der 16!/2! = 10461394944000 lösbaren Startkonstellationen die minimale Lösungszugzahl. Sie fanden erstmals alle 17 Stellungen, die genau 80 Züge benötigen. Eine zufällig gewählte lösbare Stellung benötigt im Mittel 52,6 Züge. Für die Berechnung wurden 8 ⋅ 10^{14} Bit ≈ 100 Terabyte geschrieben und gelesen; zur Vermeidung von Speicherfehlern kam ein RAID-System zum Einsatz.

Für das verallgemeinerte n×n-Spiel bewiesen Manfred Warmuth und Daniel Ratner 1986: Die minimale Zugzahl zu einer lösbaren Startanordnung zu finden, ist NP-schwer. Das bedeutet, dass dieses Optimierungsproblem für größere allgemeine Fälle rechnerisch besonders schwierig ist.