Schiebepuzzle-Löser — jedes 3×3-, 4×4- und 5×5-Brett online lösen

So verwenden Sie den Löser

Das Tool oben löst jedes lösbare 3×3- oder 4×4-Brett optimal — die Antwort, die es zurückgibt, ist die kürzestmögliche Zugfolge, nicht bloß irgendeine, die funktioniert.

1. Drücken Sie Bearbeiten und geben Sie Ihr Brett ein: Nummerieren Sie die Plättchen so, wie sie im fertigen Puzzle zu lesen sind (oben links ist die 1), und platzieren Sie sie dort, wo sie gerade stehen. Sie lösen ein Bildpuzzle — aus einem Spiel, einer Foto-App, einem Holzspielzeug? Nummerieren Sie das fertige Bild zuerst gedanklich von oben links nach unten rechts.
2. Drücken Sie Lösen. Die Zugliste erscheint bei 3×3-Brettern sofort und bei 4×4 innerhalb weniger Augenblicke.
3. Spielen Sie die Züge auf Ihrem echten Puzzle nach, einen nach dem anderen.

Wenn der Löser meldet, das Brett sei unlösbar, ist das kein Fehler — genau die Hälfte aller Anordnungen lässt sich nie lösen, und keine Folge regulärer Züge kann das ändern. Sie möchten lieber die Technik lernen, statt Züge abzulesen? Die menschliche Methode steht hier.

Wie ein Schiebepuzzle-Löser funktioniert — sechs Algorithmen im Vergleich

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.