Das Affenpuzzle-Problem

Filed Under: German by admin — 2 Comments

26.02.2012

Da wir vor einiger Zeit im Informatikunterricht mit Backtracking-Algorithmen befasst und uns auch das Affenpuzzle angesehen haben, hatte ich mich entschlossen, ein kleines C++-Programm zu schreiben, welches selbiges löst.
Unter http://www.swisseduc.ch/informatik/120-lektionen/principles/computation/kara/docs/affenpuzzle_bastelbogen_unprotected.pdf kann man sich die Bastelvorlage des Affenpuzzles herunterladen.

Das Affenrätsel ist ein Puzzle, welches aus einem Quadrat aus mit einer bestimmten Kantenlänge (2, 3, 4, 5 oder mehr) Karten besteht. Jede Karte muss passend an die andere angelegt werden, sodass ein beispielsweise gelber Affenkopf nur an einem gelben Affenkörper anliegt. Dabei gibt es nur eine begrenzte Anzahl an Lösungen, welche ausschließlich durch ein sogenanntes Backtracking-Verfahren herauszufinden sind.

// Affenpuzzle.cpp: Birk Blechschmidt, 14 November 2011
// Dieser Kommentar muss erhalten bleiben.

#include "iostream"
#include "string"
#include "time.h"
using namespace std;

const char greenhead=1;
const char greenbody=2;
const char redhead=4;
const char redbody=5;
const char bluehead=7;
const char bluebody=8;
const char yellowhead=10;
const char yellowbody=11;
time_t beginning, ending;
double timespan;

long solutioncount=0;

long iterationcount=0;

const char rowcount=4;

const char fieldcount=rowcount*rowcount;
char cards[fieldcount][4];
char rotations[fieldcount];
char table[fieldcount];
bool set[fieldcount];
char* solutions=new char[0];

char modulus(char input)
{
	char output=input;
	if(output < 0)
	{
		output*=-1;
	}
	return output;
}

string getReadableName(char input)
{
	string name="";
	if(input==greenhead)
	{
		name="gh";
	}
	if(input==greenbody)
	{
		name="gb";
	}
	if(input==redhead)
	{
		name="rh";
	}
	if(input==redbody)
	{
		name="rb";
	}
	if(input==bluehead)
	{
		name="bh";
	}
	if(input==bluebody)
	{
		name="bb";
	}
	if(input==yellowhead)
	{
		name="yh";
	}
	if(input==yellowbody)
	{
		name="yb";
	}
	return name;
}

void rotateCard(char cardnumber, char rotationcount) //Uhrzeigersinn
{
	if(rotationcount !=0)
	{
		char tempCard[4];
		for(char i=0; i < 4; i++)
		{
			tempCard[i]=cards[cardnumber][i];
		}
		for(char i=0; i < 4; i++)
		{
			char newindex=i-rotationcount;
			while(newindex < 0)
			{
				newindex+=4;
			}
			while(newindex > 3)
			{
				newindex-=4;
			}
			cards[cardnumber][i]=tempCard[newindex];
		}
		rotations[cardnumber]+=rotationcount;
		while(rotations[cardnumber] < 0)
		{
			rotations[cardnumber]+=4;
		}
		while(rotations[cardnumber] > 3)
		{
			rotations[cardnumber]-=4;
		}
	}
}

bool validNeighbours(char cardnumber, bool debug=false)
{
	bool valid=true;
	if(cardnumber % rowcount > 0)
	{
		if(table[cardnumber-1]!=-1)
		{
			if(modulus(cards[table[cardnumber]][3]-cards[table[cardnumber-1]][1])!=1)
			{
				valid=false;
			}
		}
	}

	if(cardnumber % rowcount < rowcount-1)
	{
		if(modulus(cards[table[cardnumber]][1]-cards[table[cardnumber+1]][3])!=1)
		{
			if(table[cardnumber+1]!=-1)
			{
				valid=false;
			}
		}
	}

	if(cardnumber >= rowcount)
	{
		if(modulus(cards[table[cardnumber]][0]-cards[table[cardnumber-rowcount]][2])!=1)
		{
			if(table[cardnumber-rowcount]!=-1)
			{
				valid=false;
			}
		}
	}

	if(cardnumber < fieldcount-rowcount)
	{
		if(modulus(cards[table[cardnumber]][2]-cards[table[cardnumber+rowcount]][0])!=1)
		{
			if(table[cardnumber+rowcount]!=-1)
			{
				valid=false;
			}
		}
	}

	return valid;
}

void printCards()
{
	for(char yC=0; yC < rowcount; yC++)
	{
		for(char xC=0; xC < rowcount; xC++)
		{
			cout << " |";
			cout << getReadableName(cards[table[yC*rowcount+xC]][0]) << "| ";
		}
		cout << endl;
		for(char xC=0; xC < rowcount; xC++)
		{
			cout << getReadableName(cards[table[yC*rowcount+xC]][3]) << "| |";
			cout << getReadableName(cards[table[yC*rowcount+xC]][1]) <<" ";
		}
		cout << endl;
		for(char xC=0; xC < rowcount; xC++)
		{

			cout << " |";
			cout << getReadableName(cards[table[yC*rowcount+xC]][2]) << "| ";
		}
		cout << endl<<endl;
	}
}

void solve(char fieldnumber)
{
	for(char card=0; card < fieldcount; card++)
	{
		if(!set[card])
		{
			table[fieldnumber]=card;
			set[card]=true;
			for(char r=0; r<4; r++)
			{
				iterationcount++;
				if(validNeighbours(fieldnumber))
				{
					if(fieldnumber == fieldcount-1)
					{

						if(rotations[0]==0)
						{
							solutioncount++;
							cout << "Solution:"<<endl<<endl;
							char* temparr=new char[solutioncount*fieldcount*2];
							for(int i=0; i < solutioncount-1; i++)
							{
								for(int j=0; j < fieldcount; j++)
								{
									temparr[i*fieldcount*2+j*2]=solutions[i*fieldcount*2+j*2];
									temparr[i*fieldcount*2+j*2+1]=solutions[i*fieldcount*2+j*2+1];
								}
							}
							for(int i=0; i < fieldcount; i++)
							{
								temparr[(solutioncount-1)*fieldcount*2+i*2]=table[i];
								temparr[(solutioncount-1)*fieldcount*2+i*2+1]=rotations[table[i]];
							}
							solutions=new char[solutioncount*fieldcount*2];
							for(int i=0; i < solutioncount; i++)
							{
								for(int j=0; j < fieldcount; j++)
								{
									solutions[i*fieldcount*2+j*2]=temparr[i*fieldcount*2+j*2];
									solutions[i*fieldcount*2+j*2+1]=temparr[i*fieldcount*2+j*2+1];
								}
							}

								printCards();

							cout << endl<<endl;
						}
					}

					solve(fieldnumber+1);
				}
				rotateCard(card, 1);
			}
			table[fieldnumber]=-1;
			set[card]=false;
		}
	}
}

int main()
{

	//Kartendefinition 2*2
	/*cards[0][0]=greenbody;
 cards[0][1]=redhead;
 cards[0][2]=greenbody;
 cards[0][3]=bluehead;

 cards[1][0]=bluebody;
 cards[1][1]=greenhead;
 cards[1][2]=yellowhead;
 cards[1][3]=redbody;

 cards[2][0]=yellowbody;
 cards[2][1]=bluebody;
 cards[2][2]=redbody;
 cards[2][3]=bluehead;

 cards[3][0]=greenhead;
 cards[3][1]=bluebody;
 cards[3][2]=bluehead;
 cards[3][3]=yellowbody;*/

	//Kartendefinition 4*4
	cards[0][0]=redhead;
	cards[0][1]=bluehead;
	cards[0][2]=yellowhead;
	cards[0][3]=yellowhead;

	cards[1][0]=yellowbody;
	cards[1][1]=redhead;
	cards[1][2]=greenhead;
	cards[1][3]=redhead;

	cards[2][0]=redbody;
	cards[2][1]=bluehead;
	cards[2][2]=yellowbody;
	cards[2][3]=bluebody;

	cards[3][0]=bluebody;
	cards[3][1]=bluehead;
	cards[3][2]=yellowbody;
	cards[3][3]=greenhead;

	cards[4][0]=redbody;
	cards[4][1]=bluebody;
	cards[4][2]=greenhead;
	cards[4][3]=yellowhead;

	cards[5][0]=bluebody;
	cards[5][1]=redbody;
	cards[5][2]=bluehead;
	cards[5][3]=redbody;

	cards[6][0]=bluehead;
	cards[6][1]=bluehead;
	cards[6][2]=yellowbody;
	cards[6][3]=greenbody;

	cards[7][0]=redhead;
	cards[7][1]=greenhead;
	cards[7][2]=yellowhead;
	cards[7][3]=greenhead;

	cards[8][0]=redhead;
	cards[8][1]=greenbody;
	cards[8][2]=bluehead;
	cards[8][3]=greenbody;

	cards[9][0]=bluebody;
	cards[9][1]=greenhead;
	cards[9][2]=yellowbody;
	cards[9][3]=yellowbody;

	cards[10][0]=greenbody;
	cards[10][1]=bluehead;
	cards[10][2]=yellowhead;
	cards[10][3]=redbody;

	cards[11][0]=yellowbody;
	cards[11][1]=greenhead;
	cards[11][2]=greenbody;
	cards[11][3]=bluebody;

	cards[12][0]=greenbody;
	cards[12][1]=yellowhead;
	cards[12][2]=bluehead;
	cards[12][3]=bluehead;

	cards[13][0]=greenbody;
	cards[13][1]=yellowhead;
	cards[13][2]=redhead;
	cards[13][3]=redhead;

	cards[14][0]=yellowbody;
	cards[14][1]=greenhead;
	cards[14][2]=redhead;
	cards[14][3]=bluebody;

	cards[15][0]=redbody;
	cards[15][1]=yellowhead;
	cards[15][2]=redbody;
	cards[15][3]=greenhead;

	//Kartendefinition 6*6
	/*cards[0][0]=redbody;
 cards[0][1]=redhead;
 cards[0][2]=yellowhead;
 cards[0][3]=bluebody;

 cards[1][0]=redhead;
 cards[1][1]=redbody;
 cards[1][2]=yellowbody;
 cards[1][3]=bluehead;

 cards[2][0]=yellowhead;
 cards[2][1]=greenbody;
 cards[2][2]=greenbody;
 cards[2][3]=bluehead;

 cards[3][0]=greenhead;
 cards[3][1]=bluebody;
 cards[3][2]=yellowhead;
 cards[3][3]=yellowbody;

 cards[4][0]=redhead;
 cards[4][1]=greenhead;
 cards[4][2]=bluebody;
 cards[4][3]=bluebody;

 cards[5][0]=yellowhead,
 cards[5][1]=yellowhead;
 cards[5][2]=redbody;
 cards[5][3]=greenbody;

 cards[6][0]=redbody;
 cards[6][1]=redbody;
 cards[6][2]=redhead;
 cards[6][3]=bluehead;

 cards[7][0]=bluebody;
 cards[7][1]=redbody;
 cards[7][2]=redhead;
 cards[7][3]=bluehead;

 cards[8][0]=yellowbody;
 cards[8][1]=redhead;
 cards[8][2]=bluehead;
 cards[8][3]=greenbody;

 cards[9][0]=redhead;
 cards[9][1]=yellowbody;
 cards[9][2]=redhead;
 cards[9][3]=greenhead;

 cards[10][0]=bluehead;
 cards[10][1]=bluebody;
 cards[10][2]=redhead;
 cards[10][3]=redhead;

 cards[11][0]=greenhead;
 cards[11][1]=bluebody;
 cards[11][2]=bluebody;
 cards[11][3]=greenhead;

 cards[12][0]=greenhead;
 cards[12][1]=greenhead;
 cards[12][2]=bluehead;
 cards[12][3]=yellowbody;

 cards[13][0]=yellowbody;
 cards[13][1]=greenbody;
 cards[13][2]=redbody;
 cards[13][3]=greenbody;

 cards[14][0]=yellowhead;
 cards[14][1]=redhead;
 cards[14][2]=greenhead;
 cards[14][3]=bluebody;

 cards[15][0]=bluehead;
 cards[15][1]=yellowbody;
 cards[15][2]=greenbody;
 cards[15][3]=redhead;

 cards[16][0]=yellowbody;
 cards[16][1]=greenhead;
 cards[16][2]=redhead;
 cards[16][3]=redbody;

 cards[17][0]=yellowhead;
 cards[17][1]=bluehead;
 cards[17][2]=yellowhead;
 cards[17][3]=redhead;

 cards[18][0]=bluehead;
 cards[18][1]=bluebody;
 cards[18][2]=greenbody;
 cards[18][3]=greenhead;

 cards[19][0]=bluebody;
 cards[19][1]=yellowhead;
 cards[19][2]=greenhead;
 cards[19][3]=redhead;

 cards[20][0]=redbody;
 cards[20][1]=greenhead;
 cards[20][2]=yellowhead;
 cards[20][3]=bluebody;

 cards[21][0]=greenhead;
 cards[21][1]=greenhead;
 cards[21][2]=bluehead;
 cards[21][3]=redhead;

 cards[22][0]=redhead;
 cards[22][1]=redhead;
 cards[22][2]=bluebody;
 cards[22][3]=yellowhead;

 cards[23][0]=greenhead;
 cards[23][1]=yellowbody;
 cards[23][2]=redhead;
 cards[23][3]=yellowhead;

 cards[24][0]=redbody;
 cards[24][1]=yellowhead;
 cards[24][2]=bluehead;
 cards[24][3]=yellowbody;

 cards[25][0]=redhead;
 cards[25][1]=redbody;
 cards[25][2]=bluebody;
 cards[25][3]=bluehead;

 cards[26][0]=greenhead;
 cards[26][1]=redbody;
 cards[26][2]=yellowbody;
 cards[26][3]=yellowhead;

 cards[27][0]=greenbody;
 cards[27][1]=bluehead;
 cards[27][2]=greenhead;
 cards[27][3]=greenhead;

 cards[28][0]=bluehead;
 cards[28][1]=bluebody;
 cards[28][2]=bluehead;
 cards[28][3]=greenbody;

 cards[29][0]=yellowbody;
 cards[29][1]=bluehead;
 cards[29][2]=redbody;
 cards[29][3]=redbody;

 cards[30][0]=yellowhead;
 cards[30][1]=redbody;
 cards[30][2]=greenbody;
 cards[30][3]=redhead;

 cards[31][0]=redbody;
 cards[31][1]=bluehead;
 cards[31][2]=redbody;
 cards[31][3]=yellowhead;

 cards[32][0]=redhead;
 cards[32][1]=bluehead;
 cards[32][2]=yellowbody;
 cards[32][3]=yellowhead;

 cards[33][0]=bluehead;
 cards[33][1]=yellowhead;
 cards[33][2]=redhead;
 cards[33][3]=yellowbody;

 cards[34][0]=bluehead;
 cards[34][1]=yellowhead;
 cards[34][2]=yellowbody;
 cards[34][3]=redhead;

 cards[35][0]=greenbody;
 cards[35][1]=yellowhead;
 cards[35][2]=bluebody;
 cards[35][3]=bluehead;*/

	cout << "Monkey Puzzle Solver by Birk Blechschmidt, 14 November 2011"<<endl<<endl;
	cout << "Puzzle size: "<<(short)rowcount<<"*"<<(short)rowcount<<"="<<(short)fieldcount<<endl<<endl;
	cout << "Initial cards: "<<endl<<endl;
	for(int i=0; i < fieldcount; i++)
	{
		table[i]=i;
	}
	printCards();
	cout << endl<<endl;
	for(int i=0; i < fieldcount; i++)
	{
		rotations[i]=0;
		table[i]=-1;
		set[i]=false;
	}
	cout << "Press ENTER key to start..."<<endl<<endl;
	fflush(stdin);
	getchar();
	time(&beginning);
	solve(0);
	time(&ending);
	timespan=difftime(ending, beginning);
	cout << "In total "<<solutioncount<<" solutions were found in "<<timespan<<" seconds and "<<iterationcount<<" iterations."<<endl << endl;
	cout << endl << "Press ENTER key to quit..."<<endl<<endl;
	fflush(stdin);
	getchar();
	return 0;
}

Die Ausgabe:

Monkey Puzzle Solver by Birk Blechschmidt, 14 November 2011

Puzzle size: 4*4=16

Initial cards:

  |rh|      |yb|      |rb|      |bb|
yh|  |bh  rh|  |rh  bb|  |bh  gh|  |bh
  |yh|      |gh|      |yb|      |yb|

  |rb|      |bb|      |bh|      |rh|
yh|  |bb  rb|  |rb  gb|  |bh  gh|  |gh
  |gh|      |bh|      |yb|      |yh|

  |rh|      |bb|      |gb|      |yb|
gb|  |gb  yb|  |gh  rb|  |bh  bb|  |gh
  |bh|      |yb|      |yh|      |gb|

  |gb|      |gb|      |yb|      |rb|
bh|  |yh  rh|  |yh  bb|  |gh  gh|  |yh
  |bh|      |rh|      |rh|      |rb|

Press ENTER key to start...

Solution:

  |rh|      |gh|      |gh|      |gb|
yh|  |bh  bb|  |yb  yh|  |rh  rb|  |bh
  |yh|      |yb|      |gh|      |yh|

  |yb|      |yh|      |gb|      |yb|
rh|  |rh  rb|  |rb  rh|  |bh  bb|  |gh
  |gh|      |gh|      |gb|      |gb|

  |gb|      |gb|      |gh|      |gh|
bh|  |yh  yb|  |bh  bb|  |yh  yb|  |bb
  |bh|      |bh|      |rb|      |bh|

  |bb|      |bb|      |rh|      |bb|
yb|  |rb  rh|  |yb  yh|  |rh  rb|  |rb
  |bh|      |gh|      |gb|      |bh|

Solution:

  |rh|      |yb|      |bh|      |yb|
yh|  |bh  bb|  |gh  gb|  |bh  bb|  |gh
  |yh|      |rh|      |yb|      |gb|

  |yb|      |rb|      |yh|      |gh|
gh|  |yb  yh|  |bb  bh|  |rb  rh|  |yh
  |bb|      |gh|      |gb|      |gh|

  |bh|      |gb|      |gh|      |gb|
rb|  |rb  rh|  |yh  yb|  |bb  bh|  |rh
  |bb|      |rh|      |bh|      |gb|

  |bh|      |rb|      |bb|      |gh|
bh|  |gb  gh|  |yh  yb|  |rb  rh|  |rh
  |yh|      |rb|      |bh|      |yb|

Solution:

  |gh|      |yh|      |gb|      |rb|
rh|  |rh  rb|  |rb  rh|  |bh  bb|  |bh
  |yb|      |gh|      |gb|      |yb|

  |yh|      |gb|      |gh|      |yh|
bh|  |rb  rh|  |yh  yb|  |gb  gh|  |rb
  |gb|      |rh|      |bb|      |bb|

  |gh|      |rb|      |bh|      |bh|
yb|  |bb  bh|  |bb  bh|  |yb  yh|  |bh
  |bh|      |rb|      |gb|      |gb|

  |bb|      |rh|      |gh|      |gh|
rh|  |yb  yh|  |bh  bb|  |yb  yh|  |rh
  |gh|      |yh|      |yb|      |gh|

Solution:

  |rb|      |bh|      |rh|      |gh|
bb|  |bh  bb|  |yb  yh|  |bh  bb|  |yb
  |yb|      |gh|      |yh|      |yb|

  |yh|      |gb|      |yb|      |yh|
bh|  |rb  rh|  |bh  bb|  |gh  gb|  |bh
  |gb|      |gb|      |gb|      |bh|

  |gh|      |gh|      |gh|      |bb|
yh|  |rh  rb|  |rb  rh|  |rh  rb|  |rb
  |gh|      |yh|      |yb|      |bh|

  |gb|      |yb|      |yh|      |bb|
yb|  |bh  bb|  |gh  gb|  |rh  rb|  |gh
  |bh|      |rh|      |rh|      |yh|

Solution:

  |rb|      |gh|      |rh|      |bh|
bb|  |bh  bb|  |yb  yh|  |bh  bb|  |yb
  |yb|      |yb|      |yh|      |gh|

  |yh|      |yh|      |yb|      |gb|
gb|  |rh  rb|  |rb  rh|  |rh  rb|  |bh
  |rh|      |gh|      |gh|      |yh|

  |rb|      |gb|      |gb|      |yb|
yh|  |bb  bh|  |yh  yb|  |bh  bb|  |gh
  |gh|      |bh|      |bh|      |gb|

  |gb|      |bb|      |bb|      |gh|
bh|  |rh  rb|  |rb  rh|  |yb  yh|  |rh
  |gb|      |bh|      |gh|      |gh|

Solution:

  |yb|      |yb|      |bh|      |rh|
bh|  |bb  bh|  |gh  gb|  |gb  gh|  |gh
  |rb|      |bb|      |rh|      |yh|

  |rh|      |bh|      |rb|      |yb|
yb|  |gh  gb|  |bh  bb|  |bh  bb|  |gh
  |rh|      |yb|      |rb|      |rh|

  |rb|      |yh|      |rh|      |rb|
yh|  |bb  bh|  |rb  rh|  |gb  gh|  |yh
  |gh|      |gb|      |yh|      |rb|

  |gb|      |gh|      |yb|      |rh|
bh|  |yh  yb|  |gb  gh|  |yb  yh|  |bh
  |bh|      |bb|      |bb|      |yh|

Solution:

  |bh|      |rh|      |gh|      |gb|
rb|  |yb  yh|  |bh  bb|  |yh  yb|  |bh
  |bb|      |yh|      |rb|      |bh|

  |bh|      |yb|      |rh|      |bb|
bh|  |gb  gh|  |yb  yh|  |rh  rb|  |rb
  |yh|      |bb|      |gb|      |bh|

  |yb|      |bh|      |gh|      |bb|
bb|  |gh  gb|  |yh  yb|  |gb  gh|  |bh
  |rh|      |rb|      |bb|      |yb|

  |rb|      |rh|      |bh|      |yh|
gh|  |yh  yb|  |gh  gb|  |gb  gh|  |gh
  |rb|      |rh|      |rh|      |rh|

Solution:

  |bh|      |rh|      |rb|      |rb|
bb|  |yb  yh|  |bh  bb|  |bh  bb|  |bh
  |gh|      |yh|      |rb|      |yb|

  |gb|      |yb|      |rh|      |yh|
rb|  |bh  bb|  |gh  gb|  |gb  gh|  |gh
  |yh|      |gb|      |bh|      |rh|

  |yb|      |gh|      |bb|      |rb|
rh|  |rh  rb|  |rb  rh|  |yb  yh|  |bb
  |gh|      |yh|      |gh|      |gh|

  |gb|      |yb|      |gb|      |gb|
rh|  |yh  yb|  |bb  bh|  |yh  yb|  |bh
  |rh|      |gh|      |bh|      |bh|

Solution:

  |rh|      |rh|      |rb|      |rh|
gh|  |gh  gb|  |gb  gh|  |yh  yb|  |gh
  |yh|      |bh|      |rb|      |rh|

  |yb|      |bb|      |rh|      |rb|
bh|  |gh  gb|  |yb  yh|  |bh  bb|  |bh
  |bb|      |gh|      |yh|      |yb|

  |bh|      |gb|      |yb|      |yh|
rb|  |rb  rh|  |yh  yb|  |bb  bh|  |rb
  |bb|      |rh|      |gh|      |gb|

  |bh|      |rb|      |gb|      |gh|
bh|  |yb  yh|  |bb  bh|  |yh  yb|  |rh
  |gb|      |gh|      |bh|      |bb|

Solution:

  |rh|      |yh|      |gh|      |rh|
gh|  |gh  gb|  |bh  bb|  |yh  yb|  |gh
  |yh|      |bh|      |rb|      |rh|

  |yb|      |bb|      |rh|      |rb|
bh|  |gh  gb|  |yb  yh|  |bh  bb|  |bh
  |bb|      |gh|      |yh|      |yb|

  |bh|      |gb|      |yb|      |yh|
rb|  |rb  rh|  |bh  bb|  |gh  gb|  |rh
  |bb|      |gb|      |rh|      |rh|

  |bh|      |gh|      |rb|      |rb|
gb|  |bh  bb|  |yb  yh|  |gb  gh|  |yh
  |yb|      |yb|      |bh|      |rb|

Solution:

  |rh|      |yh|      |bh|      |bh|
gh|  |gh  gb|  |rh  rb|  |yb  yh|  |bh
  |yh|      |rh|      |bb|      |gb|

  |yb|      |rb|      |bh|      |gh|
gh|  |yb  yh|  |gh  gb|  |yh  yb|  |rh
  |bb|      |rb|      |rb|      |bb|

  |bh|      |rh|      |rh|      |bh|
gb|  |gb  gh|  |yb  yh|  |bh  bb|  |yb
  |rh|      |rh|      |yh|      |gh|

  |rb|      |rb|      |yb|      |gb|
yh|  |bb  bh|  |bb  bh|  |gb  gh|  |bb
  |gh|      |rb|      |bh|      |yb|

Solution:

  |gb|      |rb|      |gh|      |rh|
rh|  |bh  bb|  |bh  bb|  |yb  yh|  |bh
  |gb|      |rb|      |yb|      |yh|

  |gh|      |rh|      |yh|      |yb|
rb|  |rb  rh|  |gb  gh|  |rb  rh|  |rh
  |yh|      |yh|      |bb|      |gh|

  |yb|      |yb|      |bh|      |gb|
bh|  |bb  bh|  |gh  gb|  |yh  yb|  |bh
  |rb|      |bb|      |rb|      |bh|

  |rh|      |bh|      |rh|      |bb|
gh|  |bb  bh|  |gb  gh|  |gh  gb|  |yb
  |yb|      |yh|      |yh|      |gh|

Solution:

  |gh|      |rh|      |bh|      |rh|
bb|  |yb  yh|  |bh  bb|  |yb  yh|  |rh
  |yb|      |yh|      |gh|      |gb|

  |yh|      |yb|      |gb|      |gh|
rb|  |rb  rh|  |rh  rb|  |bh  bb|  |yh
  |gh|      |gh|      |yh|      |rb|

  |gb|      |gb|      |yb|      |rh|
bh|  |yh  yb|  |bh  bb|  |gh  gb|  |gb
  |bh|      |bh|      |gb|      |bh|

  |bb|      |bb|      |gh|      |bb|
yb|  |rb  rh|  |yb  yh|  |rh  rb|  |rb
  |bh|      |gh|      |gh|      |bh|

Solution:

  |rb|      |rh|      |rh|      |rb|
yh|  |gb  gh|  |yb  yh|  |bh  bb|  |bh
  |bh|      |rh|      |yh|      |yb|

  |bb|      |rb|      |yb|      |yh|
gh|  |bh  bb|  |bh  bb|  |gh  gb|  |bh
  |yb|      |rb|      |rh|      |bh|

  |yh|      |rh|      |rb|      |bb|
gh|  |rb  rh|  |gb  gh|  |yh  yb|  |gh
  |bb|      |yh|      |rb|      |yb|

  |bh|      |yb|      |rh|      |yh|
gb|  |bh  bb|  |gh  gb|  |gb  gh|  |gh
  |yb|      |gb|      |bh|      |rh|

Solution:

  |bh|      |yh|      |gb|      |yb|
bh|  |gb  gh|  |rb  rh|  |bh  bb|  |gh
  |yh|      |bb|      |gb|      |rh|

  |yb|      |bh|      |gh|      |rb|
bh|  |gh  gb|  |yh  yb|  |gb  gh|  |yh
  |bb|      |rb|      |bb|      |rb|

  |bh|      |rh|      |bh|      |rh|
bh|  |yb  yh|  |rh  rb|  |yb  yh|  |bh
  |gb|      |gb|      |bb|      |yh|

  |gh|      |gh|      |bh|      |yb|
bb|  |yb  yh|  |rh  rb|  |rb  rh|  |rh
  |yb|      |gh|      |bb|      |gh|

Solution:

  |bh|      |yh|      |bh|      |bb|
bh|  |gb  gh|  |gh  gb|  |yh  yb|  |gh
  |yh|      |rh|      |rb|      |yb|

  |yb|      |rb|      |rh|      |yh|
bh|  |gb  gh|  |yh  yb|  |gh  gb|  |rh
  |bh|      |rb|      |rh|      |rh|

  |bb|      |rh|      |rb|      |rb|
rh|  |yb  yh|  |bh  bb|  |bh  bb|  |bh
  |gh|      |yh|      |rb|      |yb|

  |gb|      |yb|      |rh|      |yh|
gh|  |bb  bh|  |gh  gb|  |gb  gh|  |rb
  |yb|      |bb|      |bh|      |bb|

Solution:

  |bh|      |rb|      |gh|      |rh|
yh|  |bh  bb|  |bh  bb|  |yb  yh|  |bh
  |gb|      |rb|      |yb|      |yh|

  |gh|      |rh|      |yh|      |yb|
rb|  |rb  rh|  |gb  gh|  |rb  rh|  |rh
  |yh|      |yh|      |bb|      |gh|

  |yb|      |yb|      |bh|      |gb|
bh|  |bb  bh|  |gh  gb|  |gb  gh|  |bb
  |rb|      |bb|      |rh|      |yb|

  |rh|      |bh|      |rb|      |yh|
gh|  |bb  bh|  |yb  yh|  |gb  gh|  |gh
  |yb|      |gb|      |bh|      |rh|

Solution:

  |rh|      |rb|      |gh|      |bh|
rh|  |gb  gh|  |yh  yb|  |rh  rb|  |yb
  |yh|      |rb|      |bb|      |bb|

  |yb|      |rh|      |bh|      |bh|
gh|  |yb  yh|  |bh  bb|  |yb  yh|  |bh
  |bb|      |yh|      |gh|      |gb|

  |bh|      |yb|      |gb|      |gh|
rb|  |rb  rh|  |rh  rb|  |bh  bb|  |yh
  |bb|      |gh|      |yh|      |rb|

  |bh|      |gb|      |yb|      |rh|
gb|  |gb  gh|  |bb  bh|  |gb  gh|  |gh
  |rh|      |yb|      |bh|      |yh|

Solution:

  |yb|      |rh|      |rh|      |rh|
bb|  |gh  gb|  |gb  gh|  |yb  yh|  |bh
  |rh|      |bh|      |rh|      |yh|

  |rb|      |bb|      |rb|      |yb|
yh|  |gb  gh|  |bh  bb|  |bh  bb|  |gh
  |bh|      |yb|      |yb|      |gb|

  |bb|      |yh|      |yh|      |gh|
rb|  |gh  gb|  |rh  rb|  |rb  rh|  |yh
  |yh|      |rh|      |gh|      |gh|

  |yb|      |rb|      |gb|      |gb|
yb|  |bb  bh|  |bb  bh|  |yh  yb|  |bh
  |gh|      |rb|      |bh|      |bh|

Solution:

  |rh|      |yb|      |bh|      |rh|
gh|  |bb  bh|  |gh  gb|  |yh  yb|  |gh
  |yb|      |bb|      |rb|      |rh|

  |yh|      |bh|      |rh|      |rb|
gb|  |rh  rb|  |yb  yh|  |bh  bb|  |bh
  |rh|      |bb|      |yh|      |rb|

  |rb|      |bh|      |yb|      |rh|
yh|  |gh  gb|  |bh  bb|  |gh  gb|  |gb
  |rb|      |yb|      |gb|      |bh|

  |rh|      |yh|      |gh|      |bb|
gh|  |gh  gb|  |bh  bb|  |yh  yb|  |gh
  |yh|      |bh|      |rb|      |yb|

Solution:

  |rh|      |yb|      |rb|      |rh|
gh|  |bb  bh|  |gb  gh|  |yh  yb|  |gh
  |yb|      |bh|      |rb|      |rh|

  |yh|      |bb|      |rh|      |rb|
gh|  |gh  gb|  |yb  yh|  |bh  bb|  |bh
  |rh|      |gh|      |yh|      |yb|

  |rb|      |gb|      |yb|      |yh|
yh|  |bb  bh|  |yh  yb|  |bb  bh|  |rb
  |gh|      |bh|      |gh|      |gb|

  |gb|      |bb|      |gb|      |gh|
bh|  |rh  rb|  |rb  rh|  |yh  yb|  |bb
  |gb|      |bh|      |rh|      |bh|

Solution:

  |gh|      |gb|      |bh|      |rh|
rb|  |rb  rh|  |bh  bb|  |yb  yh|  |bh
  |yh|      |gb|      |gh|      |yh|

  |yb|      |gh|      |gb|      |yb|
gh|  |yb  yh|  |rh  rb|  |bh  bb|  |gh
  |bb|      |gh|      |yh|      |rh|

  |bh|      |gb|      |yb|      |rb|
bh|  |gb  gh|  |bb  bh|  |bb  bh|  |bb
  |yh|      |yb|      |rb|      |rb|

  |yb|      |yh|      |rh|      |rh|
bh|  |gb  gh|  |rb  rh|  |gb  gh|  |yb
  |bh|      |bb|      |yh|      |rh|

Solution:

  |gh|      |rh|      |yb|      |rh|
rb|  |rb  rh|  |gb  gh|  |yb  yh|  |bh
  |yh|      |yh|      |bb|      |yh|

  |yb|      |yb|      |bh|      |yb|
bh|  |bb  bh|  |gh  gb|  |bh  bb|  |gh
  |rb|      |bb|      |yb|      |gb|

  |rh|      |bh|      |yh|      |gh|
gh|  |bb  bh|  |gb  gh|  |rb  rh|  |yh
  |yb|      |yh|      |bb|      |gh|

  |yh|      |yb|      |bh|      |gb|
bh|  |rb  rh|  |rh  rb|  |rb  rh|  |bh
  |gb|      |gh|      |bb|      |gb|

In total 23 solutions were found in 1 seconds and 26026288 iterations.

Press ENTER key to quit...

Mein Programm löst das Puzzle rekursiv, daher kann es zu Stapelüberläufen (Stackoverflows) kommen. Es empfiehlt sich daher das Heraufsetzen der maximalen Stapelgröße.

« Das ACTA-Gedicht Spambog.com Sicherheitslücke (XSS-Injection) »

Permanent Link

Tags: Affenpuzzle, Backtracking, C#, programmieren

Comments RSS feed

2 Comments:

Günther Torgat

February 26th, 2012 at 16:45

Hallöchen,
ich bin auf diesen Artikel gelandet, weil ich in meiner Logdatei diese Adresse gesehen habe. Eigentlich wollte ich wissen, wie konkret die Besucher auf meine Webseite genau gekommen sind.
Die Möglichkeit, bzw. das widerstehen einer Verlinkung nicht zu nutzen, ist bekanntlich relativ klein.
Es ist doch üblich, dass man schon aus der Neugierde heraus, Links anklickt. Da dachte ich mir klickste mal drauf und guckst wo du landest, bzw. welche Webseite man ansehen darf.
So, da ich gerade diese Seite vor mir habe, will ich sagen, das ich diese Webseite informativ finde. Meine einzige kleine Kritik ist, möglicherweise die Navigation. Eine durchdachte Benutzerführung fehlt hier stellenweise. Eventuell reicht es schon aus, wenn man die Breadcrumbleiste ein bisschen mehr hervorhebt.Wie schon gesagt, ist die Webseite ansonsten super.So da nun die Faschingszeit endlich vorbei ist, kann ich jetzt mehr lesen, da ich ja nun viel mehr Zeit habe. Darum füge ich glatt mal diese Seite in meine Favoriten mit ein. Oder, nein ich abonniere gleich den RSS Feed als Mittel der Wahl.

So genug geschrieben, ich muß jetzt ins Bett. Ich bleibe als Leser natürlich weiterhin treu.
Tschüss!

PS:Wieso erscheint der Cursor nicht in der neuen Zeile wenn ich Enter drücke?- Komisch. Ich wollte keine Wand aus Text schreiben, naja ich lasse es lieber jetzt

Reply
- admin
  
  February 26th, 2012 at 17:02
  
  Hallo,
  
  vielen Dank für den netten Eintrag.
  Ich nehme an, in der Logdatei stehen die Referer-Header der Besucher, also die URL von wo aus diese auf Ihre Seite verwiesen wurden.
  Der Blog ist eigentlich auch nicht die Hauptseite meiner Homepage, daher achte ich hier nicht zu sehr auf die Menüführung. Die Hauptseite ist unter http://robofan.de verfügbar.
  Im Firefox kann ich übrigens einwandfrei neue Zeilen mit der Enter-Taste einfügen, das wird wohl ein Browserproblem sein.
  
  MfG
  Birk B.
  
  Reply

Software Programming Blog

2 Comments:

Leave a Reply Cancel reply

YouTube Gadget

Recent Posts

Advert

Friends & links

Pages

Monthly archives

Software Programming Blog

2 Comments:

Leave a Reply Cancel reply

YouTube Gadget

Recent Posts

Popular Tags

Advert

Friends & links

Pages

Monthly archives