Wenn Sie einen Schiebepuzzle-Solver implementieren und nicht sicher sind, welchen Algorithmus Sie nehmen sollen, vergleicht dieser Artikel sechs bekannte nach Geschwindigkeit, Speicher, Code-Komplexität und der sinnvollen Brettgröße. Die Antworten sind für 3×3, 4×4 und 5×5 verschieden.
1. Breadth-First Search (BFS)
Der dümmste korrekte Algorithmus. Zustände ebenenweise erkunden, bis Sie das Ziel finden.
- Zeit — exponentiell in der Lösungstiefe. Für 8-Puzzle endet er in Sekundenbruchteilen. Für 15-Puzzle endet er nicht, bevor dem Computer der RAM ausgeht.
- Speicher — hält die gesamte besuchte Menge im Speicher. Zehn Millionen Zustände für schwere 15-Puzzles.
- Code-Komplexität — zwanzig Zeilen.
- Verdikt — okay für 3×3, darüber hinaus nutzlos.
2. A* mit Manhattan-Distanz
Der erste echte Algorithmus. Dieselbe Struktur wie BFS, aber Zustände werden aus einer nach f = g + h geordneten Prioritäts-Warteschlange gezogen, wobei h die Manhattan-Distanz-Heuristik ist.
- Zeit — Millisekunden für 8-Puzzle, Sekunden bis Minuten für 15-Puzzle.
- Speicher — hält weiterhin alles Erkundete im Speicher; handhabbar für 8, schmerzhaft für 15.
- Code-Komplexität — fünfzig Zeilen, meist Prioritätswarteschlangen-Infrastruktur.
- Verdikt — das richtige Werkzeug für 8-Puzzle. Grenzwertig für 15.
3. A* mit Manhattan + Linear Conflict
Pro Paar Plättchen in derselben Zeile, die beide zu dieser Zeile gehören, aber in falscher Reihenfolge, 2 Züge zur Heuristik addieren. Sie müssen aneinander vorbei, was Manhattan-Distanz nicht sieht.
- Zeit — typisch 5–15 % schneller als reines Manhattan-A*.
- Speicher — unverändert.
- Code-Komplexität — sechzig Zeilen.
- Verdikt — strikt besser als reines Manhattan-A*. Immer verwenden.
4. IDA* mit Manhattan + Linear Conflict
Iterative-Deepening A*. Tiefenbegrenztes DFS mit f-Kosten als Tiefenmaß, Limit pro Iteration anheben. Speicher gegen Zeit tauschen durch erneutes Erkunden.
- Zeit — leicht langsamer pro Knoten als A* wegen Wiederholungen, aber der geringere Speicherdruck gewinnt meist bei schweren 15-Puzzles.
- Speicher — O(Tiefe), nicht O(erkundeter Zustände). Das ist der Gewinn.
- Code-Komplexität — achtzig Zeilen (rekursives DFS, Schwellen-Management).
- Verdikt — das richtige Werkzeug für 4×4. Standard seit Korf 1985.
5. IDA* mit Walking Distance
Walking Distance ist eine engere Heuristik. Berechnen Sie für jede Plättchen-Anordnung projiziert nur auf Zeilen die minimale Anzahl von Zeilentausch-Operationen vor, um jedes Plättchen in die richtige Zeile zu bringen. Dasselbe für Spalten. Addieren.
Sie fängt ein, was Manhattan verfehlt: Plättchen in derselben Zeile, die um denselben Slot „kämpfen“.
- Zeit — typisch 2× schneller als Manhattan + Linear Conflict bei schweren 15-Puzzles, weil die Heuristik enger ist und IDA* mehr beschneidet.
- Speicher — fügt eine kleine vorberechnete Tabelle hinzu (~500 KB für 4×4).
- Code-Komplexität — 150 Zeilen. Die Vorberechnung ist ein BFS auf einem reduzierten Zustandsraum.
- Verdikt — das richtige Werkzeug für 4×4, wenn Sie Engineering-Budget haben. Die erste nicht-triviale Verbesserung.
6. IDA* mit additiven disjunkten Mustertabellen
Die stärkste bekannte Heuristik für Schiebepuzzles. Plättchen in disjunkte Gruppen partitionieren (eine übliche 15-Puzzle-Partition ist 7+8 oder 5+5+5). Für jede Gruppe die Kosten vorberechnen, die Plättchen der Gruppe in ihre Zielpositionen zu permutieren über alle möglichen Anordnungen dieser Gruppe. Zur Suchzeit den Beitrag jeder Gruppe nachschlagen und addieren.
- Zeit — löst das schwerste 15-Puzzle in Millisekunden. Löst zufällige 24-Puzzles in Sekunden.
- Speicher — erheblich. Eine 7+8-Partition für 15-Puzzle ist etwa 1 GB. 5+5+5+9 für 24-Puzzle ist etwa 4 GB. Speicher dominiert das Engineering.
- Code-Komplexität — 300+ Zeilen. Die Vorberechnung nutzt retrograde BFS über den Gruppen-Zustandsraum und macht den Großteil der Arbeit.
- Verdikt — das richtige Werkzeug für 5×5 und 6×6. Übertrieben für 3×3.
Zusammengefasste Empfehlungen
Wenn Sie heute einen Solver schreiben:
- Für 3×3, A* mit Manhattan + Linear Conflict. Alles andere ist Over-Engineering.
- Für 4×4, IDA* mit Walking Distance. Mustertabellen bringen bei dieser Größe marginale Gewinne; der Engineering-Aufwand lohnt nicht.
- Für 5×5, IDA* mit additiven Mustertabellen (5+5+5+9 Standard). Ohne Mustertabellen Timeout bei den schwersten Instanzen.
- Für 6×6 (35-Puzzle) können dieselben Algorithmen zufällige Instanzen lösen, aber die schwersten Fälle sind noch offene Forschungsfragen. Die meisten Apps versuchen es nicht.
Was ist mit Machine Learning?
Eine vernünftige Frage 2026. Neuronale-Netz-Heuristiken werden seit mindestens 2014 studiert und können schnelle Heuristiken für Schiebepuzzles erzeugen. Der Haken: Sie sind meist nicht zulässig — können überschätzen, was bedeutet, dass der resultierende Algorithmus nicht mehr garantiert optimal ist. Für App-Entwickler, die garantiert optimale Lösungen zur Schwierigkeits-Kalibrierung brauchen, bleiben klassische Mustertabellen das richtige Werkzeug.
Für Forschungsinteresse bringen Mustertabellen, die von einem neuronalen Netz trainiert wurden, leichte Beschleunigungen bei den schwersten 15-Puzzle-Instanzen. Nützlich für akademische Arbeiten, marginal für ausgelieferte Software.
Was in eine echte App geht
Eine produktive mobile App, die einen Solver für Hinweisgenerierung braucht, landet fast immer bei:
- IDA* + Walking Distance für 4×4.
- IDA* + eine kleine Mustertabelle für 5×5.
- Ein einzelner Nur-nächster-Zug-Aufruf vom Hinweis-Button.
- Alles läuft on-device. Der ganze Solver sind ein paar hundert Kilobyte Code plus ein paar Megabyte vorberechneter Tabellen.
Das ist der richtige pragmatische Stack für ein ruhiges Telefon-App. Slide Puzzles Hinweis-Button funktioniert genau so.