Kategorie: Quadratische 3x3-Legespiele
Die am häufigsten vorkommenden Edge-Matching-Puzzles bestehen aus neun quadratischen Karten, die zu einem 3x3-Quadrat zusammengesetzt werden müssen, so dass die Bilder an zusammenstoßenden Kanten zusammenpassen. In den meisten Fällen gibt es vier verschiedene Bilder, so dass es insgesamt acht verschiedene Halbbilder (jeweils Oberteil bzw. Unterteil genannt) gibt. Wenn wir soviel Gemeinsamkeiten haben, kann man dann die Lösung solcher Geduldspiele nicht automatisieren und den Computer für uns arbeiten lassen? Die Antwort ist: Ja es geht, aber es ist nicht ganz einfach, weil es so viele Möglichkeiten gibt.
Legespiele automatisch online lösen
Hier ist der Legespiel-Online-Solver von Andreas Keilhauer: Sie können aus einer immer länger werdenden Liste mit vorbereiteten Anlegepuzzles auswählen oder auch die Karten für ein weiteres Spiel eingeben und sich blitzschnell die Lösungen berechnen lassen. Dank Backtracking(s.u.) dauert dies nur Sekundenbruchteile.
Orientierte und nicht-orientierte Anlegepuzzles
Manche dieser Geduldspiele haben die zusätzliche Eigenschaft der Orientiertheit: Alle Karten haben nebeneinander jeweils zwei Oberteile sowie zwei Unterteile nebeneinander. Das muss aber nicht der Fall sein, wie man bei dem rechten Spiel sieht: dort gibt es Karten mit ein bis drei Köpfen von Marienkäfern, zwei Köpfe auf einer Karte können sich nebeneinander oder gegenüber befinden.
Wie viele solche Spiele gibt es?
Dazu überlegen wir uns, wie viele verschiedene 3x3-Quadrate mit Lösungen eines 3x3-Anlegepuzzles wir erzeugen können.
Betrachten wir zunächst den orientierten Fall mit orientierten Lösungen, d.h. auch bei der Lösung des Geduldspiels haben alle Bilder die gleiche Orientierung, beispielsweise die Oberteile links bzw. oben. Es gibt 12 Kanten, an denen jeweils Karten zusammenstoßen, für jede solche Schnittkante können wir eines der vier Bilder auswählen (die Orientierung ist ja vorgegeben). Das sind 4¹² Möglichkeiten. Dann bleiben noch die 12 Kantenstücken am Rand des 3x3-Quadrats, hier haben wir wieder jeweils vier Möglichkeiten, die Orientierung ist ja wieder vorgegeben. Das sind weitere 4¹² Möglichkeiten. Wir können das 3x3-Quadrat nicht rotieren, ohne die Orientiertheit (Oberteile links/oben) zu zerstören. Das ergibt 4²⁴ = 2⁴⁸ = 281.474.976.710.656, also reichlich 281 Billionen Möglichkeiten.
Jetzt kommt der nicht-orientierte Fall: Wir können an allen Kanten die Orientierung tauschen, d.h. jeweils Ober- und Unterteile vertauschen. An den Randstücken können wir das beliebig tun, an den Stußkanten müssen wir beide Halbbilder austauschen. Das sind wieder insgesamt 24 Stellen, an denen wir je zwei Möglichkeiten haben. Wegen der jetzt möglichen Rotation müssen wir die Gesamtzahl noch durch vier Teilen. Damit vergrößert sic die Anzahl der Spiel um einen Faktor von 2²² = 4.194.304 auf 2⁷⁰ = 1.180.591.620.717.411.303.424, das ist reichlich eine Trilliarde.
So viele verschiedene Lösungen gibt es, wenn man die passenden neun Karten dazu hat. Wir könnten uns jede solche Lösung ausdrucken, in neun Karten zerschneiden und hätten dann reichlich eine Trilliarde Geduldspiele mit verschiedenen Lösungen. (Praktisch ist das natürlich illusorisch: Es gibt nicht genügend Papier auf der Welt und jeder Bewohner der Erde würde mehr als 100 Milliarden solche Geduldspiele erhalten, wenn wir unsere Geduldspiele zu Weihnachten an alle verschenken.)
Aber nicht alle diese Geduldspiele sind verschieden, da sich für manche Spiele aus den neun Karten mehrere Lösungen legen lassen. Die Zahlen werden dadurch kleiner, aber nicht sehr viel.
Mit wie vielen Lösungsversuchen muss man rechnen?
Wenn wir nun ein uns vorliegendes 3x3-Anlegepuzzle systematisch lösen wollen, müssen wir irgendwie alle Möglichkeiten durchprobieren. Wir wollen uns aber nicht die oben berechnete gigantische Zahl von Lösungen anzuschauen, sondern wir probieren nur unsere neun vorgegebenen Karten durch. Wir versuchen also, eine Reihenfolge der neun Karten zu finden, so dass sich eine Lösung ergibt, wenn wir die Karten in dieser Reihenfolge von oben links beginnend in das 3x3-Quadrat legen.
Im orientierten Fall (Orientierte Karten, wir suchen nach einer orientierten Lösung) können wir die Karten in der richtigen Orientierung (Oberteile links/oben) vor uns hinlegen, es kommt nur noch auf die Reihenfolge an. Dafür gibt es 9! = 362.880 Möglichkeiten. Das sind zwar mehr Möglichkeiten, als man als Mensch durchprobieren möchte, aber es gibt ja Computer. Und für die ist eine solche Zahl überschaubar groß. Im nicht-orientierten Fall kommt für jede Karte wegen möglicher Drehungen noch ein Faktor 4 hinzu, das gesamte 3x3-Quadrat kann aber auch gedreht werden. Bleibt ein Faktor von 4⁸ = 65536 und insgesamt eine Anzahl von 9! * 4⁸ = 23.781.703.680. Das sind reichlich 23 Milliarden Versuche. Wenn man nur nach einer Lösung sucht, muss man diese nicht alle durchprobieren, weil man eine Lösung nicht erst beim letzten Versuch finden wird. Aber wenn man die Gesamtzahl aller möglichen Lösungen exakt wissen will, muss man auch alle Möglichkeiten durchprobieren. Diese Zahl ist an der Grenze des Machbaren: Wenn der Computer 1 Million Versuche pro Sekunde schafft, wäre er nach etwa 6:36 Stunden fertig.
Jetzt ist also der Informatiker gefordert, um einen Algorithmus zu entwickeln, der wesentlich schneller ist, als alle Fälle durchzuprobieren. Das Geheimnis besteht darin, die vielen durchzuprobierenden Einzelfälle so zu gruppieren, dass man schnell sogenannte Sackgassen erkennt und große Mengen von Einzelfällen in jeweils einem Schritt als nicht zielführend verwerfen kann. Der Algorithmus heißt Backtracking und soll später noch ausführlich erläutert werden, da er für viele Geduldspiele extrem nützlich ist.
