Das Affenpuzzle

Ein Kartenpuzzle

Kennst du das Affenpuzzle?

Das Puzzle besteht (hier) aus 9 Affen-Karten, die man passend aneinander legen muss.

Aufgabe 1

(a) Drucke das Puzzle aus, schneide die Karten aus und versuche, das Puzzle zu lösen.

(b) Wenn Du das Puzzle geschafft hast, kannst Du die Variante mit 4x4 Karten probieren.

(c) Für Mutige: Das Affenpuzzle gibt es auch in einer 5x5-Version.

(d) Zum Experimentieren kannst du auch das folgende Javascript-Puzzle benutzen. Ziehe die Karten an die gewünschte Position und drehe sie, indem du auf sie klickst.

Ein Algorithmus zur Lösung des Affenpuzzles

Selbst bei recht einfachen Puzzles wie dem 3x3-Affenpuzzle oben kann es eine Weile dauern, bis man die Lösung gefunden hat. Bei größeren Puzzles wie dem 4x4- bzw. 5x5-Puzzle dauert es schon sehr lange bzw. kommt man ans Verzweifeln. Man muss viele Kartenkonfigurationen ausprobieren, um sie dann doch wieder zu verwerfen.

Das Erzeugen und Überprüfen sehr vieler Kartenkonfigurationen ist eine Aufgabe, die man gut an einen Computer übertragen kann.

Ein naiver Algorithmus zur Lösung des Affenpuzzles geht von folgender Idee aus:

Man wählt eine bestimmte Kartenreihenfolge aus (eine sog. Permutation der Ausgangskartenreihe). Zudem wählt man eine bestimmte Orientierung der einzelnen Karten (jede Karte kann ja in 4 unterschiedlichen Ausrichtungen hingelegt werden). Wenn man jetzt die zur Permutation und Orientierung gehörende Kartenreihe in das 3x3-Kartenfeld legt (z.B. von links oben nach rechts unten), dann kann man anschließend überprüfen, ob die Kartenübergänge alle stimmen.

ALGORITHMUS affenpuzzle(n):
    erzeuge n*n Karten
    erzeuge die Startpermutation der Karten
    SOLANGE die letzte Permutation noch nicht erreicht und noch keine Lösung gefunden ist:
        erzeuge eine Startorientierung der Karten
        SOLANGE die letzte Orientierung noch nicht erreicht ist:
            erzeuge das Kartenfeld zur Permutation und zur Orientierung
            überprüfe das Kartenfeld
            WENN ok:
                Lösung = Kartenfeld
            erzeuge die nächste Orientierung
        erzeuge die nächste Permutation
    Rückgabe: (Karten, Lösung)

Eine Python-Implementierung findest du hier: affenpuzzle.zip.

Aufgabe 2

Du musst nicht alle Details der Implementierung verstehen. Wichtig für die Benutzung ist vor allem die Funktion affenpuzzle(n). Der Parameter n steht hier für die Größe des Puzzles. Bei einem 3x3-Puzzle beträgt die Größe n = 3.

(a) Beim Testen ist die Größe n = 2 voreingestellt. Führe die Testanweisungen mehrere Male aus und versuche zu verstehen, wie die Karten im Implementierungsprogramm dargestellt werden. Beachte, dass es vorkommen kann, dass die erzeugten Karten keine Puzzle-Lösung haben.

(b) Stelle beim Testen die Größe n = 3 ein. Wenn du jetzt die Ausführung startest, musst du erst einmal sehr lange warten. Wenn du ungeduldig wirst, dann versuche mit folgender Strategie die Wartezeit abzuschätzen:

Schritt 1: Berechne, wie viele Konfigurationen erzeugt werden. Überlege Dir, wie viele Permutationen der Ausgangskartenreihe möglich sind und wie viele Orientierungen jede Permutation zulässt. Zur Kontrolle: 95126814720

Schritt 2: In der Implementierung ist bereits eine Variable zaehler vorgesehen, die die erzeugten Konfigurationen mitzählt. Ergänze im Programm eine Ausgabeanweisung, die bei jeweils 1 Million überprüfter Konfigurationen eine Ausgabe auf dem Bildschirm macht. Stoppe dann die Zeit, die für 1 Million Konfigurationsüberprüfungen benötigt wird.

Schritt 3: Mit den Ergebnissen aus Schritt 1 und Schritt 2 kannst du jetzt eine Hochrechnung machen.