Affenpuzzle

Wir haben heute das Affenpuzzle gespielt. Alle Gruppen haben ein Puzzle der Größe 2×2 geschaft, einige auch ein Puzzle der Größe 3×3. Online kann man es auch auf inf-schule.de spielen. Insgesamt ist das Puzzle deutlich schwerer als man es zuerst vermutet.

Wie schwer kann man erahnen, wenn man sich klar macht wie viele Möglichkeiten es gibt das Puzzle zu legen. Für n*n Karten (n ist die Kantenlänge des Puzzles) gibt es (n*n)! Permutationen. Außerdem gibt es für jede Karte 4 Drehrichtungen. Somit ergibt sich insgesamt eine mögliche Zahl an Anordnungen von (n*n)! * 4^(n*n).

Die Simulation am Computer kann man auch von inf-schule.de herunterladen. Ein erster Test mit einem 2×2-Puzzle lief sehr schnell ab. Zu beachten ist, dass es hier auch (oft) vorkommen kann, dass es keine Lösung gibt. Für uns ist das aber kein Problem, da wir den worst-case untersuchen wollen. (Der best-case ist uninteressant, da man mit extrem viel Glück direkt richtig rät)

Ein Laufzeittest mit einem 3×3-Puzzle endete nicht schnell genug, um ein Ergebnis innerhalb der Stunde zu beobachten.

HA: Das Programm soll so erweitert werden, dass man für ein Puzzle der Größe n=3,4,5 abschätzen kann, wie lange dieses im worst-case läuft. Dazu muss eine Zählvariable eingeführt werden und z.B. alle 1000000 Schritte die Zeit gemessen werden.

Schreibe einen Kommentar