Affenpuzzle/4x4
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
Das Affenpuzzle (oder auch Hexenpuzzle) ist ein kombinatorisches Rätsel. Es besteht aus 9, 16, 25 oder mehr Karten die in einer Matrix angeordnet werden. Ziel des Spiels ist es die Karten so zu legen und zu drehen, das alle Teile (hier der Hexen) zusammenpassen.
== Das Affenpuzzle (Hexenpuzzle) ==
Legen Sie die Karten in einem Feld 4x4 Karten so, dass alle Teile zusammenpassen.
== Lösung mit dem Computer ==
Würde man alle möglichen Kombinationen durchprobieren, wären das bei 3x3 bereits 95126814720 Kartenstellungen. Auch mit einem leistungsstarken Computer dauert das mehrere Stunden, diese alle durchzuprobieren.
Zum Glück müssen wir aber nicht alle Kombinationen ausprobieren. Sollte schon die erste zur zweiten Karte nicht passen, müssen wir die restlichen Kombinationen mit diesem Anfang ja gar nicht weiterverfolgen. Der nachfolgende Algorithmus nutzt das aus und legt zunächst eine Karte aufs Feld. Bei der zweiten Karte wird bereits geprüft, ob diese zur ersten passt und nur dann mit der Suche fortgesetzt.
<run id="638488538c64e">
// wir definieren die 8 verschiedenen Bilder mit Zahlen
// die Abstände der Zahlen sind so gewählt, dass wir durch Subtraktion
// immer einen Abstand von 1 haben, wenn die beiden Teile zusammenpassen
var Werte = {
KopfNormal: 1, BauchNormal:2,
Kopfpunkt: 4, BauchPunkt:5,
KopfDickpunkt: 7, BauchDickpunkt:8,
KopfSchwarz:10, BauchSchwarz:11
}
// die 16 Karten als Listen:
var Karten = [];
Karten[0] = [Werte.Kopfpunkt,Werte.KopfSchwarz,Werte.KopfDickpunkt,Werte.BauchNormal];
Karten[1] = [Werte.BauchPunkt,Werte.KopfSchwarz,Werte.KopfNormal,Werte.Kopfpunkt];
Karten[2] = [Werte.BauchDickpunkt,Werte.Kopfpunkt,Werte.BauchNormal,Werte.KopfNormal];
Karten[3] = [Werte.BauchDickpunkt,Werte.BauchPunkt,Werte.KopfSchwarz,Werte.KopfNormal];
Karten[4] = [Werte.BauchSchwarz,Werte.KopfSchwarz,Werte.KopfNormal,Werte.BauchSchwarz];
Karten[5] = [Werte.Kopfpunkt,Werte.BauchNormal,Werte.BauchSchwarz,Werte.KopfSchwarz];
Karten[6] = [Werte.Kopfpunkt,Werte.KopfSchwarz,Werte.KopfNormal,Werte.BauchPunkt];
Karten[7] = [Werte.KopfDickpunkt,Werte.KopfDickpunkt,Werte.BauchDickpunkt,Werte.KopfNormal];
Karten[8] = [Werte.BauchPunkt,Werte.KopfSchwarz,Werte.KopfDickpunkt,Werte.KopfSchwarz];
Karten[9] = [Werte.BauchNormal,Werte.BauchSchwarz,Werte.KopfDickpunkt,Werte.Kopfpunkt];
Karten[10] = [Werte.KopfNormal,Werte.BauchPunkt,Werte.KopfDickpunkt,Werte.KopfDickpunkt];
Karten[11] = [Werte.KopfDickpunkt,Werte.BauchSchwarz,Werte.BauchPunkt,Werte.Kopfpunkt];
Karten[12] = [Werte.BauchDickpunkt,Werte.KopfNormal,Werte.Kopfpunkt,Werte.BauchDickpunkt];
Karten[13] = [Werte.BauchDickpunkt,Werte.KopfNormal,Werte.BauchNormal,Werte.KopfNormal];
Karten[14] = [Werte.KopfNormal,Werte.BauchSchwarz,Werte.Kopfpunkt,Werte.BauchSchwarz];
Karten[15] = [Werte.BauchDickpunkt,Werte.BauchPunkt,Werte.BauchDickpunkt,Werte.BauchSchwarz];
var loesungen = 0;
var tests = 0;
var Kartenfeld = [];
var Platziert = [];
// Initialisierung mit leeren Daten
for(var i=0; i < 16; i++){
Kartenfeld[i] = -1;
Platziert[i] = false;
}
// die eigentliche Suchfunktion ist rekursiv und ruft sich selbst mit der nächsten Karte auf
function suchen(feld,gesetzt,platz){
for(var k=0; k < Karten.length; k++){
if(!gesetzt[k]){
feld[platz] = k;
gesetzt[k] = true;
for(var r=0; r<4; r++){
tests++;
if(kartePruefen(feld,platz)){
if(platz == Karten.length-1){
loesungen++;
console.log("Lösung:\n"+spielfeldAusgeben(feld));
}
suchen(feld,gesetzt,platz+1);
}
// Karten drehen, indem die 4 Zahlen der Karte um eine Stelle verschoben werden
var p = Karten[k].shift();
Karten[k].push(p);
}
feld[platz] = -1;
gesetzt[k]=false;
}
}
}
// für eine Karte wird getestet, ob alle Nachbarkarten daran passen
// wurde noch keine Nachbarkarte bestimmt (-1) dann akzeptieren wir die Karte
// feld = alle Karten auf dem Spielfeld
// platz = position der Karte auf dem Spielfeld, die getestet wird (0 1 2 3 / 4 5 6 7 / 8 9 10 11 / 12 13 14 15)
// um eine Karte herum oben = [0], rechts = [1], unten = [2], links = [3]
function kartePruefen(feld, platz){
if(platz == 0){
if(feld[1] != -1 && Math.abs(Karten[feld[0]][1] - Karten[feld[1]][3]) != 1) return false;
if(feld[4] != -1 && Math.abs(Karten[feld[0]][2] - Karten[feld[4]][0]) != 1) return false;
return true;
}
if(platz == 1){
if(feld[0] != -1 && Math.abs(Karten[feld[1]][3] - Karten[feld[0]][1]) != 1) return false;
if(feld[5] != -1 && Math.abs(Karten[feld[1]][2] - Karten[feld[5]][0]) != 1) return false;
if(feld[2] != -1 && Math.abs(Karten[feld[1]][1] - Karten[feld[2]][3]) != 1) return false;
return true;
}
if(platz == 2){
if(feld[1] != -1 && Math.abs(Karten[feld[2]][3] - Karten[feld[1]][1]) != 1) return false;
if(feld[6] != -1 && Math.abs(Karten[feld[2]][2] - Karten[feld[6]][0]) != 1) return false;
if(feld[3] != -1 && Math.abs(Karten[feld[2]][1] - Karten[feld[3]][3]) != 1) return false;
return true;
}
if(platz == 3){
if(feld[2] != -1 && Math.abs(Karten[feld[3]][3] - Karten[feld[2]][1]) != 1) return false;
if(feld[7] != -1 && Math.abs(Karten[feld[3]][2] - Karten[feld[7]][0]) != 1) return false;
return true;
}
if(platz == 4){
if(feld[0] != -1 && Math.abs(Karten[feld[4]][0] - Karten[feld[0]][2]) != 1) return false;
if(feld[5] != -1 && Math.abs(Karten[feld[4]][1] - Karten[feld[5]][3]) != 1) return false;
if(feld[8] != -1 && Math.abs(Karten[feld[4]][2] - Karten[feld[8]][0]) != 1) return false;
return true;
}
if(platz == 5){
if(feld[9] != -1 && Math.abs(Karten[feld[5]][2] - Karten[feld[9]][0]) != 1) return false;
if(feld[6] != -1 && Math.abs(Karten[feld[5]][1] - Karten[feld[6]][3]) != 1) return false;
if(feld[4] != -1 && Math.abs(Karten[feld[5]][3] - Karten[feld[4]][1]) != 1) return false;
if(feld[1] != -1 && Math.abs(Karten[feld[5]][0] - Karten[feld[1]][2]) != 1) return false;
return true;
}
if(platz == 6){
if(feld[10]!= -1 && Math.abs(Karten[feld[6]][2] - Karten[feld[10]][0]) != 1) return false;
if(feld[7] != -1 && Math.abs(Karten[feld[6]][1] - Karten[feld[7]][3]) != 1) return false;
if(feld[5] != -1 && Math.abs(Karten[feld[6]][3] - Karten[feld[5]][1]) != 1) return false;
if(feld[2] != -1 && Math.abs(Karten[feld[6]][0] - Karten[feld[2]][2]) != 1) return false;
return true;
}
if(platz == 7){
if(feld[11]!= -1 && Math.abs(Karten[feld[7]][2] - Karten[feld[11]][0]) != 1) return false;
if(feld[6] != -1 && Math.abs(Karten[feld[7]][3] - Karten[feld[6]][1]) != 1) return false;
if(feld[3] != -1 && Math.abs(Karten[feld[7]][0] - Karten[feld[3]][2]) != 1) return false;
return true;
}
if(platz == 8){
if(feld[4] != -1 && Math.abs(Karten[feld[8]][0] - Karten[feld[4]][2]) != 1) return false;
if(feld[9] != -1 && Math.abs(Karten[feld[8]][1] - Karten[feld[9]][3]) != 1) return false;
if(feld[12]!= -1 && Math.abs(Karten[feld[8]][2] - Karten[feld[12]][0]) != 1) return false;
return true;
}
if(platz == 9){
if(feld[5] != -1 && Math.abs(Karten[feld[9]][0] - Karten[feld[5]][2]) != 1) return false;
if(feld[10]!= -1 && Math.abs(Karten[feld[9]][1] - Karten[feld[10]][3]) != 1) return false;
if(feld[8] != -1 && Math.abs(Karten[feld[9]][3] - Karten[feld[8]][1]) != 1) return false;
if(feld[13]!= -1 && Math.abs(Karten[feld[9]][2] - Karten[feld[13]][0]) != 1) return false;
return true;
}
if(platz == 10){
if(feld[6] != -1 && Math.abs(Karten[feld[10]][0] - Karten[feld[6]][2]) != 1) return false;
if(feld[11]!= -1 && Math.abs(Karten[feld[10]][1] - Karten[feld[11]][3]) != 1) return false;
if(feld[9] != -1 && Math.abs(Karten[feld[10]][3] - Karten[feld[9]][1]) != 1) return false;
if(feld[14]!= -1 && Math.abs(Karten[feld[10]][2] - Karten[feld[14]][0]) != 1) return false;
return true;
}
if(platz == 11){
if(feld[7] != -1 && Math.abs(Karten[feld[11]][0] - Karten[feld[7]][2]) != 1) return false;
if(feld[10]!= -1 && Math.abs(Karten[feld[11]][3] - Karten[feld[10]][1]) != 1) return false;
if(feld[15]!= -1 && Math.abs(Karten[feld[11]][2] - Karten[feld[15]][0]) != 1) return false;
return true;
}
if(platz == 12){
if(feld[13]!= -1 && Math.abs(Karten[feld[12]][1] - Karten[feld[13]][3]) != 1) return false;
if(feld[8] != -1 && Math.abs(Karten[feld[12]][0] - Karten[feld[8]][2]) != 1) return false;
return true;
}
if(platz == 13){
if(feld[14]!= -1 && Math.abs(Karten[feld[13]][1] - Karten[feld[14]][3]) != 1) return false;
if(feld[9] != -1 && Math.abs(Karten[feld[13]][0] - Karten[feld[9]][2]) != 1) return false;
if(feld[12]!= -1 && Math.abs(Karten[feld[13]][3] - Karten[feld[12]][1]) != 1) return false;
return true;
}
if(platz == 14){
if(feld[15]!= -1 && Math.abs(Karten[feld[14]][1] - Karten[feld[15]][3]) != 1) return false;
if(feld[10]!= -1 && Math.abs(Karten[feld[14]][0] - Karten[feld[10]][2]) != 1) return false;
if(feld[13]!= -1 && Math.abs(Karten[feld[14]][3] - Karten[feld[13]][1]) != 1) return false;
return true;
}
if(platz == 15){
if(feld[11]!= -1 && Math.abs(Karten[feld[15]][0] - Karten[feld[11]][2]) != 1) return false;
if(feld[14]!= -1 && Math.abs(Karten[feld[15]][3] - Karten[feld[14]][1]) != 1) return false;
return true;
}
}
// Ausgabe einer Lösung - die Karten wie im Bild oben sind durchnummeriert
// von links nach rechts bzw. oben nach unten
// Ausgabe der Karte als Zahl + welches Bild nach oben zeigen muss.
function spielfeldAusgeben(Kartenfeld){
function lesbar(n){
for(k in Werte){
if(Werte[k] == n) {
var s = k;
while (s.length < 10) s = s + " ";
return s;
}
}
}
var s = "";
var zeilen = Math.round(Math.sqrt(Kartenfeld.length));
for(var i=0; i < Kartenfeld.length; i++){
s += "[ Karte "+Kartenfeld[i] +" ↑ "+lesbar(Karten[Kartenfeld[i]][0])+" ] ";
if(i % zeilen == zeilen-1) s += "\n";
}
return (s);
}
suchen(Kartenfeld,Platziert,0);
console.log("Es wurden "+tests+" Tests gemacht und "+loesungen+" Lösungen gefunden.");
</run>