Das 8-Puzzle hat einen winzigen Fußabdruck und einen überproportional großen Ruf. Acht quadratische Plättchen, nummeriert von 1 bis 8, sitzen auf einem 3×3-Brett. Ein Feld ist leer. Ihre Aufgabe: Plättchen in das leere Feld schieben, einen Zug nach dem anderen, bis die Zahlen geordnet sind — üblicherweise 1‑2‑3 oben, 4‑5‑6 in der Mitte, 7‑8‑leer unten.
Es ist das kleinste Mitglied der N-Puzzle-Familie. Das 15-Puzzle ist der bekanntere Cousin, aber das 8-Puzzle ist der Ort, an dem alle — Kinder, Studierende und Forschende für Suchalgorithmen — gewöhnlich beginnen.
Wie ein einzelner Zug funktioniert
Das leere Feld ist das Einzige, was Sie wirklich steuern. Sie können nur ein Plättchen verschieben, das direkt über, unter, links oder rechts vom leeren Feld liegt. Diagonale Züge sind nicht erlaubt. Plättchen aufnehmen und woanders absetzen ist nicht erlaubt. Jeder Zug ist ein benachbartes Plättchen, das um eine Zelle in die Lücke rutscht, und die Lücke sitzt jetzt dort, wo das Plättchen vorher war.
Diese kleine Regel macht das Puzzle interessant. Sie haben immer das Gefühl, nur ein, zwei sinnvolle Züge zu haben, und trotzdem verbirgt ein 3×3-Brett 181.440 verschiedene lösbare Anordnungen. (Die andere Hälfte — die unlösbaren — ist Thema einer eigenen Anleitung zur Parität.)
Die Standardstrategie für die Hand
Der Trick, auf den die meisten Menschen kommen und der bis hinauf zu 4×4, 5×5 und weiter funktioniert, lautet so:
- Lösen Sie zuerst die obere Zeile — bringen Sie 1, 2, 3 in Position und stören Sie sie nie wieder.
- Lösen Sie als Nächstes die linke Spalte — platzieren Sie 4 und 7. Jetzt sind die obere Zeile und die linke Spalte verriegelt.
- Das verbleibende 2×2 — drei Plättchen und eine Lücke — hat genau zwei Zustände: gelöst oder ein Plättchen daneben. Ist es daneben, lässt sich das innerhalb des 2×2 von einer lösbaren Startposition aus nicht mehr beheben; Sie müssen in das Puzzle zurückgreifen. (Deshalb spielt die Parität eine Rolle.)
Das Schwierige ist, das letzte Plättchen jeder Zeile oder Spalte zu platzieren. Um die 3 in die rechte obere Ecke zu setzen, müssen Sie meist zuerst die 2 in die rechte obere Ecke schieben, dann die 3 darunter rotieren, dann das Paar in Position drehen. Dieses kleine L-förmige Manöver ist derselbe Zug, den Sie beim 15-Puzzle, beim 24-Puzzle und bei jeder anderen Größe verwenden werden.
Optimale Lösungen sind kurz
Das schwierigste mögliche 8-Puzzle braucht 31 Züge. Das gilt über alle 181.440 Startpositionen hinweg — die schlimmste ist nicht weiter vom Ziel entfernt als 31 einzelne Schiebezüge.
Eine durchschnittliche Position braucht etwa 22 Züge. Ein Computer mit A*-Suche und einer guten Heuristik findet die optimale Antwort in Millisekunden. Per Hand kann jemand, der die Zeilenstrategie kennt, jedes 8-Puzzle in deutlich unter einer Minute lösen, sobald er das Muster erkannt hat.
Warum Informatiker es lieben
Das 8-Puzzle ist der Standard-Einstiegs-Benchmark für heuristische Suche. Das Brett ist klein genug, um es vollständig aufzuzählen, groß genug, dass Brute Force verschwenderisch ist, und reichhaltig genug, um den Unterschied zwischen zwei bekannten Heuristiken zu zeigen:
- Falsch platzierte Plättchen — zählen, wie viele Plättchen nicht an ihrer Zielposition stehen. Billig zu berechnen, schwache Orientierung.
- Manhattan-Distanz — für jedes Plättchen die Zeilen- und Spaltendistanz zum Ziel summieren. Stärkere Orientierung, immer noch billig.
Eine Lehrbuch-Implementierung von A* mit Manhattan-Distanz löst jedes 8-Puzzle in Mikrosekunden. Bei einem Wechsel zum 15-Puzzle braucht es additive Mustertabellen, damit es schnell bleibt — das ist ein größeres Gespräch und lebt im 15-Puzzle-Solver-Artikel.
Wann das 8-Puzzle spielen
Ein 3×3-Brett ist ein stilles Vergnügen. Es gibt nicht viel zu überlegen, die Gewinnbedingung ist offensichtlich, und eine Partie dauert ein bis zwei Minuten. Es ist die richtige Größe für:
- Ein Kind, das lernt, wie sich „einen Zug vorausplanen“ anfühlt.
- Einen Erwachsenen, der im Bus fährt und kein langes Puzzle in den Händen will.
- Eine Übungsrunde, bevor man auf das 15-Puzzle aufsteigt.
Es ist auch die Größe, die in Schiebepuzzle-Apps fast immer kostenlos ist, unsere eingeschlossen — die größeren Bretter sitzen meist hinter einer Bezahlschranke, weil sie länger dauern und mehr Sitzungen erzeugen, aber 3×3 ist die Einstiegsstufe für alle.
Was sich bei 4×4 ändert
In der Strategie ändert sich nichts. Lösen Sie die obere Zeile, dann die linke Spalte, dann rekursiv das verbleibende 3×3. Was sich ändert, ist die Zeit: ein 8-Puzzle in 30 Sekunden wird zu einem 15-Puzzle in 5–10 Minuten. Die Zahlen werden danach schlimmer — die 5×5- und 6×6-Größen verlangen ernsthafte Geduld.
Wenn 8-Puzzles nach einer Woche langweilig werden, ist das das Signal, eine Stufe höher zu gehen.