So benutzt du den Schiebepuzzle-Löser
Tippe die Zahl jedes Steins dort ein, wo er auf deinem Brett liegt, Reihe für Reihe, und lass die Lücke leer. Drück dann auf Lösen. Der Löser prüft das Brett, sucht die kürzeste Lösung und zeigt sie als Liste der Steine, die du schieben musst. Mit Abspielen siehst du sie ablaufen, oder du gehst sie mit den Pfeilen Schritt für Schritt durch. Wechsle zu Steine schieben, um das Puzzle selbst zu spielen, indem du auf Steine neben der Lücke tippst. Mischen gibt dir ein zufälliges lösbares Brett.
Für die kleinere 3-mal-3-Version wähl 8er-Puzzle. Du kannst ein Brett auch als Text einfügen, zum Beispiel 5 1 2 4 9 6 3 8 13 10 7 11 0 14 15 12, mit 0 oder _ für die Lücke.
Ist jedes Brett lösbar?
Nein: Genau die Hälfte aller Anordnungen lässt sich nicht lösen, und der Löser sagt dir das vor der Suche. Der Test zählt Inversionen: Lies die Steine Reihe für Reihe und zähle die Paare, bei denen eine größere Zahl vor einer kleineren steht.
- 8er-Puzzle (3 x 3): lösbar genau dann, wenn die Zahl der Inversionen gerade ist. Ein Schub entlang einer Reihe ändert nichts; ein Schub nach oben oder unten bewegt einen Stein über zwei andere hinweg und ändert die Zahl um 0 oder 2.
- 15er-Puzzle (4 x 4): Ein senkrechter Schub bewegt einen Stein über drei andere hinweg, die Zahl der Inversionen ändert sich also um eine ungerade Zahl, während die Lücke eine Reihe wandert. Inversionen plus die Reihe der Lücke, von unten gezählt, behalten deshalb immer ihre Parität, und auf dem gelösten Brett ist die Summe ungerade. Ein Brett, bei dem sie gerade ist, lässt sich nie lösen.
Das berühmte Beispiel ist ein gelöstes Brett, bei dem 14 und 15 vertauscht sind: eine Inversion, Lücke in der untersten Reihe, Summe 2, gerade, also unmöglich.
Wie der Löser die kürzeste Lösung findet
Der Löser nutzt IDA* (iterativ vertiefendes A*), eine Suche, die alle Lösungen bis zu einer Längengrenze durchprobiert und die Grenze erhöht, bis eine passt. Gelenkt wird sie von einer Schätzung der noch nötigen Züge, die nie zu hoch liegt; genau das sorgt dafür, dass die erste gefundene Lösung eine kürzeste ist.
- Beim 8er-Puzzle ist die Schätzung die Manhattan-Distanz (wie weit jeder Stein von seinem Platz entfernt ist, in Reihen plus Spalten) plus eine Korrektur für Steine, die sich in ihrer eigenen Reihe oder Spalte gegenseitig blockieren (lineare Konflikte). Jedes 8er-Puzzle wird in Sekundenbruchteilen optimal gelöst.
- Beim 15er-Puzzle werden leichte Bretter genauso gelöst; für schwerere baut der Löser drei Musterdatenbanken auf: exakte Zugzahlen für jede Lage der Steine 1, 5, 6, 9, 10, 13, der Steine 7, 8, 11, 12, 14, 15 und der Steine 2, 3, 4. Zusammengezählt und zusätzlich am entlang der Diagonale gespiegelten Brett geprüft, ergeben sie eine viel genauere Schätzung. Der Aufbau dauert ein, zwei Sekunden, in deinem Browser.
Die meisten zufälligen 15er-Puzzles werden innerhalb weniger Sekunden optimal gelöst. Die schwersten Stellungen brauchen bis zu 80 Züge und können viel länger dauern, deshalb hat die Suche ein Budget von 15 Sekunden. Läuft es ab, wechselt der Löser zu einem schnellen Verfahren (erste Reihe, dann erste Spalte, dann das übrige 3 x 3 optimal) und kennzeichnet diese Lösung als nicht die kürzeste.
Im Test stimmten die Ergebnisse beim 8er-Puzzle mit einer vollständigen Tabelle der exakten Abstände aller 181.440 lösbaren Stellungen überein, die Ergebnisse beim 15er-Puzzle mit einer zweiten, unabhängigen Suche, und jede Lösung wurde Stein für Stein nachgespielt.
Ein Beispiel
Das Beispielbrett 5 1 2 4 / 9 6 3 8 / 13 10 7 11 / _ 14 15 12 ist in 9 Zügen gelöst: schiebe 13, 9, 5, 1, 2, 3, 7, 11, 12. Fürs 8er-Puzzle probier 8 6 7 / 2 5 4 / 3 _ 1: Es ist eine von nur zwei Stellungen des 8er-Puzzles, die 31 Züge brauchen, so viele wie kein anderes 8er-Puzzle.
Tipp fürs Lösen von Hand
Löse zuerst die oberste Reihe, dann die linke Spalte, und lass sie danach in Ruhe: Was übrig bleibt, ist ein kleineres Puzzle. Die letzten beiden Steine einer Reihe setzt du gemeinsam ein, indem du den letzten unter seinem Platz parkst und beide hineindrehst.
Noch ein Rätsel für eine Person, bei dem der Löser weiterhilft, ist das Solitär-Brettspiel (Steckhalma). Und wer gern Zahlen zusammenschiebt, spielt 2048 mit KI-Helfer.
Löser getestet am . Fehler gefunden? Schreib uns.
Häufige Fragen
Warum lässt sich mein Schiebepuzzle nicht lösen?
Die Hälfte aller Anordnungen ist durch Schieben nicht erreichbar. Ist die Summe aus Inversionen und der Reihe der Lücke (von unten gezählt) gerade, löst keine Folge von Schüben das Brett. Bei einem echten Puzzle passiert das, wenn zwei Steine herausgenommen und vertauscht wurden. Vertausch zwei beliebige Steine, und es wird lösbar.
Wie viele Züge braucht ein 15er-Puzzle höchstens?
80 Züge mit einzelnen Steinen. Computersuchen haben gezeigt, dass sich jede lösbare Stellung des 15er-Puzzles in höchstens 80 Zügen lösen lässt und dass manche Stellungen alle 80 brauchen. Beim 8er-Puzzle liegt das Maximum bei 31.
Ist die Lösung wirklich die kürzeste?
Wenn das Ergebnis sie als bewiesen optimal bezeichnet, ja: Die Suche hat geprüft, dass es keine kürzere Lösung gibt. Läuft das Budget von 15 Sekunden bei einem sehr schweren Brett ab, bekommst du stattdessen eine schnelle Lösung, deutlich als nicht die kürzeste gekennzeichnet.
Wie zähle ich Inversionen?
Lies die Steine Reihe für Reihe und lass die Lücke aus. Zähle für jeden Stein, wie viele Steine nach ihm eine kleinere Zahl haben. Addiere all diese Zahlen.
Schickt der Löser mein Brett irgendwohin?
Nein. Die Suche läuft in deinem Browser in einem Hintergrund-Thread; nichts wird hochgeladen.