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 ?
Cinq font un et un font cinq : le tout est UNITE.
C'est dans l'incompréhension que je suscite que je trouve ma raison d'être.
Je suis moi, et je le suis parce que les autres ne le sont pas, et que ce sont eux qui forment ma personne.
Inconscience et déraison sont source d'imagination.
Au delà de ma conscience et de mon inconscient, mes rêves créent la réalité.

2

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)
XLib v1.00 Powerrrrrrrrrrrrrrrrrrrr!

3

le but n'est pas de trouver les solutions... mais de faire un algo permettant de les trouver (si possible toutes wink)
In many respects the Yoshi is like a beautiful woman. A man can come so enamoured that he bestows on her all his time, his energy and his fortune.
- Fred whipple, 1960

*** Ne sous-estimez pas la puissance de la Marmotte ***
© Marmotte Team : LaMarmotte, sBibi, Vark & Sabrina

4

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...
La programmation est un art... Ne prétendons pas en être des virtuoses mais tout au plus des adeptes...
ASM Rulez!!

5

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)
Cours et tutos Asm: http://membres.lycos.fr/sirryl

6

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.
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

7

c exactement ce que g fait pr le trouver manuellement... smile
In many respects the Yoshi is like a beautiful woman. A man can come so enamoured that he bestows on her all his time, his energy and his fortune.
- Fred whipple, 1960

*** Ne sous-estimez pas la puissance de la Marmotte ***
© Marmotte Team : LaMarmotte, sBibi, Vark & Sabrina

8

Les deux algos proposes ici marchent, mais ne me semblent pas efficaces.
La recursivite efficace de base, c'est le mieux, ici, non ?
Cinq font un et un font cinq : le tout est UNITE.
C'est dans l'incompréhension que je suscite que je trouve ma raison d'être.
Je suis moi, et je le suis parce que les autres ne le sont pas, et que ce sont eux qui forment ma personne.
Inconscience et déraison sont source d'imagination.
Au delà de ma conscience et de mon inconscient, mes rêves créent la réalité.

9

C'est-à-dire par récurrence ?
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

10

Voilà (j'espère qu'il n'y a pas de bogues - attention 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:
}
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

11

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]
La programmation est un art... Ne prétendons pas en être des virtuoses mais tout au plus des adeptes...
ASM Rulez!!

12

Kevin, ta solution teste tout, c'est ça ?
Elle est pas un peu trop lente ?
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

13

a tester smile

14

Elle est plus lente que la mienne, parce qu'elle est en N^8 et la mienne est plutôt en N.
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

15

Miles: tu solution est en o(N)? bizarre ça: parce que avec 8 reines il y a 92 possibilités...
La programmation est un art... Ne prétendons pas en être des virtuoses mais tout au plus des adeptes...
ASM Rulez!!

16

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

17

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).
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

18

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]
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

19

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 smile
Avec "Reine N" le programme donne toute les solutions pour placer N reines dans un echiquier de N*N embarrassed)
avatar
pwet

20

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 smile
avatar
pwet

21

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.
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

22

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

23

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
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

24

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

25

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 smile
avatar
pwet

26

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

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 smile

afficher echiquier : ca affiche la configuration de l'echiquier que le programme vient de trouver smile ... 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 smile

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

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

27

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.
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

28

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

29

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

30

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 smile

c ce ke je voulais sire smile
avatar
pwet