Wissenschaftssommer 2008

Lunar Lockout - Verschiebe-Puzzles

Die Aufgaben:

Grundaufgabe:
Spielsteine können einzeln in die vier Himmelsrichtungen bewegt werden. Die Bewegung endet aber erst direkt vor einem in Bewegungsrichtung angrenzenden Stein. Für eine Anordnung der Spielsteine ist eine Zugfolge anzugeben, nach der einer der Steine auf einer vorher bezeichneten Position steht.
Umkehrung:
für eine vorgegebene Zugfolge ist eine Aufstellung der Figuren anzugeben, von der aus die Folge tatsächlich regelgemäß ausführbar ist. (Gibt es Zugfolgen mit nur einer passenden Startaufstellung?)
Stellungs-Analyse:
für eine gegebene Grundaufgabe ist zu beweisen, daß sie unlösbar ist. (Wie kann man die Menge der erreichbaren Felder schnell und gut approximieren?)

Mathematischer Hintergrund

Ein Zug überführt eine Konfiguration in die nächste. Eine Konfiguration kann man effizient speichern, indem man nur die Menge der Koordinaten der belegten Positionen angibt. Deswegen gehört die Aufgabe zur Komplexitätsklasse PSPACE (polynomieller Platz).
Tatsächlich gehört die Aufgabe zu NPSPACE (N bedeutet Nichtdeterminismus), da man ja die Lösungsfolge nicht kennt, sondern erstmal suchen muß. Nach dem Satz von Savitch kann man aber nichtdeterministische PSPACE-Berechnungen durch deterministische PSPACE-Berechnungen simulieren.
Das erscheint verwunderlich, vor allem, da das entsprechende Problem für Zeitschranken (ist PTIME verschieden von NPTIME) bis heute ungeklärt ist.
Der Beweis ist jedoch nicht sehr schwer. Der Satz funktioniert, weil PSPACE schon Probleme mit sehr hoher Komplexität enthält. Das sieht man auch an Verschiebepuzzles: obwohl man jede Konfiguration knapp aufschreiben kann, gibt es doch sehr viele, genauer: exponentiell viele (man kann jeder Figur eine Position zuordnen).
In einer kürzesten Lösung einer Verschiebe-Aufgabe gibt es keine Wiederholungen, d. h. eine solche Lösung ist höchstens so lang, wie es verschiedene Konfigurationen gibt. Das sind aber sehr viele!
Tatsächlich ist für einige Verschiebepuzzles, zum Beispiel Atomix, bekannt, daß sie PSPACE-vollständig sind. Die entsprechende Frage für unsere Version von Lunar Lockout ist offen.
Ein Indiz für die PSPACE-Vollständikeit wäre, wenn man Folgen von Aufgaben angeben kann, deren Größe linear wächst, aber deren kürzeste Lösungslänge exponentiell.
Genauer: wir interessieren uns für folgende Funktion: f(s,n) ist das Maximum der Längen von kürzesten Lösungen von Aufgaben mit s Steinen auf einem Quadrat der Seitenlänge n. Unsere Beispiel zeigen zunächst nur lineares Wachstum von f, das liegt aber daran, daß wir s festhalten, also nur konstant viele (genauer: konstant wenige) Steine verwenden.

Anwendungen

Es handelt sich hier um eine Frage der Bewegungsplanung. Solche Fragen treten auch auf, wenn man die Arme eines Industrieroboters durch Lücken einer Autokarosserie führen muß und dabei wenig Spielraum hat.
Diese Probleme sind ebenfalls PSPACE-vollständig:

  • Die Erfüllbarkeit von aussagenlogischen Formeln mit Quantoren. Das benötigt man beim Entwurf logischer Schaltungen, bevor für diese der aufwendige industrielle Herstellungsprozeß beginnt.
  • Die äquivalenz regulärer Ausdrücke. Solche Ausdrücke beschreiben (gewünschte oder verbotene) Muster in Zeichenfolgen und werden benutzt bei der Beschreibung von Texten in Programmiersprachen oder natürlichen Sprachen.

Komplexitätsklasse: PSPACE
Selber Ausprobieren:Hier klicken!
Weitere Infos:Think Fun: http://www.thinkfun.com
produziert das Verschiebespiel Lunar Lockout.
Quellen / Fußnoten:[1]Markus Holzer und Stefan Schwoon:
Assembling Molecules in ATOMIX is hard, Theoretical Computer Science 303(3) 2007, p. 447-462

© HTWK