Startseite / Sokoban-Solver-Algorithmus
Leitfaden zum Sokoban-Algorithmus

Sokoban-Solver-Algorithmus: Wie die Suche eine Lösung findet

Ein Sokoban-Solver macht aus dem Schiebepuzzle eine Suche durch Brettzustände. Er speichert Kisten, erreichbare Felder, mögliche Schübe und bekannte Positionen.

Dieser Leitfaden erklärt die Arbeitsweise eines Solvers. Für ein ASCII-Brett und eine Route nutze die Online-Sokoban-Lösung.

Aktualisiert am 16. November 2026Für Spieler, Leveldesigner und neugierige Programmierer

Sokoban-Brett mit Kisten, Zielen, Wänden und Zugangsfeldern

Ein Solver bewertet das Brett als Zustandsgraphen, nicht nur als Bild.

Kurzantwort: Kurz erklärt: Der Solver speichert kompakte Zustände, ermittelt per Flutfüllung die erreichbaren Felder, erzeugt legale Schübe und verwirft doppelte oder offensichtlich verlorene Stellungen. Elternverweise ermöglichen es, ein gefundenes Ziel als Zugfolge wiederzugeben.

Die wichtige Einheit ist bei Sokoban meist ein Schub, nicht ein einzelner Schritt. Gehen zwischen Schüben verändert die Spielerposition, aber keine Kiste. Deshalb lässt sich das Feld als Graph auffassen: Ein Knoten ist eine bekannte Stellung, eine Kante ein legaler Schub samt nötigem Gehweg hinter die nächste Kiste.

Der Graph ist groß, weil Schübe nicht immer rückgängig zu machen sind. Zum Bewegen einer Kiste muss der Spieler auf der Gegenseite stehen; aus einer ungünstigen Ecke kann er sie nicht herausziehen. Jeder Knoten muss erkennen lassen, welche Kisten welche Felder belegen und welche Felder ohne Kistenbewegung erreichbar sind.

Sind alle Ziele belegt, folgt der Solver den Elternverweisen bis zum Start und rekonstruiert die Route. Eine Richtungsfolge enthält viele Gehschritte, doch die entscheidenden Entscheidungen sind die Schübe, die den Zustand verändern.

Wie ein Spielfeldzustand dargestellt wird

Ein Feld enthält feste und veränderliche Daten. Wände und Ziele werden einmal eingelesen. Veränderlich sind Kistenkoordinaten und der erreichbare Spielerbereich. Zwei Spielerpositionen sind häufig gleichwertig, wenn man ohne Kistenbewegung zwischen ihnen gehen kann. Eine Normalisierung verhindert, dass gleichwertige Gehpositionen die Warteschlange füllen.

ZustandsteilGespeicherte InformationBedeutung
Wände und ZieleFeste GeometrieDefiniert begehbare Felder und die Lösungsbedingung.
KistenanordnungEine Koordinate je KisteBestimmt mögliche Schübe und Zielzuordnungen.
SpielerbereichOhne Schieben erreichbare FelderZeigt, welche Kistenseiten zugänglich sind.
Vorgänger und AktionVorheriger Zustand und SchubrichtungErmöglicht die Wiedergabe einer Lösung statt nur einer Ja-Nein-Antwort.

Eine Transpositionstabelle oder Besuchsmenge speichert einen Schlüssel je normalisiertem Zustand. Tauchen dieselbe Kistenanordnung und derselbe erreichbare Bereich erneut auf, liefert ihre erneute Untersuchung keine neue Fortsetzung. Speicher wird hier gegen Geschwindigkeit getauscht.

Sokoban-Feld zur Kistenreihenfolge mit eingeschränktem Ziel und freier Abstellfläche

Erklärendes Felddiagramm: Die Kistenreihenfolge verändert die nach jedem Schub erreichbaren Zustände. Das Bild veranschaulicht die Idee und zeigt keinen Programmcode.

Wie die Suchfront wächst

Nach dem Einlesen eines Zustands ermittelt eine Flutfüllung die begehbare Fläche. Für jede Kiste werden vier Richtungen geprüft. Ein Schub ist nur legal, wenn das Zielfeld frei und das gegenüberliegende Standfeld erreichbar ist. Danach entsteht ein neuer Zustand mit verschobener Kiste und neu berechnetem Spielerbereich.

Verschiedene Suchreihenfolgen bieten verschiedene Garantien. Die Breitensuche untersucht kurze Schubfolgen zuerst und findet bei gleichen Kantenkosten eine Lösung mit minimaler Schubzahl. Die Tiefensuche verfolgt einen Zweig weit und benötigt weniger Speicher für die Suchfront, kann aber lange in einem nutzlosen Zweig bleiben. Uniforme Kostensuche und A* können Schubkosten mit einer Heuristik verbinden; deren Qualität und Eigenschaften bestimmen die Aussagekraft des Ergebnisses.

  1. Einlesen.Wände, Ziele, Kisten und Spieler erfassen; falsche Anzahlen oder unbekannte Zeichen ablehnen.
  2. Erreichbarkeit.Alle ohne Schieben erreichbaren Felder markieren.
  3. Erweitern.Schübe mit gültigem Stand- und Zielfeld erzeugen.
  4. Beschneiden und speichern.Doppelte oder offensichtlich verlorene Zustände überspringen und Vorgänger samt Schub speichern.
  5. Beenden.Bei belegten Zielen stoppen oder melden, dass innerhalb des Limits keine Route gefunden wurde.

Nicht jeder Gehweg muss einzeln untersucht werden. Nach einem Schub reicht ein normalisierter erreichbarer Bereich aus, um die nächsten Schübe zu erzeugen. Das macht einen kompakten Browser-Solver praktikabel.

Warum Blockaden früh ausgeschlossen werden

Ohne Beschneidung verschwendet die Suche Zeit mit unlösbaren Stellungen. Die einfachste Regel betrifft eine Ecke ohne Ziel: Eine Kiste an zwei rechtwinkligen Wänden kommt nicht mehr heraus. Dieser Zweig kann sofort entfallen. Wandabschnitte ohne passendes Ziel, unbewegliche 2×2-Gruppen und Kisten, die schmale Gänge verschließen, sind weitere typische Prüfmuster.

Manche Fehler betreffen den Zugang statt einer unbeweglichen Kiste. Ein korrekt belegtes Ziel kann das einzige Standfeld für eine andere Kiste blockieren. Zwei Kisten können noch beweglich sein, obwohl die zum Trennen nötige Seite unerreichbar ist. Solche Fälle sind schwieriger zu erkennen. Praktische Solver kombinieren daher einfache Regeln, Duplikatprüfung und ein begrenztes Suchbudget.

Sokoban-Eckenblockade als Beispiel für das Beschneiden der Suche

Eine Eckenblockade ist schon vor einer tieferen Suche erkennbar. Subtilere Zugangsprobleme erfordern umfassendere Zustandsprüfungen.

Beschneidung muss korrekt sein: Eine zu aggressive Regel kann eine ungewöhnliche Gewinnroute entfernen. Kleine Browser-Werkzeuge sollten ihre Prüfgrenzen erklären, statt jede Meldung ohne Lösung als Beweis zu behandeln.

Schubkosten, Gehkosten und Heuristiken

Bei einer „kürzesten Lösung“ muss klar sein, was minimiert wird. Schuboptimal bedeutet minimale Kistenschübe; zugoptimal berücksichtigt auch das Gehen. Die Ziele können sich widersprechen: Ein Umweg durch einen Raum kann einen Schub sparen und eine sichere Kistenzuordnung erhalten. Der Solver muss Kosten priorisieren und das Ergebnis entsprechend kennzeichnen.

Eine Heuristik schätzt den Abstand zur Lösung. Eine einfache Variante ordnet Kisten anhand von Gitterabständen Zielen zu und ergänzt Strafkosten für wandnahe Kisten. Wegen Wänden, Standfeldern und Kistenreihenfolge ist die echte Route schwieriger als die reine Entfernung. Die Schätzung hilft bei der Priorisierung, ohne damit eine exakte Entfernung zu beweisen.

Bei kleinen Feldern sollten Zugfolge, Schubzahl, Gehschritte und geprüfte Zustände angezeigt werden. So lässt sich das Ergebnis mit dem eigenen Plan vergleichen, ohne eine unbewiesene Optimalität anzunehmen.

Ein kleines Spielfeld Schritt für Schritt

Dieses Beispiel enthält eine Kiste: # bedeutet Wand, . Ziel, $ Kiste und @ Spieler.

#####
# . #
# $ #
# @ #
#####

Der anfänglich erreichbare Bereich umfasst das Spielerfeld und den Boden unter der Kiste. Ein Schub ist legal: Der Spieler steht unter der Kiste und schiebt sie nach oben auf das Ziel. Der Solver speichert die neue Kistenkoordinate, berechnet den Spielerbereich erneut und erkennt, dass alle Ziele belegt sind. Mit dem Elternverweis lässt sich die kurze Route aus nötigem Gehen und einem Schub rekonstruieren.

Bei schwierigeren Feldern enthält die Suchfront mehrere mögliche Schübe. Ein Eckenzweig wird beschnitten, ein beweglicher Zweig bleibt in der Warteschlange. Das unterscheidet zufälliges Probieren von einer Suche, die ihre Erkenntnisse behält.

Wann ein Solver anhält oder keine Lösung meldet

Ein Browser-Solver kann aus mehreren Gründen stoppen. Ungleiche Kisten- und Zielzahlen, unbekannte Zeichen oder ein fehlender Spieler machen das Feld ungültig. Ein gültiges Feld kann sichere Grenzen für Zeilen, Spalten, Kisten oder besuchte Zustände überschreiten. Auch kann eine begrenzte Suche ihre Suchfront ohne Lösung ausschöpfen.

Nur der letzte Fall bei einer vollständigen, unbegrenzten Suche rechtfertigt einen mathematischen Unlösbarkeitsnachweis. Kleine Online-Werkzeuge begrenzen die Arbeit gewöhnlich, damit die Seite reagiert. Eine Limitmeldung ist ein Anlass, das Feld zu verkleinern, Blockaden zu prüfen oder rückwärts zu planen. Der zugehörige Sokoban-Solver dokumentiert seine Grenzen für kleine Felder und meldet diese klar, statt endlos weiterzulaufen.

Leveldesigner können eine Route mit dem Solver prüfen und anschließend durch menschliche Spieltests feststellen, ob die beabsichtigte Idee verständlich ist. Der Leitfaden zum Sokoban-Leveldesign beschreibt diesen Ablauf; hier wird die zugrunde liegende Suche erklärt.

FAQ zum Sokoban-Solver-Algorithmus

Was ist ein Sokoban-Solver-Algorithmus?

Ein Suchverfahren, das Kisten- und Spielerzustände darstellt, legale Schübe erzeugt, bekannte verlorene Stellungen ausschließt und bei belegten Zielen eine Zugfolge rekonstruiert.

Untersucht der Solver jede Bewegung mit den Pfeiltasten?

Meist fasst er Gehwege zu einem erreichbaren Spielerbereich zusammen und erweitert Schübe als wesentliche Kanten. Dadurch entfallen viele gleichwertige Gehwege.

Warum beschleunigt das Beschneiden von Blockaden die Suche?

Es entfernt Zweige mit Ecken ohne Ziel, unbeweglichen Kistengruppen oder versperrten Gängen, bevor deren Nachfolgezustände untersucht werden.

Ist die zuerst gefundene Lösung die kürzeste?

Nur wenn Suchreihenfolge und Kostenmodell dies garantieren. Ein begrenzter Browser-Solver kann eine brauchbare Lösung liefern, ohne minimale Schub- oder Zugzahl zu beweisen.

Was bedeutet das Erreichen des Suchlimits?

Das Werkzeug hat sein Sicherheitsbudget erreicht, bevor eine Lösung oder deren Unmöglichkeit bewiesen wurde. Verkleinern Sie das Feld oder prüfen Sie die Stellung manuell. Die Meldung beweist keine Unlösbarkeit.

Quellen und weiterführende Literatur

Zustände und erreichbare Bereiche wurden mit der Solver-Referenz im Sokoban-Wiki abgeglichen. Die Beispiele zur Suchreihenfolge folgen dem Beitrag Grundlegende Suchalgorithmen für Sokoban. Zustandsraumwachstum und Entfernungsschätzungen behandelt Pavel Klaviks Dokumentation zum Sokoban-Solver. Die Quellen behandeln gewöhnliches Sokoban; werkzeugspezifische Grenzen stammen vom verlinkten Zeek-Solver.

Ein kleines Spielfeld lösen und das Ergebnis prüfen

Fügen Sie ein ASCII-Feld in den Browser-Solver ein und vergleichen Sie danach die Zugfolge mit den hier erklärten Zuständen, Schüben und Beschneidungen.

Sokoban-Solver öffnen