reines.c

For the incomplete methods, we kept the representation of the queens by a table and the method of ca

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

int temps_mis;

int nbReines = 0;
int nbSolution = 0;
int *place;//emplacement de la reine sur la ligne
int *enConflit;
int **echiquier;
char reponse = 'n';
int r1,r2,nbConflits,minConflits;

void afficherDansFic2(int nbElem, int **matrix){
	FILE *placement;
	int i,j,k;
	int ligneNOK = 1;
	
	placement=fopen("placement.txt","w");
	for(i=0;i<nbElem;i++){
		for(j=0;j<nbElem;j++){
			if(matrix[i][j] == 2){
				fprintf(placement,"R");
				ligneNOK = ligneNOK && 0;
			}
			else fprintf(placement,"%d",matrix[i][j]);
		}
		fprintf(placement,"\n");
		ligneNOK = 1;
	}
	fprintf(placement,"\n\n%d reines plac閑s avec succ鑣.\n",nbElem);
	fclose(placement);
	
}

void affTexte(int nbElem, int **matrix){
	int i,j,k;
	char temp;
	
	for(i=0;i<nbElem;i++){
		for(j=0;j<nbElem;j++){
			if(matrix[i][j] == 2) printf("R");
			else printf("%d",matrix[i][j]);
		}
		printf("\n");
	}
	//printf("Appuyer sur une touche pour continuer...\n");
	scanf("%c",&temp);
}

int bienPlacee(int **matrix, int x, int y, int nbReines){//fonction booleenne
	int i;
	for(i=0;i<nbReines;i++) if((matrix[i][y] == 2)||(matrix[x][i] == 2)) return 0;
	i=0;
	while(((x-i)>=0)&&((y-i)>=0)){
		if(matrix[x-i][y-i] == 2) return 0;
		i++;
	}
	i=0;
	while(((x+i)<nbReines)&&((y+i)<nbReines)){
		if(matrix[x+i][y+i] == 2) return 0;
		i++;
	}
	i=0;
	while(((x+i)<nbReines)&&((y-i)>=0)){
		if(matrix[x+i][y-i] == 2) return 0;
		i++;
	}
	i=0;
	while(((x-i)>=0)&&((y+i)<nbReines)){
		if(matrix[x-i][y+i] == 2) return 0;
		i++;
	}
	return 1;
}

int verifPlacement(int **matrix, int nbReines){
	int i,j;
	int compt = 0;
	for(i=0;i<nbReines;i++){
		for(j=0;j<nbReines;j++){
			if(matrix[i][j] == 2){
				matrix[i][j] = 0;
				if(!bienPlacee(matrix,i,j,nbReines)) return 0;
				matrix[i][j] = 2;
				compt++;
			}
		}
	}
	return (compt == nbReines);
}



int conflit(int i1, int j1, int i2, int j2){//booleen
	return (i1 == i2) || (j1 == j2) || ((abs(i1-i2)) == (abs(j1-j2)));
}

int estEnConflit(int n){//indique si la reine n est en conflit avec une autre reine
	int res = 0;
	int j=0;
	while((j<nbReines)&&(!res)){
		if((conflit(n,place[n],j,place[j]))&&(n != j)) res = 1;
		j++;
	}
	return res;
}

int testInversion(int n1, int n2, int compar){//indique si l'inversion de n1 et n2 diminue le nombre de conflits
	int res = nbConflits;
	int k;
	if(conflit(n1,place[n1],n2,place[n2])) res--;
	if(conflit(n1,place[n2],n2,place[n1])) res++;
	for(k=0; k<nbReines; k++){
		if((k!=n1)&&(k!=n2)&&(conflit(n1,place[n1],k,place[k]))) res--;
		if((k!=n1)&&(k!=n2)&&(conflit(n1,place[n2],k,place[k]))) res++;
		if((k!=n2)&&(k!=n1)&&(conflit(n2,place[n2],k,place[k]))) res--;
		if((k!=n2)&&(k!=n1)&&(conflit(n2,place[n1],k,place[k]))) res++;
	}
	return (res<compar);
}

int inverse(int n1, int n2, int ancien_nombre){//inverse et renvoie le nouveau nombre de conflits
	int res = ancien_nombre;
	int k;
	if(conflit(n1,place[n1],n2,place[n2])) res--;
	if(conflit(n1,place[n2],n2,place[n1])) res++;
	for(k=0; k<nbReines; k++){
		if((k!=n1)&&(k!=n2)&&(conflit(n1,place[n1],k,place[k]))) res--;
		if((k!=n1)&&(k!=n2)&&(conflit(n1,place[n2],k,place[k]))) res++;
		if((k!=n2)&&(k!=n1)&&(conflit(n2,place[n2],k,place[k]))) res--;
		if((k!=n2)&&(k!=n1)&&(conflit(n2,place[n1],k,place[k]))) res++;
	}
	k = place[n2];
	place[n2] = place[n1];
	place[n1] = k;
	return res;
}

int compatible(int i, int j){
	int k;
	int comp;//booleen
	
	comp = 1;
	k = 0;
	while(comp && (k<i)){
		comp = !conflit(i,j,k,place[k]);
		k = k+1;
	}
	return comp;
}

int nbDeConflits(){
	int i,j;
	int res = 0;
	for(i=0; i<nbReines; i++){
		for(j=i; j<nbReines; j++){
			if((i!=j)&&(conflit(i,place[i],j,place[j]))) res++;
		}
	}
	return res;
}

void maxConflit(){ //affecte r1 et r2 aux reines dont la permutation minimise le plus les conflits
	int tempi,tempj,temp2,i,j;
	int minConflits;
	r1 = 0;
	r2 = 0;
	minConflits = nbConflits;
	for(i=0; i<nbReines; i++){
		for(j=i; j<nbReines; j++){
			if(i!=j){
				tempi = place[i];
				tempj = place[j];
				temp2 = inverse(i,j,nbConflits);
				place[i] = tempi;
				place[j] = tempj;
				if(temp2 < minConflits){
					r1 = i;
					r2 = j;
					minConflits = temp2;
				}
			}
		}
	}
}


int main(int argc,char *argv[]){

int i,j,k;
int temper;
int* colDispo;
time_t t1,t2;
int nbIterations = 0;

printf("Combien de Reines desirez-vous placer ? ");
scanf("%d",&nbReines);
scanf("%c",&reponse);

t1 = time(NULL);

echiquier=(int**)calloc(nbReines,sizeof(int*));
place=(int*)calloc(nbReines,sizeof(int));
enConflit=(int*)calloc(nbReines,sizeof(int));
colDispo=(int*)calloc(nbReines,sizeof(int));

for(i=0;i<nbReines;i++){
	echiquier[i]=(int*)calloc(nbReines,sizeof(int));
	colDispo[i] = 1;
}

srand(getpid());

for(i=0;i<nbReines;i++){
	k = rand();
	k = (k%nbReines);
	while(!colDispo[k]){
		k = rand();
		k = (k%nbReines);
	}
	colDispo[k] = 0;
	place[i] = k;
	enConflit[i] = 1;
}


nbConflits = nbDeConflits();
temper = 0;
while(nbConflits > 0){
	printf("%d conflits\n",nbConflits);
	r1 = 0;
	while(!enConflit[r1]) r1++;
	r2 = rand();
	r2 = (r2%nbReines);
	k=0;
	while((r1 == r2)||(!testInversion(r1,r2,nbConflits+temper))){
		r2 = rand();
		r2 = (r2%nbReines);
		k++;
		if(k == nbReines){//trop de difficult