Lösungsalgorithmus für die Instant-Insanity-Familie

Aus der Instant-Insanity-Familie wurden bereits Colorados und Crazy Four / Das Ampelspiel vorgestellt. Mehrere (meist vier) bunte Würfel mit verschieden gefärbten Seitenflächen (die Anzahl der Farben ist gleich der Anzahl der Würfel) jeweils so gestapelt werden, dass auf jeder Außenseite des Stapels alle möglichen Farben (hier also alle vier) zu sehen sind.

Ein Lösungsalgorithmus besteht darin, alle Möglichkeiten durchzuprobieren bis eine Lösung gefunden ist. Allerdings kann das nur der Computer, als Mensch verliert man zwischendurch den Überblick und muss von vorn anfangen.

Aber es gibt eine völlig andere Herangehensweise, bei dem aus den vier Würfeln zunächst ein überschaubarer Graph erzeugt wird. Und aus diesem kann man alle Lösungen relativ einfach ablesen. Dieser Algorithmus stammt von Thomas H. O'Beirne [1]. Die wichtigste Beobachtung besteht darin, dass die eigentliche Aufgabe in zwei Teile zerfällt, die man völlig unabhängig voneinander lösen kann. Und zwar: Wenn Sie an der Vorderseite bauen, dann entsteht gleichzeitig die Rückseite. Und wenn sie einen Würfel nun so drehen, dass seine Vorderseite dieselbe bleibt, dann bleibt auch die Rückseite. Die Lösung von Vorder- und Rückseite ist die eine Teilaufgabe. Und die andere Teilaufgabe betrifft analog die Seiten Rechts und Links, ohne die Vorder- und Rückseite zu verändern. Dass diese beiden Teilaufgaben unabhängig sind, sehen Sie folgendermaßen: Wir drehen wieder einen Würfel so um eine Achse, dass seine Vorderseite erhalten bleibt. Wir können den Würfel viermal um jeweils 90 Grad drehen und erhalten so vier verschiedene Kombinationen für die rechte und linke Seite.

Jetzt müssen wir nur noch dafür sorgen, dass bei der Kombination aus Vorder- und Rückseite aus dem ersten Schritt durch die beschriebenen Drehungen auch die rechte und linke Seite passend gemacht werden können. Und dazu benötigen wir den folgenden Graphen.

Das Vorgehen soll hier am Beispiel von Crazy Four / Das Ampelspiel mit den Farben Rot (R), Grün (G), Blau (B) und Gelb (Y) erklärt werden. Dazu müssen wir zunächst den Graphen links im Bild erstellen. In der Bezeichnungsweise wie bei Colorados sind die vier Würfel von Crazy Four / Das Ampelspiel folgendermaßen gefärbt, die sechs Würfelseiten stehen in der Reihenfolge Oben, Unten, Vorn, Hinten, Links und Rechts:

Würfel 1:               "RBGGBY", 
Würfel 2:               "YRRGYB", 
Würfel 3:               "BRYGYY", 
Würfel 4:               "YGGRRB"  

Der Graph besteht aus vier Knoten, die den vier Farben (R, G, B und Y) auf den Würfelseiten entsprechen. Die Kanten werden folgendermaßen eingezeichnet: Wir nehmen einen der Würfel und zeichnen jeweils eine Kante zwischen zwei Farben, die sich auf den Seiten dieses Würfels gegenüber liegen. Für den Würfel 1 ergeben sich so die Kanten R-B, G-G und B-Y (unten eingezeichnet in roter Farbe). Analog verfahren wir für die anderen Würfel, aber wir verwenden für die unterschiedlichen Würfel wieder verschiedene Farben. So entsteht der links abgebildete Graph. Die Schlaufe an dem grünen Knoten bedeutet also beispielsweise, dass bei Würfel 1 zwei grüne Seiten gegenüberliegen.

Damit haben wir die Aufgabenstellung in einen Graphen übertragen, und jetzt müssen wir in dem Graphen nach der Lösung suchen. Und das geht ganz einfach: Wir müssen zwei Teilgraphen finden, die die Lösungen für die Seiten vorn und hinten bzw. rechts und links zeigen. Diese zwei Teilgraphen müssen die folgenden beiden Bedingungen erfüllen:

• Jeder Teilgraph besteht aus allen vier Knoten und vier Kanten in den vier verschiedenen Farben, und
• die Graphen dürfen keine Kante gemeinsam besitzen.

Die zwei Teilgraphen in der Mitte (Würfel von vorn und hinten) und ganz rechts (Würfel von links und rechts) erfüllen diese Bedingungen und sind relativ einfach zu finden. Falls es mehrere solche Graphen gibt, dann entsprechen diese verschiedenen Lösungen. 

Aus diesen zwei Teilgraphen lässt sich schnell der Würfelturm bauen. In unserem Beispiel bedeutet das für den Würfel Nummer 1: Vorn und hinten liegen Rot und Blau (rote Kante im mittleren Graphen), links und rechts liegen Blau und Gelb. Die zwei grünen Seiten liegen also oben und unten und sind an den Seiten nicht sichtbar.

Hier die Lösung, Würfel 1 liegt ganz unten.

Mehr Infos:

[1] T. H. O'Beirne: Puzzles and Paradoxes, Oxford University Press, London, 1965.