Wie wir 2.000 Schiebepuzzle-Felder vorab prüften

Ein Solver ist nur vertrauenswürdig, wenn seine Vorstellung eines Zugs dem Spiel entspricht. In einem Schiebepuzzle gleitet ein Teil etwa bis zu einer Wand, einem anderen Teil oder einem Tor, das seine Farbe nicht durchlässt. OutBrick ergänzt zustandsabhängige Details: Schlüssel ändern Tore, Eis kann mehrere Schübe zum Verschwinden brauchen und Generatoren wartende Teile einführen. Eine vereinfachte Neuumsetzung dieser Regeln für die Prüfung ließe genau dort eine Lücke, wo sich ein Fehler verstecken könnte.

Die Suche fragt deshalb die eigenen Spielregeln nach legalen Zügen und wendet sie durch denselben Zustandsübergangscode an wie das Spielen. Der Zustandsschlüssel enthält auch den Torzustand und eine zusammengefasste Zugzahl, wenn zyklische oder zeitgesteuerte Tore sie relevant machen. Zwei äußerlich gleiche Felder mit verschiedenen aktiven Torzuständen müssen unterschiedliche Suchzustände bleiben.

Der Solver nutzt gewichtetes A*. Seine ExitTable-Heuristik fragt, wie viele Schübe jedes Teil zu einem passenden Ausgang bräuchte, wenn die anderen Steine entfernt wären. Dieses vereinfachte Feld ist leichter zu analysieren als das echte und gibt eine hilfreiche Schätzung der restlichen Arbeit. Die stärkere Gewichtung der Heuristik begünstigt das schnelle Finden einer Lösung.

Diese Wahl hat eine Grenze: Der gefundene Weg ist nützlich, aber nicht garantiert der kürzeste. Eine Suche kann auch am Knotenbudget stoppen. Dann lautet die Antwort unbekannt; der Solver nennt das Feld nicht unmöglich. Nur ein vollständig erschöpfter erreichbarer Zustandsraum kann ein Urteil ‚nicht lösbar‘ tragen. Die Unterscheidung verhindert, dass Zeitlimit oder Abbruch zur falschen Aussage über das Puzzle werden.

Das Finden eines Wegs ist nicht die letzte Prüfung. Für jedes gestaltete Feld speichern wir einen Lösungsnachweis: die Zugfolge vom Anfang bis zum gelösten Zustand. Das Nachspielen startet mit einem frischen Spielzustand, prüft dessen Gültigkeit und wendet die Züge einzeln durch die echten Regeln an. Ein illegaler Zug lässt die Prüfung sofort scheitern.

Die Prüfung spielt außerdem jeden Zug aus demselben Vorherzustand erneut ab und vergleicht resultierenden Zustand, Ereignisse und Ergebnis. So werden Übergänge erkannt, die bei Wiederholung anders reagieren. Nach jedem Zug wird geprüft, dass jedes Teil auf gültigen Feldzellen bleibt und keine zwei Teile dieselbe Zelle belegen. Am Ende muss das Feld tatsächlich gelöst sein. Ein nur plausibel wirkender Weg oder einer mit einem verbliebenen Stein zählt nicht.

Ein legaler Nachweis beweist einen vorhandenen Weg. Er beweist nicht, dass ein Mensch ihn findet, dass er fair wirkt oder dass das Feld auf die richtige Weise schwierig ist. Auch belegt der Solverweg keine optimale Zugzahl. Das sind eigene Designfragen; deshalb behandeln wir das Nachspielen des ganzen Pakets als Korrektheitsprüfung und beurteilen Tempo und Schwierigkeit getrennt.

Das Zuglimit muss außerdem Raum für den geprüften Weg lassen. Spieler dürfen beliebig lange denken: Das Limit zählt Züge, und OutBrick hat keine Uhr. So erhält das Puzzle Druck, ohne das Prüfungsergebnis zum Timer zu machen.

Das nützliche Veröffentlichungsergebnis lautet nicht ‚Der Solver lief einmal‘. Es lautet, dass jedes Feld im Paket einen Lösungsnachweis hatte, der sauber nach den veröffentlichten Regeln nachgespielt wurde. Ändert sich eine Regel oder ein Feld, lässt sich das Paket erneut prüfen; der erste fehlerhafte Zug zeigt, welcher Vertragsteil brach: Legalität, Determinismus, Feldgeometrie oder der endgültige gelöste Zustand.

So prüften wir OutBricks 2.000 Felder vor Veröffentlichung. Du kannst diese Art Schiebepuzzle auf dem kostenlosen Browser-Feld ausprobieren oder OutBrick für iPhone und iPad herunterladen.