|
DAME Le problème des huit dames
ou des huit reines est classique car il se prête bien à une initiation informatique, notamment pour
apprendre la notion de récursivité. Problème formalisé en 1848
par le jouer d'échecs Max Bezzel. |
|
D C'est DAME ! |
|
Mais, le mot reine est
souvent utilisé du fait que cette |
|
||
Problème Faire passer la dame sur 3 x 3 cases en
seulement 4 mouvements. |
Solution Il y a une astuce: utilisation de deux cases
supplémentaires sur le damier. |
|
|
|||||||
Caractérisation de l'énigme
|
|||||||
Énigme Combien de pions au
minimum peut-on placer sur les sommets des carrés (points bleus) sans que
deux pions soient sur la même ligne ? |
Réponse Maximum six
pions. Cette énigme est
du même type que celle des huit reines. |
||||||
Problème
des huit d Eight
queens puzzle |
|
|||||
Caractérisation de l'énigme
Problème
des huit reines Il est possible de placer huit dames
sur un échiquier sans qu'elles ne s'attaquent les unes les autres (on ne
tient pas compte de la couleur de la dame). Autrement dit: placer huit dames
sur des lignes, colonnes et diagonales différentes. Solutions Remarque Il y a bien une reine par ligne et
une reine par colonne. Observation utile pour réaliser un algorithme de
résolution. Attention, ce n'est pas vrai pour les pandiagonales (diagonales
reconstituées par
enroulement). |
Correspondance
avec les solutions présentées sur la page Wikipédia
Voir Nombre 92
Vous
pouvez jouez au problème des huit dames sur Internet:
Exemple
de résolution
Vous
pouvez aussi vous essayer à la programmation
de ce jeu. Un million de dollars est offert
par le Clay Mathematics Institure à celui qui trouvera un algorithme
capable de résoudre le cas 1000x1000 réalisable en un temps raisonnable sur
ordinateur. |
|
|
|
Merci
à Jos Heynderickx pour tous les
compléments apportés à cette page
Suite |
|
Voir |
|
Sites |
|
Algorithme et programmation |
|
Cette page |