Ein Schiebepuzzle-Solver ist ein Programm, das zu jeder lösbaren Startposition eine Folge von Zügen ausgibt, die zum Ziel führt. Es ist ein Werkzeug mit zwei Zielgruppen: Spieler, die feststecken, und Entwickler, die eine Schiebepuzzle-App ausliefern müssen.
Die beiden Zielgruppen wollen sehr unterschiedliche Dinge.
Warum Spieler fast nie einen Solver brauchen
Wenn Sie an einem Schiebepuzzle feststecken, ist die ehrliche Lösung meist nicht „einen Solver laufen lassen“. Es ist eines von drei Dingen:
- Die Zeilen-und-Spalten-Methode lernen. Die meisten, die aufgeben, sind die, die die kanonische Strategie nie gelernt haben. (Beginnen Sie mit dem 8-Puzzle, dann nach oben skalieren.)
- Prüfen, dass das Puzzle lösbar ist. Wenn Sie keine Lösung finden, egal was Sie tun, hat die App vielleicht ein unlösbares Brett erzeugt. Schnell verifizierbar.
- Einen Hinweis nutzen, keine Komplettlösung. Der nächste Einzelzug reicht meist, um aus der Sackgasse zu kommen. Apps, die Hinweise anbieten (unsere tut es, in Premium), berechnen meist einen Zug auf Anfrage, keine ganze Lösung.
Eine Komplettlösung lehrt Sie selten etwas Nützliches, weil der Solver eine optimale Folge produziert — typisch 52 Züge für ein schweres 15-Puzzle — und 52 optimalen Zügen beim Vorbeirauschen auf dem Handy zuzusehen, baut keine Intuition auf.
Der Hinweis ist die richtige Einheit. Wer einen Hinweis braucht, braucht keinen Solver.
Warum Entwickler immer einen brauchen
Eine Schiebepuzzle-App zu bauen bedeutet, sich zu mehreren Zusagen zu verpflichten:
- Jedes Puzzle ist lösbar.
- Jedes Puzzle braucht ungefähr eine bestimmte Anzahl Züge (Schwierigkeits-Kalibrierung).
- Jedes Puzzle kann auf Anfrage einen Hinweis produzieren.
Keine dieser Zusagen ist ehrlich ohne einen Solver, der im Hintergrund läuft.
Lösbar-durch-Konstruktion-Generierung kann das Laufen eines Solvers während der Generierung vermeiden: vom Zielzustand rückwärts mit zufälligen legalen Zügen laufen, und Sie garantieren eine lösbare Startposition. Die meisten Apps, unsere eingeschlossen, machen genau das.
Schwierigkeits-Kalibrierung will, dass das Puzzle „interessant“ ist — weder trivial (Brett ist fast schon gelöst) noch erschöpfend (Brett braucht 60 Züge auf einem 3×3, um es zu richten). Der Standardtrick ist, genug Rückwärtszüge anzuwenden, um in der Nähe der optimalen Distanz zum Ziel zu landen — typisch 20–30 für 3×3, 40–60 für 4×4. Der Solver verifiziert die Distanz nach der Generierung.
Hinweise brauchen einen Solver, der einen guten nächsten Zug in ein paar hundert Millisekunden produziert. Das ist schneller als eine volle optimale Lösung, fordert aber dennoch echte Algorithmusarbeit.
Welche Art Solver
Die Wahl hängt von der Brettgröße ab:
| Brett | Empfohlener Algorithmus | Zeit pro Lösung |
|---|---|---|
| 3×3 | A* + Manhattan | < 1 ms |
| 4×4 | IDA* + Walking Distance | 10 ms – 1 s |
| 5×5 | IDA* + 5+5+5+9-Mustertabelle | 100 ms – Minuten |
| 6×6 | IDA* + größere Mustertabelle | Sekunden – Stunden |
Für 3×3 funktioniert sogar Brute-Force-BFS. Bei 4×4 brauchen Sie eine echte Heuristik, und Manhattan-Distanz ist Standard seit den 1980ern. Bei 5×5 brauchen Sie Mustertabellen. Bei 6×6 sind Sie in der Forschung.
Die Algorithmus-Details behandeln wir im 15-Puzzle-Solver-Artikel und im 8-Puzzle-Solver-Artikel. Algorithmusvergleich siehe Schiebeplättchen-Solver.
On-Device vs serverseitig
Mobile Apps, die einen Solver ausliefern, haben zwei Implementierungsoptionen: lokal auf dem Gerät laufen lassen oder einen Server aufrufen.
On-Device ist die ehrlichere Wahl für eine privatsphäre-respektierende App. Der Solver sind ein paar hundert Codezeilen, die Mustertabellen für 4×4 passen in ein paar Megabyte, und ein modernes Telefon löst jedes 15-Puzzle in deutlich unter einer Sekunde. Es gibt keinen Grund, einen Puzzle-Zustand an einen Server zu schicken — und nicht zu schicken ist eine der Sachen, die ein ruhiges Telefonspiel von einem unterscheiden, das Telemetrie zum Funktionieren braucht.
Serverseitig wird verwendet, wenn der App-Entwickler verfolgen will, an welchen Puzzles Nutzer hängen bleiben, oder Schwierigkeitskurven A/B-testen will. Das sind echte Produktgründe, aber sie kommen mit Privatsphärekosten und Netzwerkabhängigkeit. Apps, die ein Puzzle nicht offline lösen können, funktionieren nicht im Flugzeug.
Slide Puzzle löst vollständig on-device. Die Mustertabelle für 4×4 ist etwa 6 MB groß und lebt im App-Bundle. Die Hinweistaste benutzt sie direkt. Vom Telefon geht keine Anfrage ab.
Pragmatische Notiz
Wenn Sie hier sind und nach „einer Solver-Website suchen, in die ich mein Brett eingebe und sie sagt mir die Antwort“ — die gibt es, und sie sind meist webbasierte 8-Puzzle-Solver. Für 3×3 sind sie in Ordnung. Für 4×4 und größer ist das Nutzererlebnis unbeholfen: 16 Zahlen eintippen, einer 50-Zug-Folge zusehen, versuchen, 50 spezifische Züge auf einem physischen Brett auszuführen. Niemand hat dabei Spaß.
Die realistischen Verwendungen eines Schiebepuzzle-Solvers sind:
- Eigene Implementierung im Code verifizieren.
- Ein Test-Brettkorpus erzeugen.
- Innerhalb einer App einen Hinweis berechnen.
Außerhalb davon ist die Zeilen-und-Spalten-Methode schneller zu lernen.