Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis
Huit dames)
Le but du « problème »[1] des huit dames[2], est de placer huit dames d'un jeu d'échecs sur un échiquier de 8×8 cases sans que les dames ne puissent se menacer mutuellement, conformément aux règles du jeu d'échecs (la couleur des pièces étant ignorée). Par conséquent, deux dames ne devraient jamais partager la même rangée, colonne, ou diagonale.
Simple mais non trivial, ce problème sert souvent d'exemple à des techniques de programmation.
Durant des années, beaucoup de mathématiciens, y compris Gauss ont travaillé sur ce problème, qui est un cas particulier du problème généralisé des n-dames, posé en 1850 par Franz Nauck, et qui est de placer n dames « libres » sur un échiquier de n×n cases. En 1874, S. Gunther proposa une méthode pour trouver des solutions en employant des déterminants, et J.W.L. Glaisher affina cette approche.
Ce problème fut utilisé au début des années 1990, dans le jeu sur ordinateur The 7th Guest (Le Septième Invité).
[modifier] Élaboration d'une solution
Il existe un algorithme simple retournant une solution simple pour n dames si n = 1 ou n ≥ 4:
- Diviser n par 12. Se rappeler du reste (c'est 8 pour le problème des huit dames).
- Écrire dans l'ordre la liste des nombres pairs de 2 à n.
- Si le reste est 3 ou 9, mettre 2 à la fin de la liste.
- Écrire dans l'ordre les nombres impairs de 1 à n, mais, si le reste est 8, permuter les deux à deux (ie 3, 1, 7, 5, 11, 9, …).
- Si le reste est 2, permuter les places de 1 et 3, puis mettre 5 à la fin de la liste.
- Si le reste est 3 ou 9, mettre 1 et 3 à la fin de la liste.
- Placer la reine de la première colonne dans la ligne avec le premier nombre de la liste, placer la reine de la seconde colonne dans la ligne avec le deuxième nombre de la liste, etc.
Pour n = 8 ceci a pour conséquence la solution montrée ci-dessus.
- 14 dames (reste 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
- 15 dames (reste 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
- 20 dames (reste 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
Le problème des huit dames a 92 solutions distinctes, ou seulement 12 solutions en tenant compte de transformations telles que des rotations ou des réflexions (par l'intermédiaire du lemme de Burnside.)
