// problŠme des huit reines



#include <conio.h>         

#include <stdio.h>

#include <time.h>



typedef int bool;



typedef struct {

	int nb_reines;

	int reineligne[8];

	bool reinecol[8];

	bool reinediagp[15];

	bool reinediags[15];

} Echiquier;



void afficher (Echiquier *echiq)

{

int i;

static n=1;



	printf ("\n----------%d\t",n++);

	for (i=0; i<8; i++)

		printf ("%d-%d ", i+1, echiq->reineligne[i]);

}



bool case_ok (Echiquier *echiq, int ligne, int col)

{

int diagp, diags;



	diagp = ligne + col - 2;

	diags = col - ligne + 7;

	return echiq->reinecol[col-1] && echiq->reinediagp[diagp]

		&& echiq->reinediags[diags];

}



void ajouter_reine (Echiquier *echiq, int ligne, int col)

{

	echiq->nb_reines++;

	echiq->reineligne[ligne-1] = col;

	echiq->reinecol[col-1] = 0;

	echiq->reinediagp[ligne + col - 2] = 0;

	echiq->reinediags[col - ligne + 7] = 0;

}



void retirer_reine (Echiquier *echiq)

{

int i;



	echiq->nb_reines--;

	for (i = 0; i < 8; i++)

		echiq->reinecol[i] = 1;

	for (i = 0; i < 15; i++)

		echiq->reinediags[i] = echiq->reinediagp[i] = 1;

	for (i = 0; i < echiq->nb_reines; i++) {

		echiq->reinecol[ echiq->reineligne[i] - 1] = 0;

		echiq->reinediagp [ i + echiq->reineligne[i] -1 ] = 0;

		echiq->reinediags [ echiq->reineligne[i] - i + 6 ] = 0;

	}

}











void pb_reines (Echiquier *echiq)

{

int ligne,col;



	if (echiq->nb_reines == 8)

		afficher (echiq);

	else {

		ligne = echiq->nb_reines +1;

		for (col = 1 ; col <= 8; col++)

			if (case_ok (echiq, ligne, col)) {

				ajouter_reine (echiq, ligne, col);

				pb_reines (echiq);

				retirer_reine (echiq);

			}

	}

}



main ()

{

Echiquier echiquier = {0, {0, 0, 0, 0, 0, 0, 0, 0},

							{1, 1, 1, 1, 1, 1, 1, 1},

							{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},

							{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};



time_t t1,t2;



	t1 = time(NULL);

	pb_reines (&echiquier);

	t2 = time(NULL);

	printf ("temps = %f", difftime(t2,t1));

	return 0;

}