Ich bin vor kurzem auf ein sogenanntes Legespiel gestoßen. Bei diesem Spiel müssen quadratische Karten so zu einem größeren Quadrat gelegt werden, dass die Bilder aller Karten an den Rändern zusammenpassen. Ich werde hier zeigen, wie komplex derartige Spiele sind, und einen Algorithmus zur Lösung vorstellen.

Ich bin zufällig in einem Kinderbuchladen auf das Legespiel “Pippi Langstrumpf Absolut knifflig!” gestoßen. Mein 4-jähriger Sohn mochte es, weil Bilder von Pippi Langstrumpf darauf waren und es sah nach einer guten stillen Beschäftigung aus. Ziel des Spiels ist es, alle neun Karten so in einem Quadrat anzuordnen, dass alle Figuren (Pippi, Herr Nilson und der Kleine Onkel) zusammenpassen.

Nachdem ich meinen Sohn einige Zeit beobachtet hatte, fand ich heraus, dass das Spiel tatsächlich knifflig ist. Spätestens bei der achten oder bei der letzten Karte war Schluß – die Karten passten nie alle zusammen. Mein Sohn glaubte an Sabotage und wurde etwas sauer, aber machte trotzdem – schimpfend – weiter.

Die Analyse

Hinten auf der Verpackung stand: „Es gibt mehrere Lösungen.“. Jetzt war mein Ehrgeiz geweckt! Wie viele Lösungen gab es denn genau? Wie könnte man mit Software alle Lösungen herausfinden? Was wäre ein guter Algorithmus? Einfach alle Möglichkeiten, d.h. alle 9 Karten in allen Positionen und in allen 4 Drehlagen, durchprobieren? Das wären …

(9 · 4) · (8 · 4) · (7 · 4) · (6 · 4) · (5 · 4) · (4 · 4) · (3 · 4) · (2 · 4) · (1 · 4) = 9! · 4⁹ = 95.126.814.720

und damit etwas weniger als 100 Milliarden Möglichkeiten. Das ist in etwa die Anzahl der Nervenzellen im menschlichen Gehirn. Mit genügend Zeit auf einem modernen PC wäre das durchaus noch beherrschbar. Aber es geht deutlich effizienter mit dem Prinzip des Ariadnefadens oder auch Backtracking.

„Der Ariadnefaden war der griechischen Mythologie zufolge ein Geschenk der Prinzessin Ariadne, Tochter des Königs Minos, an Theseus. Mit Hilfe des Fadens fand Theseus den Weg durch das Labyrinth, in dem sich der Minotauros befand.“ – Wikipedia

Theseus fand den Weg durch das Labyrinth, weil er anscheinend einen sehr langen Faden hatte, den er beim Gehen ständig abrollte. Weil er das tat konnte er nach jeder Sackgasse, auf die er traf wieder den Weg zurück finden (daher „Backtracking“). Er sah natürlich auch immer genau, wo er noch nicht gewesen war. Nämlich dort wo noch kein Faden lag.

Theseus konnte mit seinem Faden das Labyrinth systematisch durchsuchen. Auch das Spiel “Absolut knifflig!” stellt ein Labyrinth dar. Nur ist der Suchraum, um den es hier geht deutlich abstrakter. Wir starten mit dem leeren Spielfeld. Jetzt muss man sich entscheiden, mit welcher Karte man anfangen möchte und wie sie gedreht werden soll. Das sind also in diesem ersten Schritt 36 (=9·4) Entscheidungen. Das wäre äquivalent zu 36 Wegen an der ersten Abzweigung eines Labyrinths.

Egal welchen dieser Wege wir einschlagen, bei der zweiten Karte, die wir rechts neben die erste Karte legen (wir arbeiten immer von links nach rechts und von oben nach unten), gibt es wieder mehrere Möglichkeiten. Aber es sind deutlich weniger. Wir haben jetzt natürlich nur noch 8 Karten übrig, was 32 (8 · 4) Möglichkeiten ergeben würde (siehe Berechnung oben), aber es gibt noch weniger Möglichkeiten, da die erste und die zweite Karte aneinanderpassen müssen. Dank dieser Tatsache wird man mit einer systematischen Suche und Backtracking deutlich weniger Möglichkeiten ausprobieren müssen, um alle Lösungen zu finden, als die oben angegebenen knapp 100 Milliarden.

Der Algorithmus

Zunächst brauchen wir einen Algorithmus für folgendes Teilproblem: Nach dem n-ten Schritt (n ist in diesem Fall zwischen 0 und 8) alle Möglichkeiten für den (n+1)-ten Schritt  berechnen.

Der Algorithmus soll also, ausgehend von einem leeren oder teilweise befüllten Spielfeld (im Folgenden „field“ genannt) und den noch verbliebenen Karten (im Folgenden „remainingCards“ genannt), alle Möglichkeiten finden, genau eine zusätzliche Karte zu legen, sodass das Ergebnis immer noch zusammenpasst:

Um nun alle Lösungen unseres Legespiels zu berechnen, starten wir mit einem leeren Spielfeld. Dann suchen wir alle Möglichkeiten eine erste Karte zu legen (wie oben schon erwähnt sind das 36), danach alle Möglichkeiten für die nächste Karte, dann für die übernächste und so weiter. Wir verwenden solange rekusriv die unten angegebene Methode findAllSolutions (siehe Zeile 11 unten) bis wir alle Möglichkeiten aufgesammelt haben, bei denen wir das Spielfeld mit allen 9 Karten ausfüllen konnten (siehe Zeile 7 und 8 unten). Das sind dann unsere Lösungen (solutions).

Aber wo ist jetzt hier der Faden? Der Ariadnefaden versteckt sich in den rekursiven Aufrufen (also quasi im Callstack). Jedesmal, wenn wir einen rekursiven Methoden-Aufruf machen, rollen wir etwas Faden ab, und bei jeder Rückgabe von Lösungen („return solutions“) – egal ob die Liste leer ist oder nicht – gehen wir an dem Faden wieder ein Stück zurück.

Die Lösungen

Der hier entworfene Algorithmus findet, in Java implementiert und gestartet auf einem handelsüblichen PC, in wenigen Millisekunden alle 148 Lösungen durch systematisches Ausprobieren von 220.760 Möglichkeiten anstatt der oben angegebenen 95.126.814.720.

Die 148 Lösungen bei diesem Spiel haben noch eine Besonderheit. Eigentlich ist nur ein Viertel der Lösungen (37) von wirklichem Interesse, da die restlichen Lösungen durch Rotation des gesamten Spielfelds um 90°, 180° und 270° entstehen. Man könnte auch sagen: Die 148 Lösungen zerfallen in 37 Äquivalenzklassen mit jeweils 4 Mitgliedern. Aber genug gefachsimpelt! Im Folgenden sind auf jeden Fall alle 37 echt unterschiedlichen Lösungen zu sehen:

Manche andere Legespiele enthalten doppelte Karten, was die Anzahl der echt unterschiedlichen Lösungen nochmals reduziert. Zu diesem Thema gibt es einen separaten Artikel Knifflidiffels lösen.

Spielen mit beliebigem Schwierigkeitsgrad

Da wir nun alle Lösungen zu dem Legespiel „Absolut knifflig!“ kennen, ist es jetzt auch möglich, das Spiel mit beliebigem Schwierigkeitsgrad zu spielen. Dazu legt man eine Teillösung (z.B. mit 6 Karten) und lässt den Spieler die restlichen Karten (3 in unserem Beispiel) richtig anordnen. Wenn das zu leicht wird, gibt man nur noch 5 Karten vor usw.

Noch ein Tipp: Dieser Blog-Post kann auch auf einem Smartphone gut angezeigt und als Spickzettel verwendet werden.

Die Software

Das Java-Programm „Legespiel-Solver“ ist freie Software und unter der freizügigen MIT-Lizenz veröffentlicht. Das komplette Eclipse-Projekt kann bei Github heruntergeladen werden. Für die Anzeige aller Lösungen im generierten HTML werden die neun Bilder der Karten benötigt (siehe zweite Abbildung in diesem Post) . Diese sind nicht Teil des Software-Pakets, da es sich hierbei um geistiges Eigentum des Oetinger-Verlags handelt.

Andere ähnliche Legespiele

Es gibt andere Legespiele auf dem Markt, die den Spieler vor ein sehr ähnliches Problem stellen. Siehe hierzu die Liste von Legespielen und ihre Lösungen.

Interessieren Euch die Lösungen für ein bestimmtes Legespiel? Mit dem Legespiel-Solver Online könnt Ihr eine einfache Benutzeroberfläche verwenden, um die Daten zu dem Legespiel einzugeben und dann alle Lösungen anzuzeigen.

Wenn Ihr Fragen zur Software habt oder ein weiteres Spiel damit gelöst habt, dann hinterlasst mir bitte einen Kommentar. Oder noch besser: Reicht das Spiel mit Hilfe des Legespiel-Solver Online ein.