/*******************************************************************/
/** PROBLEME DES HUIT REINES ** 9 MARS 1994 ** 22 H 54 Min 17 Sec **/
/*******************************************************************/
/** Programm‚ en Turbo C++ v1.00 de BORLAND International Inc. *****/
/*******************************************************************/
/** Sujet : Combien y a-t-il de maniŠres diff‚rentes de placer *****/
/*********  huit reines sur un ‚chiquier (8 cases sur 8), sans *****/
/*********  qu'elles puissent se prendre l'une l'autre ???     *****/
/*********  (les reines prennent lat‚ralement et en diagonale) *****/
/*******************************************************************/

#include <stdio.h>

int reine[8]={0,0,0,0,0,0,0,0}; /* Tableau des reines pour chaque colonne */

/*************************************/
/** Prototypes des fonctions cr‚‚es **/
/*************************************/
void affichage(int);  /** Fonction visualisation des solutions … l'‚cran **/
int nonprenable(int); /** Fonction d‚terminant si une reine est imprenable **/
void placer(int);     /** Fonction pla‡ant une reine sur l'‚chiquier **/


/*******************************************************/
/** Fonction de visualisation des solutions … l'‚cran **/
/*******************************************************/
void affichage(solution)
{
	int i;      /** compteur de boucle **/

	clrscr();
	/************************/
	/** Affichage du titre **/
	/************************/
	gotoxy(30,1);
	printf("PROBLEME DES HUIT REINES\n");
	gotoxy(30,2);
	printf("ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\n");
	gotoxy(25,3);
	printf("(c) S‚bastien PISSAVY - Mars 1994");

	/*************************************************/
	/** Affichage du num‚ro de la solution en cours **/
	/*************************************************/
	gotoxy(46,12);
	printf("Solution Nø%d",solution);
	gotoxy(46,13);
	printf("ÄÄÄÄÄÄÄÄÄÄÄÄÄ");

	/******************************************************/
	/** Affichage de la solution en notation ensembliste **/
	/******************************************************/
	gotoxy(45,15);
	printf(" S = { ");
	for (i=0 ; i<8 ; i++)
		printf("%d ",reine[i]);
	printf("}\n");

	/******************************/
	/** Affichage de l'‚chiquier **/
	/******************************/
	gotoxy(1,7);
	printf("   0   1   2   3   4   5   6   7  \n");
	printf(" ÚÄÄÄÂÄÄÄÂÄÄÄÂÄÄÄÂÄÄÄÂÄÄÄÂÄÄÄÂÄÄÄ¿\n");
	printf("1³   ³   ³   ³   ³   ³   ³   ³   ³\n");
	for (i=0 ; i<7 ; i++)
	{
		printf(" ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´\n");
		printf("%d³   ³   ³   ³   ³   ³   ³   ³   ³\n",i+2);
	}
	printf(" ÀÄÄÄÁÄÄÄÁÄÄÄÁÄÄÄÁÄÄÄÁÄÄÄÁÄÄÄÁÄÄÄÙ\n");

	/**************************/
	/** Affichage des reines **/
	/**************************/
	for (i=0 ; i<8 ; i++)
	{
		gotoxy(((i+1)*4), 7+reine[i]*2);
		printf("Û");
	}
	sleep(1);
}


/*****************************************************/
/** Fonction v‚rifiant si une reine est en position **/
/** de prendre ou d'ˆtre prise pas une autre reine  **/
/** (plac‚e sur sa gauche sur l'‚chiquier (< num))  **/
/** Entr‚e : num‚ro de la reine de 0 … 7            **/
/** Sortie : 0 si emplacement prenable              **/
/**          1 si emplacement non prenable          **/
/*****************************************************/
int nonprenable(num)
{
	int i;  /** compteur de boucle **/

	if (num > 0)
	{
		for (i=0 ; i<num ; i++)
		{
			if ((reine[i]==reine[num]) || (reine[i]==reine[num]+num-i) || (reine[i]==reine[num]-num+i))
			{
				return(0);   /** la reine peut prendre ou ˆtre prise **/
			}
		}
	}
	return(1);   /** la reine est non prenable **/
}


/************************************************/
/** Fonction pla‡ant une reine sur l'‚chiquier **/
/** Entr‚e : num‚ro de la reine de 0 … 7       **/
/** Sortie : N‚ant                             **/
/************************************************/
void placer(num)
{
	int etat = 0;           /** si etat == 1, la reine n'est pas prenable **/
	int nonplacable = 0;    /** si nonplacable == 1, pas de solution **/

	while ((nonplacable == 0) && (etat == 0))
	{
		reine[num]++;
		if (reine[num] > 8)
		{
			reine[num] = 0;
			nonplacable = 1;
		}
		else
		{
			etat = nonprenable(num);
		}
	}
}


/*****************************************************/
/** Programme principal g‚rant le "commit-rollback" **/
/*****************************************************/
void main(void)
{
	int colonne = 0;           /** 0<=colonne<=7 -> colonne de l'‚chiquier **/
	int nbr_solutions = 0;     /** compteur incr‚ment‚ … chaque solution   **/

	do            /** Tant qu'on n'a pas ‚puis‚ toutes les solutions... **/
	{
		placer(colonne);              /** on place la reine de la colonne **/

		if (reine[colonne] != 0)      /** si on a pu placer la reine de la **/
		{                             /** colonne en cours, alors.. **/
			if (colonne < 7)          /** si on n'est pas derniŠre colonne **/
				colonne++;            /** on passe … la colonne suivante **/
			else
			{                         /** on a plac‚ la derniŠre colonne **/
				nbr_solutions++;      /** donc on a une solution **/
				affichage(nbr_solutions);
			}
		}
		else                          /** si on n'a pas pu placer la reine **/
			colonne--;                /** de colonne en cours, on revient  **/
	}while (reine[0] != 0);

	gotoxy(45,20);
	printf("Il y a %d solutions \n",nbr_solutions);
	gotoxy(45,21);
	printf("au problŠme des huit reines.");
}