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);
}
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 ++ !
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 ???
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.