L'ALGORITHME DES 8 REINES

Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
- - Dernière réponse : eldered
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
- 5 févr. 2004 à 12:41
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/18571-l-algorithme-des-8-reines

Afficher la suite 
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 ???
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 ++ !
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)
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 !