// nikohaus.c -- Sourcecode under GPL, author: RTC @ 2004		//
// Programm setzt das "Haus-des-Nikolaus"-Problem algorithmisch mit	//
// einer Adjazenzmatrix um und gibt die Möglichkeiten aus, wieviel mal  //
// das Haus von jeder seiner Ecken ausgehend aufgebaut werden kann	//

#include <stdio.h>
#include <stdlib.h>

//--- globale Deklarationen ----------------------------------------------
typedef enum {false=0,true=1} bool;
int zaehl[10];//speichert die Konstruktionsmöglichkeiten ab

//--- rek. Fkt. zum Berechnen und zur Ausgabe der Moeglichkeiten ---------
void haus_rek(bool mtrx[5][5], const int start, const int kn, const int count, char *weg){
	int i; char *weg_neu=(char *)malloc(100*sizeof(char));
	for(i=0;i<5;i++){//eine Matrix-Zeile durchgehen
		if(mtrx[kn][i]==1){//wenn mit anderer Zeile verbunden...
			sprintf(weg_neu, "%s->%d",weg,i);
			if(count==7){//Haus komplett errichtet
				zaehl[start]++; //Moeglichkeiten hochzaehlen
				if(start==0)
					printf("%2d: %s\n",zaehl[start],weg_neu);
				return;
			}
			mtrx[kn][i]=0; mtrx[i][kn]=0; //diese Wege streichen
			haus_rek(mtrx,start,i,count+1,weg_neu); //naechster Knoten
			mtrx[kn][i]=1; mtrx[i][kn]=1; //Wege wieder herstellen
		}
	}
	zaehl[start+5]++; //Nicht-Moeglichkeiten hochzaehlen
	free(weg_neu);
}

//--- main() ------------------------------------------------------------
int main(void){
	bool mtrx[5][5]={{0,1,1,1,0},//Adjazenzmatrix des "Haus' vom Nikolaus"
			 {1,0,1,1,0},
			 {1,1,0,1,1},
			 {1,1,1,0,1},
			 {0,0,1,1,0} };
	int i; char *weg=(char *)malloc(100*sizeof(char)); //weg speichert den Weg
	for(i=0; i<10; i++) //Zaehler auf 0 setzen
		zaehl[i]=0;

	printf("Konstruktionsmoeglichkeiten vom Knoten 0 aus:\n");
	for(i=0; i<5; i++){//alle Knoten einmal als Anfangsknoten
		sprintf(weg,"%d",i);
		haus_rek(mtrx,i,i,0,weg);
	}
	free(weg);

	for(i=0; i<5; i++)
		printf("-> Von Knoten %d aus gibt es %d Moeglichkeiten, %d Sackgassen.\n",i,zaehl[i],zaehl[i+5]);

	return 0;
}