L'algorithme des 8 reines

Soyez le premier à donner votre avis sur cette source.

Snippet vu 13 465 fois - Téléchargée 29 fois

Commenter

Contenu du snippet

Un algorithme trés simple à comprendre

Source / Exemple : 


/*
pour j allant de 1 . 8 effectuer
 si la case (i,j) est libre et non control,e alors :
 1-occuper cette case
 2-si (i=8), on a trouv, une solution, sinon on remplit la (i+1)-iSme ligne
 3-lib,rer la case (i,j)


  • /

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<math.h>
int x[8];
int compteur=0;
void echiquier()
{int i,j;
printf("\n\n\n");
for(i=0;i<=7;i++)
{
for(j=0;j<=7;j++)
printf("0");
printf("\n");
}
}
void poser()
{
int i;
clrscr();
compteur++;
printf("Voici la solution N=%d\nAppuyer sur une touche pour continuer...                    Esc pour sortir!!!",compteur);
echiquier();
for(i=0;i<=7;i++)
{
gotoxy(i+1,x[i]+5);printf("X");
}
}
int libre(int l ,int c)
{
int i;
for(i=0;i<c;i++)
if ((x[i]==l)||(abs(x[i]-l)==abs(i-c))) return 0;
return 1;
}
void solution(int n)
{
int i;
if(n==8)
{
poser();
if(getch()==27) exit(1);
}
else
for(i=0;i<8;i++)
if(libre(i,n))
{
x[n]=i;
solution(n+1);
}
}
void main()
{
solution(0);
}

A voir également

Ajouter un commentaire

Commentaires

Signaler
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
 -
je rêve ou c'est du "brute force" ton algo? lol, c'est pas la meilleur manière. ou bien j'ai pas compris, mais pour des algos d'intelligence artificielle (trouver une solution à partir des règles du problème), le plus simple c'est encore d'utiliser des piles LIFO (last int, first out) qui permettent de tester "en profondeur d'abord".

je vias pas retapper le tuto de GLInfrench, va voir ça:
http://glinfrench.apinc.org/rubrique.php3?id_rubrique=7

tu prends le premier, tu le lis, et c'est un bond en avant :-)

pour les piles en C++, je te conseil <stack> de la STL, c'est excellent.

ciao ;-)


PS: et encore des gens qui côtent mal sans commenter ???
Signaler
eldered
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
 -
J'ai fais le même exo, mais en JAVA! J'utilise des graphes d'états avec un principe de séparation, je m'explique :

Tout d'abord pour qu'un reine ne soit pas en prise avec une autre, chaque reine doit être sur une ligne différente. Je vais donc chercher à placer une reine par ligne. Pareillement pour les colonnes. Et pour terminer il faut faire attention au diagonales de part et d'autre de ta reine. J'ai donc réalisé un graphe imaginaire, avec, pour chaque noeud, une matrice représentant ton echiquier. A une ligne i, Je balance ma fonction recursive sur toute les cases que je peux occuper. Cette fonction recursive va refaire le meme traitement mais a la case i+1 etc .... Je passe ne parametres une matrice avec les positions condamnée à la ligne i, mais aussi celles condamnées par la reine que je viens de placer à la ligne i. Finalement je m'arréte quand je suis au bout de l'échiquier. Si j'ai N reines de placées sur mon echiqiuer de taille N*N, j'affiche la solution, rien sinon.

Petit + : Je fais cet exo avec N reines.

Tu trouvera le source sur www.blindprod.fr.st, si tu as des remarques n'hesites pas !

Voila ++ !
Signaler
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
 -
j'ai fait l'exo à la main, et pr n reines il te faut un échiquier de n cases de côté, sauf pour n <= 4, là tu ne peux mettre que n-1 reines (je sais plus si c t 4 ou 3, j'ai fait ça y a lgtps)
Signaler
eldered
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
 -
c 4, et vi il faut un echéquier de n*n. Mais ce qui est bien dans celui que j'ai fait, c que j'utilise la structure algorithmique "graphe", et ça c puissant !
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 (cs_mtougui)