Das 15-Puzzle ist seit den 1960ern ein Benchmark für KI-Suchalgorithmen. Jede Algorithmengeneration wurde erfunden, um die Wand zu durchbrechen, gegen die die vorige stieß. Dieser Artikel geht sie in Erfindungsreihenfolge durch, mit Begründungen, wofür jeder gut war und was den nächsten nötig machte.
1960er — Breadth-First Search
Der erste Algorithmus, den jeder probiert. Zustände ebenenweise erkunden: Tiefe 1 hat 4 Zustände, Tiefe 2 hat 16, Tiefe 3 hat 64, und so weiter. Erkunden, bis Sie das Ziel finden.
Für das 8-Puzzle endet BFS schnell — die schlimmste Tiefe ist 31, also höchstens 4³¹ Zustände (viel weniger in der Praxis durch Wiederholungen). Für das 15-Puzzle ist die schlimmste Tiefe 80, also 4⁸⁰ Zustände. Das sind mehr Zustände als Atome im beobachtbaren Universum. BFS endet nicht.
Die Wand: exponentielle Explosion. Lösen mit uninformierter Suche ist jenseits von 3×3 hoffnungslos.
1968 — A*-Suche
Hart, Nilsson und Raphael veröffentlichen A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Die Idee: statt Zustände in Reihenfolge der Distanz vom Start zu erkunden, in Reihenfolge von f = g + h, wobei h eine Untergrenze-Schätzung der verbleibenden Distanz ist.
Für das 15-Puzzle ist h die Manhattan-Distanz — Summe der Zeilen-plus-Spalten-Distanzen jedes Plättchens zum Ziel. Manhattan ist zulässig (überschätzt nie) und konsistent (erfüllt eine Dreiecksungleichung). Mit diesen Eigenschaften findet A* die optimale Lösung.
Leistung auf dem 15-Puzzle: löst jedes Brett, aber auf den schwersten Instanzen erkundet es Millionen Zustände und verbraucht Hunderte Megabyte Speicher. Die Wand: Speicher.
1985 — IDA*
Richard Korfs Depth-first iterative-deepening: An optimal admissible tree search. Die Einsicht: statt A*s Prioritätswarteschlange (die alle erkundeten Zustände hält), iterativ vertiefende DFS, bei der die Tiefengrenze die f-Kosten sind, nicht die Tiefe.
IDA* erkundet dieselben Zustände wie A*, ungefähr in derselben Reihenfolge, aber ohne Erinnerung zwischen Iterationen. Jeder „Tiefen-Sweep“ verwendet O(Tiefe) Speicher statt O(erkundeter Zustände).
Leistung auf dem 15-Puzzle: löst jedes Brett in Sekunden auf Hardware von 1985, passt in Kilobyte Speicher. Die Wand: Die Heuristik ist immer noch Manhattan. Suche beschleunigen verlangt eine engere Heuristik.
1990er — Linear Conflict
Hansson, Mayer und Yungs Criticizing solutions to relaxed models yields powerful admissible heuristics. Die Manhattan-Heuristik nimmt an, dass Plättchen einander durchdringen können. Sie können nicht.
Linear Conflict addiert 2 Züge zur Heuristik für jedes Paar Plättchen in derselben Zeile, die beide zu dieser Zeile gehören, aber in falscher Reihenfolge sind — eines muss aus der Zeile, damit das andere passieren kann. Analog für Spalten.
Effekt: typisch 5–15 % Reduktion expandierter Knoten bei schweren 15-Puzzles. Strikte Verbesserung gegenüber reinem Manhattan; kein echter Nachteil.
1996 — Walking Distance
Eine Heuristik, die die Struktur des Puzzles tiefer einfängt. Für jede Plättchen-Anordnung projiziert nur auf Zeilen (Position innerhalb der Zeile ignorierend) die minimale Anzahl von Zeilentausch-Operationen vorberechnen, um jedes Plättchen in die richtige Zeile zu bringen. Dasselbe für Spalten.
Walking Distance ist zulässig und deutlich enger als Manhattan + Linear Conflict — typisch 1,5–2× der Manhattan-Wert, was bedeutet, dass IDA* weit weniger Knoten expandiert.
Implementierungskosten: eine kleine vorberechnete Tabelle (~500 KB für 4×4). Sweetspot für das 15-Puzzle.
2002 — Additive disjunkte Mustertabellen
Korf und Felners Disjoint pattern database heuristics. Die stärkste bekannte Heuristik für Schiebepuzzles.
Die Idee: Plättchen in disjunkte Gruppen partitionieren (eine 7+8-Partition für das 15-Puzzle ist Standard). Für jede Gruppe die optimalen Kosten, nur die Plättchen dieser Gruppe in ihre Zielpositionen zu bringen, vorberechnen, andere Plättchen ignorierend. Jede mögliche Anordnung der Gruppe tabellieren.
Zur Suchzeit den Beitrag jeder Gruppe nachschlagen und addieren. Wegen der Disjunktheit und einem sorgfältigen Argument, dass die für jede Gruppe nötigen Züge nicht konfligieren, ist die Summe zulässig.
Speicher-Kosten: etwa 1 GB für das 15-Puzzle. Leistung: löst das schwerste 15-Puzzle in ein paar tausend Knoten-Expansionen — Millisekunden.
2005+ — größere Mustertabellen für größere Puzzles
Dieselbe Technik skaliert auf das 24-Puzzle (5×5) und darüber hinaus. Eine 5+5+5+9-Partition für das 24-Puzzle ist etwa 4 GB. Damit löst sich jedes zufällige 24-Puzzle in Sekunden.
Das 35-Puzzle (6×6) ist am Rand des Machbaren. Die schwersten 6×6-Instanzen sind 2026 noch offene Forschung.
2010er+ — neuronale Heuristiken
Neuronale Netze werden trainiert, die Manhattan-distanz-artige Größe für Schiebepuzzles zu vorhersagen, und produzieren manchmal engere Heuristiken als handgebaute. Der Haken: NN-Heuristiken sind meist nicht beweisbar zulässig, also liefern darauf gebaute Solver wahrscheinlich-optimale statt garantiert-optimale Antworten.
Für Forschungspapiere interessant. Für ausgelieferte Software, wo Optimalität zählt (Schwierigkeits-Kalibrierung in Spielen), bleiben klassische Mustertabellen das richtige Werkzeug.
Warum diese Geschichte wichtig ist
Jede Welle der Schiebepuzzle-Algorithmen-Forschung wurde von demselben Druck getrieben: Das Puzzle ist klein genug, um Algorithmen zu benchmarken, groß genug, dass schlechte ein Timeout erreichen. Das 15-Puzzle war der Prüfstand für allgemeine Fortschritte in heuristischer Suche — A*, IDA*, Mustertabellen — die heute Routenplanung, Theorembeweisen und viele andere Domänen antreiben.
Wenn Sie ein 15-Puzzle in einer App über eine Hinweistaste lösen, verwenden Sie Algorithmen, die genau für dieses Spiel entwickelt und dann überall verallgemeinert wurden.
Zusammenfassende Tabelle
| Jahr | Algorithmus | Zeit für schweres 15-Puzzle | Speicher | Was ermöglicht |
|---|---|---|---|---|
| 1960er | BFS | Endet nicht | Riesig | — |
| 1968 | A* + Manhattan | Minuten | Hunderte MB | Heuristische Suche |
| 1985 | IDA* + Manhattan | Sekunden | KB | Iterative Vertiefung |
| 1996 | IDA* + Walking Distance | < 1 s | + 500 KB Vorberechnung | Bessere Heuristik |
| 2002 | IDA* + 7+8-Mustertabelle | Millisekunden | + 1 GB Vorberechnung | Teilmengen-Enumeration |
Jede Zeile ist ein echter qualitativer Sprung, keine marginale Verbesserung. Die Geschichte des 15-Puzzle-Lösens ist auch die Geschichte moderner heuristischer Suche.