Le probleme des 8 reines - Page 1

ccf le casse tete de vero dans j'aio rien a dire.
Le defi est de trouver une configuration sur un echiquer comprenant 8 reines sans qu'aucune d'entre elle ne soit sous la menace d'etre prise.
Trouver une solution est facile.
Parviendrez vous a ecrire un algo efficace calculant TOUTES les solutions ?

je dirais meme plus:
trouver une solution est facile...
en trouver 4 aussi...
en trouver 8 aussi...
en trouver 16 un peut moins
En trouver 32 impossible (il me semble)

le but n'est pas de trouver les solutions... mais de faire un algo permettant de les trouver (si possible toutes )

TiMad: il y a 92 possibilité pour 8 reines!
Voici un algo pour N reines avec un echiqier de N*N:

#include <stdio.h>

int NombreReines;
int TableauReines[50];

int nonprenable(num){
int i;
if(num > 0)
for (i = 0 ; i < num ; i++)
if ((TableauReines[i] == TableauReines[num]) || (TableauReines[i] == TableauReines[num] + num - i) || (TableauReines[i]==TableauReines[num] - num + i))
return(0); //La reine peut prendre ou etre prise
return(1);
}


void placer(num){
int etat = 0;
int nonplacable = 0;

while ((nonplacable == 0) && (etat == 0)){
TableauReines[num]++;
if (TableauReines[num] > NombreReines){
TableauReines[num] = 0;
nonplacable = 1;
}
else
etat = nonprenable(num);
}
}


void main(void)
{
int Colonne = 0;
long int NombreSolutions = 0;
int i;

do{
printf("nnPlacer N reines en sécurité sur un echiquier de N*N...")
printf("nnCombien de reines ?")
scanf("%d", &NombreReines);
}while(NombreReines > 50); //Si vous voulez plus: modifier int TableauReines[50]!!

for (i = 0 ; i < NombreReines ; i++)
TableauReines[i] = 0;

do{
placer(Colonne);

if (TableauReines[Colonne] != 0){
if (Colonne < NombreReines - 1)
Colonne++;
else{
NombreSolutions++;
printf("%ld ",NombreSolutions);
for (i = 0 ; i < NombreReines ; i++)
printf(" %d",TableauReines[i]);
printf("n")
}
}
else
Colonne--;
}while (TableauReines[0] != 0);

printf("Il y a %ld solutions pour %d reines. ",NombreSolutions ,NombreReines);
}

Pour les courageux qui veulent tester avec bcp de reines: avec 13 reines dans un echiquier de 13*13 on a deja 73712 solutions...

moi je l'aurai fait en CaML, mais paske j connais presque rien en C
Info: le Caml est en 2è position niveau calculs de maths derrière le C (ou troisième derrière le C++, je sais plus)

Une approche pour trouver une solution est la réparation. Je m'explique :
- Tu prends ta matrice N*N
- Tu place dans chaque colonne une reine
- Tu prends chaque colonne et tu testes
1 - pour chaque case de la colonne le nombre de reines qui peuvent l'atteindre, tant dans les colonnes qui précèdent que dans les colonnes qui suivent
2 - tu choisis la case ayant le nombre le plus faible
- Tu fait ça pour chaque colonne.
- En faisant ça, tu devrais trouver en bouclant.
- Malheureusement, il se peut qu'une solution ne puisse être atteinte par ce moyen, et il faut recommencer dans ce cas.

c exactement ce que g fait pr le trouver manuellement...

Les deux algos proposes ici marchent, mais ne me semblent pas efficaces.
La recursivite efficace de base, c'est le mieux, ici, non ?

C'est-à-dire par récurrence ?

Voilà (j'espère qu'il n'y a pas de bogues - c'est en qqch. entre O(n^8) et O(n^10) - à calculer exactement):

[i]unsigned char a[64],i,j,k,l,m,n,o,p,q,r,s;
for(i=0,i<64,i++)
for(j=i+1,j<64,j++)
for(k=j+1,j<64,k++)
for(l=k+1,j<64,l++)
for(m=l+1,j<64,m++)
for(n=m+1,j<64,n++)
for(o=n+1,j<64,o++)
for(p=o+1,j<64,p++)
{
memset(a,64,0);
a=a[j]=a[k]=a[l]=a[m]=a[n]=a[o]=a[p]=1;
for(q=0,q<8,q++) if(a[q]+a[q+8]+a[q+16]+a[q+24]+a[q+32]+a[q+40]+a[q+48]+a[q+56]>1) goto skip;
for(q=0,q<64,q+=8) if(a[q]+a[q+1]+a[q+2]+a[q+3]+a[q+4]+a[q+5]+a[q+6]+a[q+7]>1) goto skip;
for(q=0,q<15,q++)
{
s=0;
for(r=0,r<=q,r++) s+=a[r*7+q];
if(s>1) goto skip;
s=0;
for(r=0,r<=q,r++) s+=a[r*9-q+7];
if(s>1) goto skip;
}
// afficher la solution
skip:
}

smeet: je pense que ma solution est mieux que la recursivité: de toute façon, tu est obligé de tester quasiment toutes les possibilité... donc l'iterativité est mieux (de plus elle est presque toujours plus rapide...)

[edit]Edité par zewoo le 29-10-2001 à 23:50:18[/edit]

Kevin, ta solution teste tout, c'est ça ?
Elle est pas un peu trop lente ?

a tester

Elle est plus lente que la mienne, parce qu'elle est en N^8 et la mienne est plutôt en N.

Miles: tu solution est en o(N)? bizarre ça: parce que avec 8 reines il y a 92 possibilités...

La solution de Miles ne donnerait jamais toutes les 92 possibilités. Et la mienne, en effet, teste toutes les nCr(64,8)=4426165368 possibilités de placer 8 reines dans 64 cases de l'échiquier.

Au fait, voilà une solution meilleure, qui n'essayera pas de placer plusieurs reines dans la même ligne:

[i]unsigned char a[64],i,j,k,l,m,n,o,p,q,r,s;
for(i=0,i<8,i++)
for(j=8,j<16,j++)
for(k=16,j<24,k++)
for(l=24,j<32,l++)
for(m=32,j<40,m++)
for(n=40,j<48,n++)
for(o=48,j<56,o++)
for(p=56,j<64,p++)
{
memset(a,64,0);
a=a[j]=a[k]=a[l]=a[m]=a[n]=a[o]=a[p]=1;
for(q=0,q<8,q++) if(a[q]+a[q+8]+a[q+16]+a[q+24]+a[q+32]+a[q+40]+a[q+48]+a[q+56]>1) goto skip;
for(q=0,q<15,q++)
{
s=0;
for(r=0,r<=q,r++) s+=a[r*7+q];
if(s>1) goto skip;
s=0;
for(r=0,r<=q,r++) s+=a[r*9-q+7];
if(s>1) goto skip;
}
// afficher la solution
skip:
}

Cela ne testera que 8^8=16777216 possibilités, et de plus on a 8 tests de moins à faire (ceux qui testent s'il y a plusieurs reines sur la même ligne).

Encore une chose: cette solution est en O(n^n) et la précédente était en O((n²)^n)=O(n^(2n)) où n est le nombre de lignes (l'estimation O(n^8) pour la précédente était fausse même si on prend n comme étant le nombre d'éléments puisque le 8 n'est pas constant, c'est le nombre de lignes). Au fait, le O(n^(2n)) n'est pas une bonne estimation pour la solution précédente non plus... (le nombre exact de possibilités testées est nCr(n²,n)) Mais en tout cas, la nouvelle solution est clairement en O(n^n) parce que je teste n^n possibilités.
[edit]Edité par Kevin Kofler le 01-11-2001 à 23:21:41[/edit]

Encore un de ces topics qui m'echappent :]
Je post avec un peu de retard mais tant pis :]

// ---------------------------------------------------------------- //
#include <stdio.h>
#include <stdlib.h>
// ---------------------------------------------------------------- //
char	*t,NR;
unsigned long cmpt=0;
// ---------------------------------------------------------------- //
char	libre(char,char);
void	afficher_echiquier(void);
int	main(int,char**);
void	reine(char);
// ---------------------------------------------------------------- //
char libre(char ligne,char colonne)
{
	char i,j;
	for (j=1,i=ligne-1;i>=0;i--,j++)
	{
		if ((colonne==t[i]) || (colonne==t[i]+j) || (colonne==t[i]-j))
			return(0);
	}
	return(1);
}
// ---------------------------------------------------------------- //
void afficher_echiquier(void)
{
	char i;
	printf("n %u - ",++cmpt);
	for (i=0;i<NR;i++)
		printf("%u ",t[i]+1);
}
// ---------------------------------------------------------------- //
int main(int argc,char **argv)
{
	int i;
	if ((i=(int)atoi(*++argv)))
	{
		NR=(char)i;
		t=(char *)malloc(NR*sizeof(char));

		reine(NR-1);

		printf("n%u coups possibles pour %u reinesn",cmpt,NR);
		free(t);
		return(0);
	}
	else
		return(1);
}
// ---------------------------------------------------------------- //
void reine(char n)
{
	char i;
	if (n==-1)
		afficher_echiquier();
	else
	{
		for (i=0;i<NR;i++)
		{
			if (libre(NR-n-1,i))
			{
				t[NR-n-1]=i;
				reine(n-1);
			}
		}
	}
}
// ---------------------------------------------------------------- //

C en C pour PC mais ca marche bien :]
suffit d'appeler le programme en mettant le nombre de case de l'echiquier
Avec "Reine N" le programme donne toute les solutions pour placer N reines dans un echiquier de N*N )

par contre il y a tellement de solutions possible pour N>20 et plus que c meme pas la peine d'esperer de votre PC qu'il arrive au bout

Mon but n'est jamais d'avoir toutes les solutions. J'avais fait ça pour un jeu très connu dont je ne siterais pas le nom que j'avais adapté plusieurs fois. Mais je ne fais plus ce genre de chose : vive l'IA.

ben c le but fixé par le createur d topic en tout cas !

D'accord, plantage de ma part. Mais il est possible de chopper les 92 solutions avec ce système - seulement qu'on aura peut-être plusieurs fois les mêmes

c un topic dans algo et optimisation non ? ;p
c pas du tout optimisé tont ruc :]

non mon algo donne les 92 solutions sans jamais donner 2 fois la meme !
il ne reteste jamais 2 fois le meme chemin !
et franchement je vois pas d'autres trucs plus efficaces ... mais bon g pas non plus de grandes connaissances en algo moa

pis si on compte bien il fait que 13 lignes l'algo donc c pas mal par rapport aux monstuosites d'algo iteratifs vus plus haut

le main c juste pour recupere la valeur passee en argument du programme et ensuite il appelle la fonction Reine recursive qui traite le probleme

afficher echiquier : ca affiche la configuration de l'echiquier que le programme vient de trouver ... il affiche le numero de la colonne de la reine 1,2,3,4,5,6, ... ,n
chaque reine etant sur une ligne differente ! la reine 1 sur la ligne 1, la reine 2 sur la ligne 2, la reine n sur la ligne n

libre : c pour voir si la case que le programme "scanne" est deja attaquée par une autre piece ou pas

et reine c la fonction recursive qui fait tout le boulot de recherche

Il devrait y avoir mieux que du n^n, puisqu'on sait qu'il n'y a qu'une seule reine par ligne et par colonne. On devrait pouvoir éliminer des cas pour qu'il ne reste plus autant à chercher.

l'algo de Bill-Bop me paraît être la solution la plus élégante.

Bill-Bob un algo pourras tres bien faire le triple de ligne du tiens et etre 20 fois plus rapide

oxman a raison ... mais le probleme des reines est typiquement un probleme de nature recursive (on appelle ca du backtracking) alors c carrement une mauvaise idee d'implementer un algo iteratif (un boucle while ou for) pour le resoudre

c ce ke je voulais sire