Das Affenpuzzle-Problem

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: B. 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 B. 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 B. 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.