/*******************************************************************/
/** PROBLEME DES N 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>
#include <time.h>
#include <dos.h>
#include <conio.h>

int NBREINES;         /* Nombre de reines */
int reine[50];        /* Tableau des reines pour chaque colonne */

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


/*****************************************************/
/** 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] > NBREINES)
		{
			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 **/
	long int nbr_solutions = 0;  /** compteur incr‚ment‚ … chaque solution   **/
	int i;
	clock_t start,end;

	do
	{
		clrscr();
		printf("\n\n      SOLUTIONS AU PROBLEME DES N REINES SUR UN ECHIQUIER DE N x N");
		printf("\n\nCombien de reines ?");
		scanf("%d", &NBREINES);
	}
	while ((NBREINES > 50) || (NBREINES < 4));

	start=clock();
	clrscr();
	for (i=0 ; i<NBREINES ; i++)
		reine[i] = 0;

	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 < NBREINES-1) /** 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 **/
				printf("%ld ",nbr_solutions);
				for (i=0 ; i<NBREINES ; i++)
					printf(" %d",reine[i]);
				printf("\n");
			}
		}
		else                          /** si on n'a pas pu placer la reine **/
			colonne--;                /** de colonne en cours, on revient  **/
	}while (reine[0] != 0);

	end=clock();

	gotoxy(45,20);
	printf("Il y a %ld solutions \n",nbr_solutions);
	gotoxy(45,21);
	printf("au problŠme des %d reines.",NBREINES);
	gotoxy(45,22);
	printf("TEMPS : %ld\n",end-start);
}