8 Puzzles

Das 8-Puzzle ist die kleinere Variante des 15-Puzzles und wird auf einem 3×3-Raster mit Plättchen gespielt, die von 1 bis 8 nummeriert sind, sowie einem leeren Feld. Das Ziel besteht darin, die Steine in das leere Feld zu schieben, um sie in numerischer Reihenfolge anzuordnen. Trotz seiner kompakten Größe bietet das 8-Puzzle eine lohnende Herausforderung und nimmt in der Informatik einen besonderen Platz ein, da es zu den am häufigsten untersuchten Problemen bei Suchalgorithmen der künstlichen Intelligenz zählt.

Regeln

1. Das Spielfeld ist ein 3x3-Raster mit Spielsteinen, die von 1 bis 8 nummeriert sind, sowie einem leeren Feld.
2. Schiebe einen beliebigen Spielstein, der an das leere Feld angrenzt, in das leere Feld.
3. Es darf jeweils nur ein Spielstein verschoben werden, entweder horizontal oder vertikal.
4. Ordne die Spielsteine wie folgt an: 1–3 in der obersten Reihe, 4–6 in der mittleren Reihe, 7–8 und das leere Feld in der untersten Reihe (unten rechts leer).

Strategien

• Zuerst die oberste Reihe: Platziere die Steine 1, 2 und 3 in der obersten Reihe. Sobald sie feststehen, sollten sie nicht mehr verschoben werden müssen.
• Als Nächstes die linke Spalte: Platziere die Steine 4 und 7 in der linken Spalte (falls dies nicht bereits beim Lösen der obersten Reihe geschehen ist).
• Die Ecke fertigstellen: Die verbleibenden Steine (5, 6, 8) und das leere Feld bilden einen kleinen 2×2-Bereich, der durch zyklisches Verschieben der Steine gelöst werden kann.
• Zyklischer Zug: Wenn die letzten Steine neu angeordnet werden müssen, rotieren Sie sie zyklisch um das leere Feld herum, bis sie die richtigen Positionen erreichen.
• Lösbarkeitsprüfung: Genau die Hälfte aller möglichen Konfigurationen ist lösbar. Zähle die Anzahl der Inversionen (Kacheln, die vor ihrem natürlichen Vorgänger erscheinen). Ist die Anzahl gerade, ist das Puzzle lösbar; ist sie ungerade, ist es nicht lösbar.
• Manhattan-Abstand: Berechne für jede Kachel, wie viele Züge sie von ihrer Zielposition entfernt ist (horizontal + vertikal). Die Summe ergibt eine Untergrenze für die Anzahl der benötigten Züge. Nutze dies, um einzuschätzen, wie nah du der Lösung bist.

Das 8-Puzzle ist ein direkter Nachfahre des 15-Puzzles, dessen Raster von 4×4 auf 3×3 verkleinert wurde. Während das 15-Puzzle ab 1880 die Aufmerksamkeit der Öffentlichkeit auf sich zog, rückte das kleinere 8-Puzzle in den Fokus der wissenschaftlichen Forschung, insbesondere auf dem Gebiet der künstlichen Intelligenz.

In den 1960er- und 1970er-Jahren übernahmen KI-Forscher das 8-Puzzle als Standard-Benchmark zum Testen von Suchalgorithmen. Sein Zustandsraum ist klein genug, um vollständig erkundet zu werden (181.440 erreichbare Zustände von 362.880 möglichen Permutationen), und dennoch komplex genug, um die Effizienz verschiedener Ansätze zu testen. Das Puzzle wurde verwendet, um die Breiten- und Tiefensuche, die iterative Vertiefung sowie den berühmten A*-Algorithmus zu veranschaulichen und zu vergleichen, der 1968 von Peter Hart, Nils Nilsson und Bertram Raphael entwickelt wurde.

Der A*-Algorithmus kann in Kombination mit der Manhattan-Distanz-Heuristik jede lösbare 8-Puzzle-Konfiguration optimal lösen – also die minimale Anzahl an Zügen ermitteln. Die maximale Anzahl an Zügen, die zum Lösen einer beliebigen lösbaren Konfiguration benötigt wird, beträgt 31, und der Durchschnitt liegt bei etwa 22 Zügen. Diese Ergebnisse wurden durch erschöpfende Computersuchen ermittelt.

Das 8-Puzzle ist nach wie vor ein fester Bestandteil von Einführungskursen in KI und Algorithmen an Universitäten weltweit. Studierende implementieren Suchalgorithmen anhand des Puzzles, um Konzepte wie Heuristiken, optimale Pfade und die Erkundung des Zustandsraums zu verstehen. Es dient als Einstieg in das Verständnis komplexerer Probleme in den Bereichen Planung, Robotik und Optimierung. Über den akademischen Bereich hinaus ist das 8-Puzzle ein beliebtes Freizeitpuzzle, das in Spielzeuggeschäften, in mobilen Apps und als Minispiel in größeren Videospielen zu finden ist.