Le problème des 8 dames (14 cavaliers, ...)

Commenter

Contenu du snippet

Le problème des 8 dames consiste à trouver comment placer 8 dames sur un échiquier classique (8*8) de telle sorte qu'aucune ne puisse prendre les autres...

J'ai trouvé ce problème sur wikipedia, mon programme comptes les solutions, mais peut aussi bien les afficher, suffit de le lui demander...

Source / Exemple : 


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

typedef struct {
	int x, y;
} cases;

typedef struct {
	char c[8][8];
} echiquier;

int myabs(int a){
	return (a>=0)?a:-a;
}

int damesCanGo(cases a, cases b){
	if (a.x==b.x || a.y==b.y){
		return 1;
	}else if (myabs(a.x-b.x) == myabs(a.y-b.y)){
		return 1;
	}else{
		return 0;
	}
}
int fousCanGo(cases a, cases b){
	if (myabs(a.x-b.x) == myabs(a.y-b.y)){
		return 1;
	}else{
		return 0;
	}
}
int cavaliersCanGo(cases a, cases b){
	int c, d;
	c=myabs(a.x-b.x);
	d=myabs(a.y-b.y);
	if ((d==2 && c==1) || (d==1 && c==2)){
		return 1;
	}else{
		return 0;
	}
}
int roisCanGo(cases a, cases b){
	int c, d;
	c=myabs(a.x-b.x);
	d=myabs(a.y-b.y);
	if (c==1 && d==1){
		return 1;
	}else{
		return 0;
	}
}
void afficher(echiquier a){
	int i, j;
	for (j=0;j<10;j++){
		printf("----");
	}
	printf("\n");
	for (i=0;i<8;i++){
		for (j=0;j<8;j++){
			printf(" | %c", a.c[i][j]);
		}
		printf(" |\n");
		for (j=0;j<10;j++){
			printf("----");
		}
		printf("\n");
	}
}
int sol(int nbr, int di, int dj, echiquier a, int (*fnc) (cases a, cases b)){
	int i, j, k, l, m, n=0;
	cases c, b;
	if (nbr==0){
		//afficher(a);
		return 1;
	}
	nbr--;
	for (i=di;i<8;i++){
		for (j=dj;j<8;j++){
			if (a.c[i][j]==' '){
				m=0;
				for (k=0;k<=di;k++){
					for (l=0;l<8;l++){
						if ((k!=i || l!=j ) && a.c[k][l]=='Q'){
							c.x=i;
							c.y=j;
							b.x=k;
							b.y=l;
							if (fnc(c, b)){
								m=1;
								break;
							}
						}
					}
					if (m) break;
				}
				if (!m){
					a.c[i][j]='Q';
					n+=sol(nbr, i, j, a, fnc);
					a.c[i][j]=' ';
				}
			}
		}
		dj=0;
	}
	return n;
}
echiquier new_echiquier(){
	echiquier a;
	int i, j;
	for (i=0;i<8;i++){
		for (j=0;j<8;j++){
			a.c[i][j]=' ';
		}
	}
	return a;
}
int main(){
	echiquier a=new_echiquier();
	printf ("il y a %d solutions au problÃ?me des 8 dames!\n",sol(8, 0, 0, a, damesCanGo));
	printf ("il y a %d solutions au problÃ?me des 14 fous!\n",sol(14, 0, 0, a, fousCanGo));
	printf ("il y a %d solutions au problÃ?me des 32 cavaliers!\n",sol(32, 0, 0, a, cavaliersCanGo));
	printf ("il y a %d solutions au problÃ?me des 16 rois!\n",sol(16, 0, 0, a, roisCanGo));
	return 42;
}

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (coucou747)