Schiebespiele als Graphen

Wenn man Schiebespiele analysieren möchte, bieten sich Graphen an. Dazu betrachtet man alle Möglichkeiten, die Steine in den dazugehörigen Rahmen zu packen. Diese sollen als Stellungen bezeichnet werden. Jede solche solche Stellung bildet einen Knoten des Graphen. Jeweils zwei Knoten werden durch eine Kante verbunden, wenn sich eine Stellung durch einen einzelnen Zug in die andere Stellung überführen lässt. Diese Kanten sind nicht gerichtet, da jeder Zug auch in der umgekehrten Richtung ausgeführt werden kann.

Das Bild zeiht einen Ausschnitt aus dem Graphen für das einfache Schiebespiel von F.C. Hughes. Links im Graphen findet sich die Startposition. Zwei Positionen sind so verbunden, dass man jeweils den zu bewegenden Stein erkennt. Man sieht sehr schön, dass man sich oben in der Mitte in seiner Sackgasse befindet und nur Züge rückgängig machen kann.

Frage: Welche Position befindet sich unten in dem Rechteck mit dem Fragezeichen? 

Was kann der Graph eines Schiebespiels uns über das entsprechende Schiebespiel aussagen? Er kann uns bei der Such nach einer Lösung helfen, allerdings meist nur mit Hilfe eines Computers. Da es für die meisten Schiebespiele recht viele Stellungen gibt (einige Tausend bis viele Millionen), können wir den Graphen nicht einfach auf ein Stück Papier zeichnen und einfach so analysieren. Der Computer kann uns auch für größere Graphen noch helfen, stößt aber irgendwann wegen der schieren Größe der Graphen auch an Grenzen.

Hier eine Zusammenstellung von Aufgaben für die Suche im Graphen. Zunächst zwei Fragen, die für die Lösung konkret gegebener Schiebespiele von Bedeutung sind:

Aufgabe 1: Finde den (oder genauer gesagt: einen) kürzesten Weg von einer ersten vorgegebenen Stellung (als Start) zu einer zweiten Stellung als Ziel. Diese Aufgabe wird beispielsweise bei dem Schiebespiel von L. W. Hardy (1909) gestellt, ebenso beim Moving Day Puzzle (hier ist die Lage der übrigen drei kleinen Quadrate zwar nicht explizit vorgegeben, aber es besteht kaum eine Auswahl. Abstrakt betrachtet muss man in dem Graphen einen kürzesten Weg (oder wenigstens überhaupt ein Weg) zwischen den zwei Knoten zu Start und Ziel finden.

Aufgabe 2: Finde den kürzesten Weg von einem Startknoten zu einer Menge von möglichen Zielknoten. Solch eine Menge von Zielknoten wird beim Eselspuzzle und vielen anderen verwendet: Zu der Menge gehören hier alle Knoten, bei denen sich der quadratische Stein der Größe 2x2 an einer bestimmten Position, nämlich unten in der Mitte, befindet.

Für beide Aufgaben ist es nicht unbedingt notwendig, den ganzen Graphen zu kennen. Man kann den Graphen während der Suche nach dem kürzesten Weg sukzessive aufbauen und so bei kurzen Wegen auch relativ schnell eine Lösung finden. Die benötigte Zeit wächst allerdings mit der Länge des Weges stark an. 

Für die folgenden Aufgabenstellungen benötigt man den ganzen Graphen: Sie dienen dazu, ein Schiebespiel besser zu verstehen und neue, schwierige Aufgaben für dieses Schiebespiel zu stellen.

Aufgabe 3: Wie viele Stellungen sind mit den gegebenen Steinen im vorgegebenen Rahmen überhaupt möglich? D.h. aus wie vielen Knoten besteht der gesamte Graph?  

Aufgabe 4: Es ist in der Regel nicht möglich von einer beliebigen Stellung zu jeder anderen möglichen Stellung zu gelangen. Einige Stellungen sind einfach nicht über Züge aus einer oder mehreren Kanten verbunden. Mathematisch gesprochen besteht der Graph aus mehreren Zusammenhangskomponenten. Große Zusammenhangskomponenten ermöglichen eine Vielzahl von Zügen und machen ein Schiebespiel interessant. Aus wie vielen Knoten bestehen die größten Zusammenhangskomponenten? Bei anspruchsvollen Geduldspielen ist die Situation meist folgendermaßen: Neben vielen kleinen Zusammenhangskomponenten (das sind Stellungen, von denen aus nur ganz wenige Züge möglich sind) gibt es meist eine einzige große Zusammenhangskomponente oder auch zwei oder vier Zusammenhangskomponenten exakt gleicher Größe. Im ersten Fall sind in der Regel waagerecht und senkrecht gespiegelte Stellungen in dieser Zusammenhangskomponente verbunden, bei zwei großen Komponenten nur ist nur eine Spiegelung (oder Drehung um 180 Grad) möglich, bei vier Komponenten gar keine.

Aufgabe 5: Wie groß ist der Durchmesser der größten Zusammenhangskomponente? Für den Durchmesser betrachtet man die jeweils kürzesten Wege zwischen zwei Knoten und sucht dann ein Paar von Knoten, für das dieser Abstand maximal ist. Dieses Paar entsprechen im betrachteten Schiebespiel zwei Stellungen, die als Start und eine Ziel den maximal möglichen Abstand haben und deshalb eine maximale Anzahl von Zügen benötigen. Damit finden wir komplizierte Aufgabenstellungen.

Der Zusammenhang zwischen der Größe eines zusammenhängenden Graphen und seinem Durchmesser ist nicht so einfach, wie man vermuten könnte. Zwar haben größere Graphen tendenziell einen größeren Durchmesser, aber es gibt auch relativ kleine Schiebespiele mit verblüffend großem Durchmesser.

Wegen der symmetrischen Form sowohl des Rahmens wie auch der konvexen Steine unterscheiden sich maximal entfernte Positionen eines Schiebespiels oft nur durch eine Drehung oder Spiegelung. Hier einige solche Aufgaben zum Nachspielen, beispielsweise mit dem Baukasten für mehr als 50 Schiebespiele.

Eine Variante  einfachen Schiebespiels von Hughes mit einer Spiegelung:

Viel komplizierter ist die Variante von Blockado mit einer Drehung um 180 Grad.

Bei der folgenden Variante des Happy Couple liegt die Symmetrie in der Vertauschung der beiden 2x2-Quadrate: