PROBLÈME DE N DAMES

/*******************************************************************/
/***                     probléme de n-dames                     ***/
/***                       crée par blackbird                   ***/
//Le but du problème des n dames (parfois appelé à tort problème
//des huit reines), est de placer huit dames d'un jeu 
//d'échecs sur un échiquier de n×n cases 
//sans que les dames ne puissent se menacer mutuellement, conformément 
//aux règles du jeu d'échecs (la couleur des pièces étant ignorée.) 
//Par conséquent, deux dames ne devraient
//jamais partager la même rangée, colonne, ou diagonale
/*******************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <windows.h>
#define vrai 1
#define faux 0

FILE *Fichier;
int **Damier;
char Buf[1];


void Affiche (int Dim ) {
	int ParcourLigne,ParcourColonne;
	for (ParcourLigne=0;ParcourLigne<Dim;ParcourLigne++)
	{
		for (ParcourColonne=0;ParcourColonne<Dim;ParcourColonne++) {
			_itoa(Damier[ParcourLigne][ParcourColonne],Buf,10);
			fputs(Buf,Fichier);
			fputs("\t",Fichier);
			printf("%d\t",Damier[ParcourLigne][ParcourColonne]);
		}
		fputs("\n",Fichier);
		printf("\n");
	}
}

void Init(int Dim) {
	int ParcourLigne,ParcourColonne;
	for (ParcourLigne=0;ParcourLigne<Dim;ParcourLigne++)
	 for(ParcourColonne=0;ParcourColonne<Dim;ParcourColonne++)
		Damier[ParcourLigne][ParcourColonne] = 0;
}
//
//fonction qui vérifie si on peut poser une dame à la
//position Ligne,Colonne en regardant les colonnes vers la
//gauche.
//
int PeutPoser(int Ligne, int Colonne,int Dim){
	
	int ParcourLigne,ParcourColonne,ok; 
	ok = vrai;
	
	ParcourColonne=Colonne-1;
	ParcourLigne=Ligne;
	while(ParcourColonne>=0 && ok) {
			if (Damier[ParcourLigne][ParcourColonne]) ok= faux;
			ParcourColonne--;
	}

	ParcourLigne=Ligne-1;
	ParcourColonne=Colonne-1;
	while(ParcourLigne>=0 && ParcourColonne>=0 && ok) {
		if (Damier[ParcourLigne][ParcourColonne]) ok = faux;
		ParcourLigne--;
		ParcourColonne--;
	}

	ParcourLigne=Ligne+1;
	ParcourColonne=Colonne-1;
	while(ParcourLigne<Dim && ParcourColonne>=0 && ok) {
		if (Damier[ParcourLigne][ParcourColonne]) ok = faux;
		ParcourLigne++;
		ParcourColonne--;
	}

		

return ok;
}
//

//
//fonction qui essaye mettre une dame dans la colonne "Colonne"
//si on peut on passe au colonne suivant par appel recusive, sinon
//on cherche une position dans la colonne précédente.
//lorsque on pose une dame dans une case, on teste toutes les 
//possibilités dans la colonne suivante
//
int Positionner(int Colonne, int Dim){ 
	int ParcourLigne,NbreSolutions=0;

	if (Colonne==Dim ) {
		            Affiche(Dim);
	                printf("\n");
					fputs("\n",Fichier);
					return 1;
	} 

	//
    //Mettre la dame dans une ligne du colonne
	//
	for (ParcourLigne=0;ParcourLigne<Dim;ParcourLigne++)     
		if (PeutPoser(ParcourLigne,Colonne,Dim)) 
        {   
			Damier[ParcourLigne][Colonne]=vrai;
            NbreSolutions+=Positionner(Colonne+1,Dim);
			Damier[ParcourLigne][Colonne]=faux;
         }  
	

return NbreSolutions;
}

//

int main(){ 
	    int TailleDamier,AllocLigne, NbreSolutions = 0;
		int Rep;

		LARGE_INTEGER Debut,Fin,Frequence;
		double Duree;

			printf("********************************Probl%cme de n-dame******************************\n\n\n",138);

		printf("Donner la dimension du damier \n");
		scanf("%d",&TailleDamier);
		
		//
		//allocation dynamique
		//
        Damier = malloc(TailleDamier*sizeof(int*));
		if (Damier == NULL) {
		printf("ERREUR allocation mémoire%c !!!\n",130);
		exit(EXIT_FAILURE);
	}
	else {
		for (AllocLigne = 0;AllocLigne<TailleDamier;AllocLigne++) {
			Damier[AllocLigne] =malloc(TailleDamier*sizeof(int));
			if (Damier[AllocLigne] == NULL) {
				printf("ERREUR allocation mémoire%c !!!\n",130);
				exit(EXIT_FAILURE);
			}
		}
	
	
	  
		QueryPerformanceFrequency(&Frequence);
		QueryPerformanceCounter(&Debut);

	
		if( (Fichier = fopen( "Solutions.txt", "w+" )) != NULL )
        {
		printf( "Fichier ouvert...\n");
		
		Init(TailleDamier);  
		
		//
		//on commence par la colonne 0
		//
		NbreSolutions = Positionner(0,TailleDamier);
		///
		
		_itoa(NbreSolutions,Buf,10);
		fputs(Buf,Fichier);
		fputs(" Solutions\n",Fichier);
		printf("%d solutions\n",NbreSolutions);
		
        
		printf("Vous trouvez les solutions dans le fichier 'Solutions.txt' \n");
		printf("0 --> position vide \n");
		printf("1 --> position occup%ce par une dame \n",130);
		fputs("0 --> position vide \n",Fichier);
		fputs("1 --> position occupée par une dame \n\n",Fichier);

		QueryPerformanceCounter(&Fin);
		Duree = 1000.0 * (Fin.QuadPart-Debut.QuadPart)/Frequence.QuadPart;
		printf("\nEx%ccut%c en %0.3f secondes.\n",130,130,Duree/1000);
		
		}
		else
			printf( "Erreur d'ouverture du fichier \n");

		fclose(Fichier);

		//
	    //Désalloaction mémoire
		//
    	for (AllocLigne = 0;AllocLigne<TailleDamier;AllocLigne++)
			free(Damier[AllocLigne]);
		free(Damier);
		//
	}
	   printf("\n\nTaper sur Entr%ce pour continuer.\nTaper sur une autre pour quitter\n\n\n",130);
       Rep = _getch();
	   if (__toascii(Rep) == 13)  {system("cls");main();}
	   else exit(EXIT_SUCCESS);
	   
	
}