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 nbReines = 0;
int nbSolution = 0;
int *place;//emplacement de la reine sur la ligne
int **echiquier;
char reponse = 'n';
int temps_mis;
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++;
	}
	//printf("Comparaison reines %d et %d :\n",n1,n2);
	//printf("res = %d ; ancien_nombre = %d\n",res,ancien_nombre);
	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;
	//int nbConflits_old = nbConflits;
	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){
					//printf("minConflits : %d - temp2 : %d\n",minConflits,temp2);
					r1 = i;
					r2 = j;
					minConflits = temp2;
				}
			}
		}
	}
}


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

int i,j,k;
time_t t1,t2;
int temper;
int solutOK;//booleen
int alea,new_nbConf,delta;
int* colDispo;
int nbConflits_debut;
int compt;
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));
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;
}


nbConflits = nbDeConflits();
nbConflits_debut = nbConflits;
temper = 0;
solutOK = 1;//pr l'affichage du nb de conflits au d閜art
while(nbConflits > 0){
	if(solutOK) printf("%d conflits\n",nbConflits);

	solutOK = 0;
	while(!solutOK){
		r1 = rand();
		r1 = r1%nbReines;
		r2 = rand();
		r2 = r2%nbReines;
		i = place[r1];
		j = place[r2];
		new_nbConf = inverse(r1,r2,nbConflits);
		delta = new_nbConf - nbConflits;
		if(delta < 0) solutOK = 1;
		else{
		        place[r1] = i;
			place[r2] = j;
			compt++;
			if(compt ==  nbReines){
				r1=0;
				while(!estEnConflit(r1)) r1++;
				r2 = 0;
				compt = 0;
				k = 0;
				while((r1 == r2)||(!testInversion(r1,r2,nbConflits+k))){
					r2 = rand();
					r2 = (r2%nbReines);
					compt++;
					if(compt == nbReines){
						k++;
						compt = 0;
					}
				}
				new_nbConf = inverse(r1,r2,nbConflits);
				solutOK = 1;
			 }
		}
		if(!solutOK){
			place[r1] = i;
			place[r2] = j;
		}
	}
	nbConflits = new_nbConf;
	compt = 0;
	
	nbIterations++;
}

if(nbConflits == 0) printf("\nplacement reussi.\n");
else printf("\n%d conflits restants.\n",nbConflits);
for(i=0; i<nbReines; i++){
	for(j=0; j<nbReines; j++){
		if(place[i] == j) echiquier[i][j] = 2;
		else echiquier[i][j] = 0;
	}
}

t2 = time(NULL);

temps_mis = (int) (t2 - t1);
printf("temps mis : %d minutes %d secondes\n",(temps_mis/60),(temps_mis%60));

printf("nombre d'iterations : %d\n",nbIterations);


printf("demarrage verification\n");
if(!verifPlacement(echiquier,nbReines)) printf("Placement erron