Daniel

Aus ProgrammingWiki
< IKG2018 < Einführung
Archivierte Version vom 2018-03-21T18:38:27+00:00. Aktuelle Version

Inhaltsverzeichnis

Das Affenpuzzle

TheFloeng_Affenpuzzle3.png

Das Affenpuzzle ist ein kombinatorisches Rätsel.

Es besteht aus 9, 16, 25 oder mehr Karten die zu einem Quadrat angeordnet werden.
Die Affen, Hexen oder anderen Formen bestehen jeweils aus einem Ober- und Unterteil in einer bestimmten Farbe. Also besteht eine Karte aus 4 Teilen von, in diesem Fall, Affen in unterschiedlichen Farben.


Ziel des Spiel ist es das Puzzle zu lösen, indem man die Karten so dreht und verschiebt bis alles passt.




Lösung des Puzzles


Dazu gibt es 3 verschiedene Lösungsvorschläge: 
    

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

    Als nächstes gibt es da eine Anwendung, welche einem erlaubt Das Puzzle per Maus zu lösen.
Hier kannst du diese downloaden:TheFloeng_Affenpuzzle.zip 
    3.   
  3. 

    Und als dritte Möglichkeit ist die Lösung per Computer. 
Da ich aber nicht allzu viel Programmierkenntnis habe muss ich auf jemanden verweisen der dies schon gelöst hat: 
    
http://.de/Affenpuzzle Autor wird "Admin" angegeben.''  
    4.  

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! (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 43
Diese beiden Teile werden nun multipliziert und es ergeben sich 49*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:



Quellen
https://www.inf-schule.de/grenzen/komplexitaet/affenpuzzle/ergebnisse_komplexitaetsaussagen 

http://.de/Affenpuzzle

https://forum.selfhtml.org/ für Commands