Problème des 8 dames

[Hari58]

Bonjour à tous,

Je suis actuellement en train de m'entrainer / me perfectionner sur le langage assembleur. Après avoir écumé les nombreux tutoriels d'une multitude de sites, j'ai entendu parler d'un code assembleur permettant de résoudre le problème des 8 reines à placer sur l'échiquier.

Même si je pense que vous connaissez, le problème consiste à placer 8 reines sur l'échiquier afin qu'aucune ne puisse "manger" l'autre ( ligne, colonne, diagonale ). J'ai réussi a comprendre et à résoudre auparavant les tours d'hanoi qui ne consiste qu'a gérer la récursivité, même si ce n'était pas optimisé je m'en suis sorti.

Cela fait environ 2 semaines que je suis dessus, et je ne trouve toujours pas comment faire. Je sais que c'est une attitude faible de ma part mais, est-ce que quelqu'un aurait le code assembleur pour résoudre le problème des 8 reines ? Cela m'aiderait énormément.


Merci à vous,

Cordialement, Hari

[edfed]

avant le code, il y a l'algorithme.

donc, qu'as tu comme algorithme? tu n'as pas bossé dessus? ha mais va falloir le faire, c'est important d'ecrire l'algorithme avant de coder ce genre de truc.

de quelle manière represente tu l'echiquier (un nombre 64 bits suffit largement)
de quelle manière represente tu les reines (un simple 0 pour absence, 1 pour presence suffit)

et donc, au final, il ne s'agit plus que de calculs conditionnels sur un nombre 64 bits, dans lequel il faut repartir nos 8 bits à 1 (les reines).

mais comme tout depend de l'algorithme, il faudra faire ça plus serieusement.

peut etre qu'un tableau de 64 octets (8*8) serait plus pratique en raison de l'arithmetique des pointeurs... à voir donc.


et pour conclure, c'est pas cool de demander comme coup de main un code tout fait. ça revient à tricher, meme s'il ne s'agit pas d'un devoir d'ecole, que c'est un projet perso, il ne faut pas tricher envers soi meme, il faut soit trouver la solution, soit changer de passion.

[Hari58]

Oui c'est bien ce que je pensais, je ne sais juste pas comment "condamner" des cases. C'est à dire, si la reine 1 et a 0,0, la ligne 0 ne peut pas etre mise a 1 autre part, la colonne 0 non plus et la diagonale 0+n,0+n doit l'être aussi.

Je suis bien conscient que ce n'est pas la meilleure solution de demander la solution, mais je vais bientôt intégrer une école d'ingénieur et je souhaiterai me "mettre à niveau" concernant tout les langages que j'ai appris ces deux dernières années..

[edfed]

pour ça, il y a une reponce toute bete.

vu que chaque ligne fait 8 cases
et qu'il y a 8 lignes.

on peu utiliser un masque.

ce masque sera utilisé pour tester les autres lignes.
tandis que sur la meme ligne, il ne faudra qu'un seul bit à 1 (celui qu'on vien de poser), ceux des lignes en dessous seront:
le meme bits, mais sur les autres lignes, donc, juste un test
des bits decalés à droite et à gauche pour les diagonales, donc, decalage logique et test.

en gros, il faudrait, avant de definir l'algo qui touve une solution tout seul, trouver l'algo de test, qui determine si la solution est valide ou non.

donc, pour trouver si une reine est sur une case deja occupée, il faut tout simplement tester l'absence d'un bit sur les 8 directions.

as tu essayé sur papier? j'ai reussi à trouver une solution en 4 essais.

Code :

1
2
3
4
5
6
7
8
9
 
00000100
00100000
00001000
00000001
10000000
00010000
01000000
00000010

je suis sur qu'il y a au moins 3 auters solutions (en faisant tourner l'echiquer), donc c'est pas si dur que ça à trouver.

l'algo pour trouver une solution sera difficile, mais il faut d'abord l'algo qui determine que la solution est juste, et ça, c'est très facile. ça doit etre l'affaire de 2 boucles ou 3 boucles imbriquées, à vue de nez, 80 lignes de code.



sinon, l'uitlisation d'un tableau de 8*8 octets sera beaucoup plus simple à mette en oeuvre, et permettra aussi un truc super, implementer un vrai echiquier, cases noire, cases blanches, pionts, cavaliers, fous, tours, camp.

tout un tas de données (un octets pouvant en representer 256) qui permettrons de faire un vrai echiquier.

une case vide sera egale à 0
une case avec une reine serait egale à 1
les cases marquées par la reine seront à 2
et donc, si une case est differente de 0, alors la case est occupée.

mais on en revien à l'algo qui determine la zone couverte par la piece, celui avec les decalages et tests, à part que l'on ne va faire que des decalages et copies de la valeur 2.

un tableau d'octets me semble très bon pour ce probleme.

mais un tableau de bits serait encore meilleur.

[Hari58]

J'avais créer un algorithme qui balayé le tableau 8*8 a la recherche de bits différents de 0 comme tu l'as dis. je passe de la première adresse, place une reine, placement de tout les bit de la meme ligne, colonne, et diagonale a 1, puis je continue a balayer, des qu'un bit a 0 apparait je place une autre reine et place les bits correspondants aux cases condamnés.

Corriges moi si je me trompe

[edfed]

l'algo est juste, mais il faudra conserver l'info sur les positions des 8 reines.

soit 8 autres octets.
ce qui pour un total de 16 octets permet en effet de contenir l'echiquier.

maintenant, il faut trouver comment ça fonctionne exactement pour poser les reines, il doit bien y avoir une regle, déjà, on remarque que des reines disposée à interval de cheval (+1, +2) permet d'en placer 7 sans difficulté.

[Forthman]

J'ai tape "8 reines" dans gougueul, et le premier lien était vers Wiki :
http://fr.wikipedia.org/wiki/Probl%C...des_huit_dames

Je pense qu'il y a tout pour pouvoir faire un zoli programme

a+ François