Introduction
Le but du problème des huit dames 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. À noter que ce problème appartient au domaine des problèmes mathématiques et non à celui de la composition échiquéenne.
Simple mais non trivial, ce problème sert souvent d'exemple pour illustrer des techniques de programmation.
Histoire
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é).
Variantes
- Avec des pièces différentes
Trente-deux cavaliers, quatorze fous ou seize rois peuvent être disposés sur un échiquier traditionnel. Les pièces d'échecs féeriques peuvent remplacer les dames.
- Avec des échiquiers différents
- Pólya a étudié le problème des n-dames sur un échiquier toroïdal. D'autres supports ont été utilisés, comme les échiquiers tridimensionnels.
- Le problème des dominations
- Le problème est de trouver le nombre minimal de dames (ou d'autres pièces) nécessaires pour contrôler toutes les cases d'un échiquier n×n. Par exemple pour un échiquier « 8×8 », ce nombre vaut cinq.
- Le problème des neuf dames (en anglais)
- Il faut placer neuf dames et un pion sur un échiquier classique, en évitant que les dames ne puissent se prendre. Ce problème se généralise en considérant un échiquier n×n et r dames (r>n) et il faut trouver le nombre minimum de pions, de telle sorte que les dames et les pions puissent être placés sur l'échiquier sans que des dames ne se menacent.
- Le Carré magique
- En 1992, Demirörs, Rafraf et Tanik ont publié une méthode de conversion de carrés magiques en solutions du problème des n-dames, et réciproquement.
- Le carré latin
- Les problèmes d'échecs
- Les types de problèmes d'échecs
Les solutions
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.)
on remarque que ce problème des huit reines est encore plus difficile quand on y ajoute la condition que huit reines ne soient non seulement jamais en prise l'une avec l'autre mais qu'en plus trois d'entre elles ne soient jamais alignées ( par la marche du cheval ou autre). Alors on voit que, parmi les solutions précédentes, seule la solution 10 est acceptable.
