PROBLÈME DES 8 REINES

eldered Messages postés 232 Date d'inscription vendredi 21 mars 2003 Statut Membre Dernière intervention 25 mai 2022 - 18 juin 2004 à 10:01
willti2s Messages postés 1 Date d'inscription samedi 17 janvier 2009 Statut Membre Dernière intervention 10 octobre 2010 - 10 oct. 2010 à 21:34

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/23786-probleme-des-8-reines

willti2s Messages postés 1 Date d'inscription samedi 17 janvier 2009 Statut Membre Dernière intervention 10 octobre 2010
10 oct. 2010 à 21:34

et c'est tres long comme code!

eldered Messages postés 232 Date d'inscription vendredi 21 mars 2003 Statut Membre Dernière intervention 25 mai 2022
18 juin 2004 à 23:01

Wé, c'est pas du rapide ! C'est bourrin, mais bon, c instructif !

++ Ed.

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
18 juin 2004 à 22:43

grmbl... viens d'écrire un algo de recherche en profondeur d'abord avec un minimum d'optimisations logiques etc en C++, et dès que je lui demande une résolution pour un échiquier de genre 13*13 il lui fait 25 secondes O_o bon, y a 80 000 solutions (dont je supprime la moitié dès le début en n'acceptant que des reines sur la première moitié de la première ligne, parce que sinon après tu génères toutes les symétries, c'est idiot). c'est qd même super lent! 8 reines ça met entre 0 et 15 ms ...

StanOfSky Messages postés 43 Date d'inscription mardi 30 mars 2004 Statut Membre Dernière intervention 7 octobre 2006
18 juin 2004 à 22:39

ouep c kler ke c un probleme classique ;)
encore un probleme super facile à résoudre en Prolog
pour ceux qui voudraient connaitre les méthodes de résolution avec description type : "génère et teste", "simple retour-arrière", "anticipation/noeud", "anticipation/noeud + échec d'abord"
c'est ici : http://www710.univ-lyon1.fr/~csolnon/Site-PPC/e-miage-ppc-som.htm

ya aussi comparaison de la vitesse d'execution des algos exemple :
http://www710.univ-lyon1.fr/~csolnon/Site-PPC/session4/e-miage-ppc-sess4.htm#grd6

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
18 juin 2004 à 18:42

oué oué, okok, mais je comprends pas, ... comme disais je sais plus qui, un algo est sensé résoudre un problème pour un programmeur qui préfère se casser la tête sur la rédaction de l'algo que sur le problème qu'on lui demande de résoudre ^^

écrire une interface pour que l'humain puisse se taper la recherche tout seul, c'est une insulte à la flemmardise des programmeurs! ;)

cs_khayyam Messages postés 51 Date d'inscription lundi 7 juin 2004 Statut Membre Dernière intervention 15 juillet 2005
18 juin 2004 à 16:06

ça y est, j'ai mis un nombre de reines customizable. le prog se révèle instantané (ou presque) même lorsqu'il y a beaucoup de reines.

j'ai aussi corrigé une affreuse bourde algorithmique.

évidemment, ce qui pourrait le ralentir considérablement, ce serait de faire afficher toutes les solutions pour un damier 16*16.

eldered Messages postés 232 Date d'inscription vendredi 21 mars 2003 Statut Membre Dernière intervention 25 mai 2022
18 juin 2004 à 13:10

Clonk : J'ai bien compris que c'était avec 8 reines, mais justement, je lui reprochais de ne pas donner les solutions. Ensuite, il y a plusieurs résolutions à ce problème, c'est pour ça que c interessant de voir comment s'y est pris le programmeur ...

Khayyam : Alala, comment ça "c'est franchement pas beaucoup plus difficile" ??? Fais le qu'on rigole ^^ ... Lance ton algo pour un damier de 16*16 et on verra le temps qu'il mettra ! Le but de l'algorithme (en général) c'est d'optimiser le temps de calcul sans perdre la solution ... si tu ne prend pas se problème avec des principes de séparation (condamnée des branches de ton graphe ...), ton pc va souffrir !

Enfin ceci dit, il est vrai que c'est pas compliquer, mais faut le faire pour capter le truc !

++ Ed.

cs_khayyam Messages postés 51 Date d'inscription lundi 7 juin 2004 Statut Membre Dernière intervention 15 juillet 2005
18 juin 2004 à 11:51

pour passer à n reines, c'est franchement pas beaucoup plus difficile. il suffit de changer les bornes et la taille du tableau. le générateur de solutions, ça sera pour la prochaine fois , si vous êtes sages.

Clonk Messages postés 278 Date d'inscription mardi 22 janvier 2002 Statut Membre Dernière intervention 29 août 2006
18 juin 2004 à 11:49

Rooo! Mais C même pas un générateur de solutions!!!
Bah alors? ;)
nan, C pas mal dans l'idée, mais le but du problème des n reines, C de générer toutes les solutions possibles!

Clonk Messages postés 278 Date d'inscription mardi 22 janvier 2002 Statut Membre Dernière intervention 29 août 2006
18 juin 2004 à 11:46

Nan eldered! sur un échiquier de 8*8, on essaye de place 8 reines pour qu'elles ne puissent pas se "bouffer" en un coup...
Ce problème est vieux comme le monde, c'est un cas d'école en informatique (jme le suis tapé 2 fois déjà)

Dis donc, tu veux pas essayer en n reines maintenant?
C tellement plus drôle ;)

eldered Messages postés 232 Date d'inscription vendredi 21 mars 2003 Statut Membre Dernière intervention 25 mai 2022
18 juin 2004 à 10:01

Salut,

Je n'ai pas télécharger ta source, mais si je comprend bien, elle permet à l'utilisateur de déplacer les reines sur le damier, puis qd il a placé les 8 reines, il a gagné ?

Il est ou l'exercice de style algorithmique ? Si tu donnais au moins toutes les solutions pour en placer 8, on pourrait parler d'algo, mais là, c'est plus de l'interface homme-machine.

Pour info : http://perso.wanadoo.fr/eddy.albert/sheets/pedag.htm
tu as le pb avec n reines et toutes ces solutions !

++ Ed.

Discussions similaires

Racine cubique

Convertions GT/s, MT/s, GB/s, Mhz

Remplacer une lettre par une autre

Scores foot direct

codage utf-8

Votre réponse

Discussions similaires