#include <stdio.h>
int anzrota (int);
static int karte[9][4];              /* Es gibt neun Karten mit jeweils 4 Kanten, */
static int feld [9][2];			  /*	Auf jedem der Felder liegt *eine* Karte und sie ist rotiert */ 
static int rota [4];			  /* rota ist das übergabefeld zwischen anzrota und prob */				  
int prob(int);
int main()
{
	int i;
	einlesen();
	auflegen();
	prob(0);
}


int prob(int a){
	int lage[4];
	int w,i;
	if (a==9) {
		printf ("Lösung: \n");
		feld_ausgeben();
		return;
	}
	do {
		w=anzrota(a);
		for (i=0;i<w;i++) lage[i]=rota[i];
		for (i=0;i<w;i++){                          /* mache die schleife w mal */
			feld [a][1]=lage[i];
			prob (a+1);
		}
	} while (neubesetzen_von_stelle(a));
}

anzrota (int a){          /* rotieren von Karte a bis es passt und zurückgeben, wie oft es passt */			
	int b=0,c=0,i,temp;
	int q=0;
	temp=feld[a][1];
	for (i=0;i<4;i++){
		feld [a][1]=i;
		if (passt(a)){
			rota[c++]=i;
		}
	}
	feld[a][1]=temp;
	return(c);
}
	
	
auflegen()               /* anfänglicher init von feld[][]  */ 
{
	int i;
	for (i=0;i<9;i++)
	{
		feld[i][0]=i;
		feld[i][1]=0;
	}
}

feld_ausgeben()    /* AUSGABE DER KARTEN WIE SIE GERADE LIEGEN */
{
	int i,j; 
	for (i=0;i<7;i+=3)
	{
		for (j=i;(j<(i+3));j++)
			printf (" %d  ",karte [feld [j] [0] ]  [feld [j] [1] ]); 
		printf ("\n");
		for (j=i;j<(i+3);j++)
			printf ("%d%d%d ",karte [feld[j][0]] [((feld[j][1]+3)%4)],\
						   feld[j][0],\
						   karte [feld[j][0]] [((feld[j][1]+1)%4)]);
		printf ("\n");
		for (j=i;j<(i+3);j++)
			printf (" %d  ",karte[feld[j][0]][((feld[j][1]+2)%4)]);
		printf ("\n");
	}
	printf ("\n");
	printf ("\n");
}



ausgeben()
{
	int i,j,k;
	printf ("\n -------- AUSGABE DER KARTEN WIE SIE EINGELESEN WURDEN -------- \n");
	for (i=0;i<9;i++)
	{
		for (j=0;j<4;j++)
			printf ("%d  ",karte[i][j]);
		printf (" das war Karte %d\n",i);
	}
	printf ("\n");
}


einlesen()
{
	FILE *datenfile;
	int i,j,erfolg=0;
	char c;
	if ((datenfile=fopen("karten","r"))==NULL) 
	{	fprintf (stderr, "Datei wurde nicht gefunden.\n");
		exit (1);
	};
	for (i=0;i<9;i++)
		for (j=0;j<4;j++) 
		do
		{
			c=getc(datenfile);
			if (c==EOF)              /*       SCHON AUS?      */
			{
				fprintf (stderr, "Datei war frühzeitig zu Ende - bitte prüfen!\n");
				exit (1);
			}
			if ((c<'0')||(c>'9'))
				erfolg=0;
			else
			{
				erfolg=1;
				karte[i][j]=c-48;
			}
		} while (erfolg==0);
}
	
neubesetzen_von_stelle(int a)      /* besetzt feld[a] neu und sortiert den rest */ 
{							/* gibt zurück, ob es ging */
	int b,i=0,n;
	int stellevon_neukarte,neue_karte;
	if ((a<8)&&(a>=0)){          	/* Es kann vielleicht neubesetzt werden */
		do {
			neue_karte=feld[a][0]+(++i);		/* Es gibt mehrere Möglichkeiten: karte[n] ist geschützt */
			if (neue_karte>8) return (0);		/* wenns nicht geht, gib "nicht möglich" zurück 		*/
			stellevon_neukarte=stelle_von (neue_karte);
		} while (stellevon_neukarte<a); 
		tausche (stellevon_neukarte,a);	/* bis incl stelle a liegen alle richtig, die Nachkommen fehlen noch */
		for (i=a+1;i<8;i++){
			feld [i][1]=0;
			b=ortvon_kleinster(i);
			if (!(b==i)) tausche (b,i);
		}
		return (1);
	}
	else return (0);
}	

stelle_von(int s)    /* getestet - funkt! */
{
	int l=0;                               /* ein hässlicher suchalgorithmus */
	while (!(feld[l][0]==s)) l++;
	return (l);
}

tausche(int a,int b)      /* lässt rotationen aber wie sie sind */
{
	int c;
	c=feld[a][0];
	feld[a][0]=feld[b][0];
	feld[b][0]=c;
}

ortvon_kleinster(int i)     /* Ab Stelle i!!! */
{
	int a,b=8,c,platz=8;
	for (a=i;a<9;a++) {
		c=feld[a][0];
		if (c<b) {
			b=c;
			platz=a;
		}
	}
	return (platz);
}

passt (int a){                      /*   Prüft, ob das, was auf feld[a] liegt, passt. */
	int oberkante,unterkante,linkskante,rechtskante;
	if ((a==3)||(a==6)){
		oberkante=karte[feld[a][0]][feld[a][1]];
		a-=3;
		unterkante=karte[feld[a][0]][(feld[a][1]+2)%4];
		return ((oberkante+unterkante)==10);
	} else if ((a==1)||(a==2)){
		linkskante=karte[feld[a][0]][(feld[a][1]+3)%4];
		--a;
		rechtskante=karte[feld[a][0]][(feld[a][1]+1)%4];
		return ((linkskante+rechtskante)==10);
	} else if ((a>3) && (a<9)){                           /* a ist nicht: 3,6,1,2,0 aber vielleicht 4,5,7,8 */
		oberkante=karte[feld[a][0]][feld[a][1]];
		linkskante=karte[feld[a][0]][(feld[a][1]+3)%4];
		--a;
		rechtskante=karte[feld[a][0]][(feld[a][1]+1)%4];
		a-=2;
		unterkante=karte[feld[a][0]][(feld[a][1]+2)%4];
		return (((linkskante+rechtskante)==10)&&((oberkante+unterkante)==10));
	}
	else if (a==0) return 1;
}