Daniel

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Das Affenpuzzle 2 Lösung des Puzzles 3 Abschätzung des Berechnungsaufwands 4 Quellen

Das Affenpuzzle

Das Affenpuzzle ist ein kombinatorisches Rätsel. Es besteht aus 9, 16, 25 oder mehr Karten, die zu einem Quadrat angeordnet werden. Die Formen können entweder Affen, Hexen oder anderen Formen sein und bestehen jeweils aus einem Ober- und Unterteil in einer bestimmten Farbe. Das heißt eine Karte besteht aus 4 Teilen von, in dem Fall, Affen in unterschiedlichen Farben. Das Ziel des Spieles ist es, dass Puzzle zu lösen, indem man die Karten so dreht und verschiebt bis alle Karten zusammen passen.

Lösung des Puzzles

Zur Lösung des Puzzels gibt es drei Anzätze:

1. Einmal die physische Variante bei der man sich das Puzzle ausdruckt oder selber bastelt und es dann versucht zu lösen. Dazu einfach die Fotodatei oben ausdrucken, ausschneiden und lospuzzeln.


2. Die nächste mögliche Lösung ist eine Anwendung, welche einem erlaubt das Puzzle per Maus zu lösen. Hier kannst du diese downloaden:

   TheFloeng_Affenpuzzle.zip (0.1 MB)



3. Und als dritte Möglichkeit ist die automatische Lösung des Puzzels per Code. Da meine Programmierkenntnis leider nicht ausreicht um so einen Code selber zu schreiben, muss ich auf jemanden verweisen, der dies schon gelöst hat:
   http://.de/Affenpuzzle Autor wird "Admin" angegeben.

Abschätzung des Berechnungsaufwands

Der Berechnungsaufwand wird hier wesentlich durch die Anzahl der Kartenkonfigurationen bestimmt, die hier systematisch erzeugt und überprüft werden. Mit der Kostenfunktion K(n) beschreiben wir diesen Berechnungsaufwand:
K(n) gibt an, wie viele verschiedene Kartenkonfigurationen es bei einer Problemgröße n gibt. n gibt dabei die Anzahl pro Karten pro Reihe/Spalte/Diagonale an.

Für die Herleitung wird zuerst das Beispiel n=3 durchgespielt. Bei n=3 beträgt die Anzahl der Karten 3*3= 9 Karten. Wenn man jetzt die Karten nacheinander anordnet, dann gibt es 9 Möglichkeiten für die erste Karte, 8 Möglichkeiten für die zweite Karte, 7 Möglichkeiten für die dritte Karte, ... 2 Möglichkeiten für die achte Karte und schließlich 1 Möglichkeit für die neunte Karte.

Also gibt es bei 9 Karten also 9*8*7*6*5*4*3*2*1 verschiedene Anordnungsmöglichkeiten(Permutationen). //=Entspricht 9! (sprich 9 Fakultät)

Nach Anordnung der Karten gibt es nun 4 Möglichkeiten wie jede dieser Ausgerichtet sein kann. Also gibt es 4*4*4*4*4*4*4*4*4 verschiedene "Orientierungen der Karten. //=Entspricht 4³ Diese beiden Teile werden nun multipliziert und es ergeben sich 4⁹*9! bzw. 4^(3*3)*(3*3)! verschiedene Kartenkonfigurationen.
Allgemein erhält man die Formel:

K(n)=4^(n*n)*(n*n)!

---

Die Anzahl der Möglichkeiten steigt schneller als jede Exponentialfunktion und bereits für kleine n-Werte werden riesige Funktionswerte bzw. Möglichkeiten der Anordnung geliefert.
Wenn man davon ausgeht, dass ein Rechner zur Erzeugung und Überprüfung von 1 Million Konfigurationen 1 Sekunde benötigt, dann besagt der Wert T(3) = 95126814720, dass für ein 3x3-Puzzle im 'ungünstigsten' Fall mehr als 95126 Sekunden (das ist mehr als ein Tag) benötigt werden.

Hier kannst du sehen wie viele Möglichkeiten es bei n Karten gibt:

function Fakultaet(n){ var x= 1; for(var i=1; i<=n; i++){ x = x*i; } return x; } function Affe(n){ var k = Math.pow(4,(n*n))*Fakultaet((n*n)); return k; } Affe(2);

ausführen

Quellen

https://www.inf-schule.de/grenzen/komplexitaet/affenpuzzle/ergebnisse_komplexitaetsaussagen
http://.de/Affenpuzzle
https://forum.selfhtml.org/ für Commands