Es gibt zwei Wege, ein 15-Puzzle zu lösen. Einer ist der Weg, den jeder Spieler irgendwann findet — obere Zeile lösen, dann linke Spalte, rekursiv. Der andere ist der Weg, den Computer gehen: eine heuristische Suche durch Millionen Zustände, geleitet von einer cleveren Untergrenze für die verbleibenden Züge.
Dieser Leitfaden behandelt beides, ungefähr in der Reihenfolge, in der die meisten Menschen sie lernen.
Das 15-Puzzle in einem Absatz
Ein 4×4-Brett, fünfzehn nummerierte Plättchen, eine leere Zelle. Sie schieben Plättchen in die Lücke, bis die Zahlen geordnet sind — 1 bis 15, leeres Feld unten rechts. Das Brett wurde 1874 von Noyes Chapman erfunden und wurde in den 1880ern zum internationalen Wahn, nachdem Sam Loyd 1000 Dollar für das Lösen einer unlösbaren Variante bot. Es ist im Grunde dasselbe Puzzle wie das 8-Puzzle — nur eine Zeile und eine Spalte größer.
Per Hand lösen: die Zeilen-und-Spalten-Methode
Die Technik, die jeder Mensch irgendwann findet:
- Zeile 1 lösen. 1 und 2 platzieren. Dann 3 in die rechte obere Ecke. Das L-förmige Manöver — 4 in Position 3 bringen, 3 darunter schieben, dann das Paar in die Ecke drehen — ist der Trick, der Ecken möglich macht.
- Spalte 1 lösen. 5 platzieren, dann 9, dann 13 in der unteren linken Ecke mit demselben L-Eck-Trick.
- Rekursion. Übrig bleibt ein 3×3-Sub-Puzzle (mit der rechten Spalte und unteren Zeile), das einfach ein 8-Puzzle ist, das Sie schon zu lösen wissen.
Ein sicherer Spieler löst ein 15-Puzzle per Hand in 3–5 Minuten. Ein neuer Spieler kann beim ersten Mal 20 Minuten brauchen und beim dritten Mal ein Drittel davon.
Dieselbe Methode skaliert auf 5×5 und 6×6. Die Rekursion landet immer bei einem 3×3-Endspiel.
Optimaler Solver: A* mit Manhattan-Distanz
Ein Computer kann deutlich besser als die Zeilen-und-Spalten-Methode. Konkret: er kann die kürzeste Lösung finden, was Menschen selten spielen.
Die mathematische Tatsache: Das mediane 15-Puzzle braucht beim optimalen Lösen etwa 52 Einzelschiebezüge. Der schlechteste Fall sind 80. Die Zeilen-und-Spalten-Methode braucht typisch 100–150 Züge auf demselben Brett.
Um eine optimale Lösung zu finden, behandelt A*-Suche jeden Brettzustand als Knoten, jeden Zug als Kante, und fragt: wie viele Züge bis zum Ziel, mindestens? Die minimale Zahl verbleibender Züge ist nicht exakt berechenbar, ohne das Puzzle zu lösen, aber eine gute Untergrenze macht A* schnell.
Die klassische Untergrenze ist die Manhattan-Distanz:
Für jedes Plättchen die Zeilendistanz plus die Spaltendistanz von seiner aktuellen Position zu seiner Zielposition summieren. (Die Lücke wird ignoriert.)
Manhattan-Distanz ist zulässig — sie überschätzt nie die tatsächliche Distanz, weil jedes Plättchen mindestens so weit reisen muss. Mit A* und Manhattan-Distanz löst sich das 8-Puzzle in Mikrosekunden und das 15-Puzzle in Sekunden.
IDA*: der speicherfreundliche Cousin
A* muss sich jeden erkundeten Zustand merken. Für 15-Puzzles bedeutet das Hunderte Megabyte RAM bei den schwersten Brettern. Iterative-Deepening A (IDA)** tauscht Speicher gegen Zeit, indem es tiefen-begrenzte DFS mit der Heuristik macht und die Tiefenbegrenzung jede Runde erhöht.
IDA* ist das, was jeder Referenz-Solver für das 15-Puzzle tatsächlich benutzt. Richard Korfs Arbeit von 1985 führte IDA* genau ein, um 15-Puzzles auf Anfang-80er-Hardware optimal zu lösen.
Jenseits von Manhattan: Walking Distance und Mustertabellen
Manhattan-Distanz ist schnell, aber locker. Sie nimmt an, dass Plättchen einander durchdringen können. Sie können nicht — zwei Plättchen in derselben Zeile müssen sich abwechseln, was Extrazüge kostet.
Walking Distance zählt diese Extrazüge. Berechnen Sie für jedes Zeilenpaar die minimale Anzahl von „Zeilentausch“-Operationen vor, die nötig sind, um die Plättchen in die richtigen Zeilen zu permutieren. Dasselbe für Spalten. Addieren Sie beide. Das Ergebnis ist beweisbar enger als die Manhattan-Distanz — typischerweise rund 25 % größer, was bedeutet, dass A*/IDA* 25 % weniger Knoten erkundet.
Die stärkste bekannte Heuristik für das 15-Puzzle ist die additive disjunkte Mustertabelle:
- Plättchen in disjunkte Gruppen partitionieren (eine übliche Aufteilung ist 5-5-5 plus die Lücke).
- Für jede Gruppe für jede mögliche Anordnung der Plättchen dieser Gruppe auf dem Brett die minimale Zugzahl vorberechnen, um die Plättchen der Gruppe in ihre Zielpositionen zu bringen, andere Plättchen ignorierend.
- Zur Suchzeit die Lookups jeder Gruppe addieren.
Eine 7+8-Partition für das 15-Puzzle braucht etwa 1 GB Speicher, lässt IDA* aber jedes 15-Puzzle in Millisekunden lösen. Für das 24-Puzzle (5×5) sind Mustertabellen im Wesentlichen der einzige praktikable Ansatz.
Warum Handlösen für eine Partie meist schneller ist
Ein kurzer Realitätscheck: Eine A*-Implementierung zu schreiben, eine Heuristik zu wählen und auf das Ergebnis zu warten dauert länger, als ein einzelnes 15-Puzzle in die Hand zu nehmen und per Hand zu lösen. Die Mathematik ist interessant; das Praktische ist, dass jemand, der die Zeilen-und-Spalten-Methode kennt, jedes einzelne Brett in fünf Minuten löst.
Der Grund, warum Solver wichtig sind, ist die Summe: Forschungsarbeiten, die Heuristiken über Tausende zufälliger Instanzen vergleichen; KI-Lehrbücher, die das 15-Puzzle als Benchmark verwenden; und Apps, die Puzzles erzeugen müssen, die ungefähr in N Zügen garantiert lösbar sind zur Schwierigkeits-Kalibrierung.
Empfohlene Lese-Reihenfolge
Wenn Sie hier sind, um einen Solver zu schreiben: beginnen Sie mit A*/Manhattan, sehen Sie zu, wie es ein paar 8-Puzzles löst, dann portieren Sie auf IDA* für 15-Puzzles. Danach ist Walking Distance ein 100-Zeilen-Zusatz, der die Geschwindigkeit verdoppelt. Mustertabellen sind ein Wochenend-Projekt, das eine weitere Größenordnung an Geschwindigkeit bringt.
Wenn Sie hier sind, um ein 15-Puzzle zu spielen, lernen Sie zuerst die Zeilen-und-Spalten-Methode, lesen Sie dann, warum manche Bretter unlösbar sind, und kommen Sie dann hierher für die Theorie zurück.