Miles > 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.
C exactement ce ke fait mon algo ... il place la premiere reine sur la premiere colonne de la premiere ligne
ensuite il passe a la 2ème ligne ou il va essayer de placer la 2eme reine. Il commence par regarder si la premiere case de la 2eme ligne est non-attaquée, si elle l'est alors, il regarde la prochaine case de la ligne, si elle n'y etait pas il place la 2 eme reine dessus et passe a la 3eme reine sur la 3eme ligne
losque il arrive a poser sur l'echiquier la n ème reine ca veut dire que l'ago a trouver une solution, on peut donc l'afficher et ensuite continuer l'ago pour la soluce suivante !
A l'etape i, si la k eme reine qu'on essaie de placer sur la k eme ligne ne peut pas etre placer [c'est a dire qu'on arrive au bout de la ligne], alors on remonte d'un cran : c'est a dire qu'on repasse a la reine k-1-eme sur la k-1-eme ligne et on cherche la prochaine case valide pour cette reine ...
Bon en fait c exactement ce k'on ferait si on avait a resoudre ce probleme a la main !
pwet
smeet 2001-11-06 at 05:50pm Desole de pas avoir pu participer.
D'apres moi, il existe une solution encore plus simple.
Voyez le topic "tours de hanoi" : les deux sujets etaient poses en meme temps.
Pour les tours de hanoi, j'ai trouve une solution enfantine (vraiment), et je pense que le pb des 8 reines peut se
resoudre par une solution quasiment analogue.
Cf le nouveau topic.
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é.
ben ma solution pour les 8 reines est aussi enfantine :]
ca prend 5 lignes et c la recursivite qui fait tout !
pwet
Miles 2001-11-11 at 08:58pm CAML aurait très bien pu servir ici - il arrive à peu près à bien dérécursifier -
Bill-Bob : Tu n'as toujours pas répondu à ma question de l'autre fois, mais bon, je te laisse du temps pour répondre.
Tu changes souvent de première ligne dans ton algo ? - pas eu la force et le temps de regarder plus précisément -
Miles 2001-11-12 at 08:01am La question si tu venais aussi de SupElec.
moi je suis d'accord avec Bill-Bob, la solution la plus simple est la sienne puisque des qu'elle rencontre un cas impossible elle revient en arriere et saute ce cas pour passer aussuivant. c'est donc elle qui fait le moins de test...
