Geduldspiele mit ausgetauschten Figuren
Es gibt viele mit unterschiedlichen Motiven bedruckt 3x3-Anlegepuzzles, aber sind die auch wirklich verschieden? Das Foto zeigt, dass die nicht so ist: Die beiden Geduldspiele haben eine völlig gleiche Struktur, Köpfe sind oben oder links. Und wo im linken Bild bei Das verflixte Tom & Jerry Spiel eine orange Figur steht, finden wir bei Duckula der Verflixte eine dunkelblaue Figur. Ebenso entsprechen sich andere Paare von Figuren. Wir können also die Geduldspiele ineinander überführen, indem wir einfach die Bilder passend austauschen. Das ist einfach zu machen und auch vergleichsweise einfach wieder herauszufinden.
Geduldspiele mit ausgetauschten Figuren und Rotation
Aber es geht auch komplizierter: Wir hätten bei der Ersetzung auch teilweise die Orientierung ändern können und Oberteile eines Bildes durch Unterteile des anderen Bildes ersetzen können und umgekehrt (natürlich nicht nur an einer Stelle, sondern an allen Vorkommen des Bildes). Das würde immer noch dieselben Lösungen liefern, aber die Äquivalenz wäre den Karten aber nicht mehr so einfach anzusehen.
Einfache Invarianten für Anlegepuzzles
Als Invarianten wollen wir hier Eigenschaften der Anlegepuzzles betrachten, die sich bei den oben genannten Austauschmöglichkeiten nicht ändern. Sind beispielsweise zwei Karten eines Anlegepuzzles identisch, so bleibt diese Eigenschaft auch beim Austausch von Figuren (mit oder ohne Änderung der Orientierung) erhalten.
Invariante 1: Das Vorhandensein von Paaren (oder auch Dreiergruppen) identischer Karten.
Enthält eine Karte Halbbilder von allen vier Bildern, dann bleibt auch diese Eigenschaft beim Austausch von Figuren (mit oder ohne Änderung der Orientierung) erhalten. Deshalb:
Invariante 2: Die Anzahl der Karten mit Halbbildern von allen vier Bildern, dazu noch die Anzahl der Karten mit Halbbildern von nur drei Bildern, usw.
Invariante 3: Die Anzahl der Lösungen. Doch die muss man erst einmal kennen. Um sicher zu gehen, kann man den Legespiel-Solver von A. Keilhauer benutzen.
Diese Invarianten haben die Eigenschaft, dass zwei Anlegepuzzles mit sich unterscheidenden Invarianten nicht äquivalent sein können. Die Umkehrung gilt jedoch nicht, Geduldspiele mit gleichen Invarianten können durchaus nicht-äquivalent sein.
Der Fingerabdruck
Deshalb soll einem Anlegespiel ein sogenannter Fingerabdruck zugeordnet werden, der für äquivalente Puzzles derselbe ist, sich bei Austauschen und Umorientieren der Einzelbilder also nicht ändert. Damit können wir einfach entscheiden, ob wir ein neues oder ein bekanntes Geduldspiel vor uns liegen haben.
Das grundlegende Vorgehen ist folgendermaßen: Den Halbbildern auf den Karten werden Symbole aus der Menge ABCDabcd zugeordnet: Zusammenpassende Teile an den Kanten sind Aa, Bb, Cc und Dd. Groß- bzw. Kleinbuchstabe haben nichts mit Ober- / Unterteil eines geteilten Bildes zu tun, da die Zuordnung auf einem anderen Geduldspiel auch anders sein könnte. Strings aus diesen Buchstaben haben eine alphabetische Ordnung: Diese Ordnung solcher Strings ergibt sich aus der natürlich Ordnung der acht Zeichen wie angegeben, groß vor klein, dann alphabetisch. Alles zeichenweise von links nach rechts.
Wir betrachten jetzt eine dieser Zuordnungen. Mit ihr verfügen wir jetzt über eine Beschreibung einer Karte in einer vorgegebenen Orientierung, bestehend aus vier Buchstaben zu den Halbbildern oben, rechts, unten und links. Bei Rotation der Karte um 90 Grad ändert sich diese Beschreibung. Als minimale Beschreibung bezeichnen wir die alphabetisch kleinste dieser vier Möglichkeiten. Wenn wir diese minimalen Beschreibungen aller neun Karten in der eben erklärten alphabetischen Reihenfolge hintereinanderschreiben (der Übersichtlichkeit halber durch Minuszeichen getrennt), haben wir eine Beschreibung aller neun Karten in einem String. Dies ist die Beschreibung des Spiels entsprechend der gewählten Zuordnung.
Jetzt müssen wir nur noch aus den vielen möglichen Zuordnungen diejenige auswählen, welche die in alphabetischer Ordnung kleinste Beschreibung des Spieles liefert. Dies nennen wir den Fingerabdruck des Spiels.
Etwas ausführlicher ist der Fingerabdruck in [1] erklärt.
Solch ein typischer Fingerabdruck ist
Mehr Infos: