Problème des huit dames

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Chess zhor 26.png
Chess zver 26.png
Case blanche a8 vide Case noire b8 vide Case blanche c8 vide Reine blanche sur case noire d8 Case blanche e8 vide Case noire f8 vide Case blanche g8 vide Case noire h8 vide
Case noire a7 vide Case blanche b7 vide Case noire c7 vide Case blanche d7 vide Case noire e7 vide Case blanche f7 vide Reine blanche sur case noire g7 Case blanche h7 vide
Case blanche a6 vide Case noire b6 vide Reine blanche sur case blanche c6 Case noire d6 vide Case blanche e6 vide Case noire f6 vide Case blanche g6 vide Case noire h6 vide
Case noire a5 vide Case blanche b5 vide Case noire c5 vide Case blanche d5 vide Case noire e5 vide Case blanche f5 vide Case noire g5 vide Reine blanche sur case blanche h5
Case blanche a4 vide Reine blanche sur case noire b4 Case blanche c4 vide Case noire d4 vide Case blanche e4 vide Case noire f4 vide Case blanche g4 vide Case noire h4 vide
Case noire a3 vide Case blanche b3 vide Case noire c3 vide Case blanche d3 vide Reine blanche sur case noire e3 Case blanche f3 vide Case noire g3 vide Case blanche h3 vide
Reine blanche sur case blanche a2 Case noire b2 vide Case blanche c2 vide Case noire d2 vide Case blanche e2 vide Case noire f2 vide Case blanche g2 vide Case noire h2 vide
Case noire a1 vide Case blanche b1 vide Case noire c1 vide Case blanche d1 vide Case noire e1 vide Reine blanche sur case blanche f1 Case noire g1 vide Case blanche h1 vide
Chess zver 26.png
Chess zhor 26.png
Exemple de solution

Le but du problème des huit dames[1] 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. Ce problème appartient au domaine des problèmes mathématiques et non à celui de la composition échiquéenne[2].

Simple mais non trivial, ce problème sert souvent d'exemple pour illustrer des techniques de programmation.

Histoire[modifier | modifier le code]

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é).

Les solutions[modifier | modifier le code]

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).

Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 1
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 2
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 3


Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 4
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 5
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 6


Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 7
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 8
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 9


Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 10
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 11
Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png
Solution unique 12


Ce problème des huit dames est encore plus difficile[réf. souhaitée] quand on y ajoute la condition que huit dames 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 (comme b4-c6-d8 dans la solution 1 ou a5-d4-g3 dans la solution 5). Alors on voit que, parmi les solutions précédentes, seules les solutions 9 et 10 sont acceptables.

Variantes[modifier | modifier le code]

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[3]
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.
Les carrés magiques
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[4].
Les carrés latins
Les problèmes d'échecs

Le problème des huit dames en informatique[modifier | modifier le code]

Le problème des huit dames est un bon exemple de problème simple mais non évident. Pour cette raison, il est souvent employé comme support de mise en œuvre de différentes techniques de programmation, y compris d'approches non traditionnelles de la programmation telles que la programmation par contraintes, la programmation logique ou les algorithmes génétiques.

Le plus souvent, il est employé comme exemple d'un problème qui peut être résolu avec un algorithme récursif, en exprimant qu'une solution du problème des n-dames peut être obtenue, par récurrence, à partir d'une solution quelconque du problème des (n-1)-dames par l'adjonction d'une dame. La récurrence commence avec la solution du problème de 0-dame qui repose sur un échiquier vide.

Cette technique est beaucoup plus efficace que l'algorithme naïf de recherche exhaustive, qui parcourt chacun des 648 = 248 = 281 474 976 710 656 placements possibles des huit dames, pour retirer tous ceux pour lesquels plusieurs dames se trouvent sur une même case (laissant seulement A_{64}^8=64!/56! = 178 462 987 637 760 arrangements possibles) ou pour lesquels des dames se menacent mutuellement.

Ce très « mauvais » algorithme produira les mêmes résultats à plusieurs reprises en attribuant différentes places aux huit dames, et recommencera les mêmes calculs plusieurs fois pour différentes parties de chaque solution. Un algorithme légèrement meilleur de recherche exhaustive place une seule dame par rangée, réduisant à seulement 88 = 224 = 16 777 216 placements possibles.

Il est possible de faire beaucoup mieux que cela. Par exemple, un programme de recherche en profondeur examinerait seulement 15 720 placements possibles des dames en construisant un arbre de recherche et en parcourant les rangées de l'échiquier une par une, éliminant la plupart des positions possibles à un stade très primitif de leur construction.

La programmation par contraintes est bien plus efficace pour ce problème. Un algorithme de « réparation itérative » commence typiquement à partir d'un placement de toutes les dames sur l'échiquier, par exemple avec une seule dame par colonne. Il compte alors le nombre de conflits entre dames, et utilise une méthode heuristique pour déterminer comment améliorer les placements des dames. La méthode heuristique de moindre conflit, qui consiste à déplacer la pièce ayant le plus grand nombre de conflits, dans la même colonne à une place où le nombre de conflits est le plus petit, est particulièrement efficace. Elle résout le problème des millions de dames (sur un échiquier de 1 000 000×1 000 000 cases) en moins de 50 étapes en moyenne!

L'obtention de cette moyenne de 50 étapes suppose que la configuration initiale soit raisonnablement bonne. Si au début, un million de dames sont placées dans la même rangée, l'algorithme prendra évidemment plus de 50 étapes pour résoudre le problème. Un point de départ « raisonnablement bon » consiste à placer chaque dame dans une colonne telle qu'elle soit en conflit avec le plus petit nombre de dames se trouvant déjà sur l'échiquier.

Remarquez que la méthode de réparation itérative, à la différence de la recherche en profondeur décrite ci-dessus, ne garantit pas une solution. Comme toutes les méthodes de plus profonde descente, elle peut se bloquer sur un extremum local (dans ce cas l'algorithme peut être remis en marche avec une configuration initiale différente.) D'un autre côté, elle peut résoudre des problèmes de grandes tailles qui sont largement au-delà de la portée d'une recherche en profondeur.

Notes[modifier | modifier le code]

  1. Parfois appelé problème des huit reines par traduction de l'anglais, bien que le nom de cette pièce soit Dame en français.
  2. Le terme de problème est ici mis entre guillemets, car il s'agit bien d'un problème au sens général du terme, mais pas d'un problème d'échecs au sens de la composition échiquéenne. En effet, ce problème n'a pas été composé et n'a pas d'auteur. De plus, il n'a pas une solution unique, mais sur ce dernier point, il suffirait de changer son énoncé en demandant de trouver le nombre de solutions et il pourrait alors être rangé dans la catégorie des problèmes d'échecs mathématiques.
  3. (en) The 9 Queens Problem sur chessvariants.org
  4. (en) O. Demirörs, N. Rafraf, M. M. Tanik, « Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions », Journal of Recreational Mathematics, vol. 24,‎ 1992, p. 272-280

Voir également[modifier | modifier le code]

Références[modifier | modifier le code]

  • Édouard Lucas, Récréations mathématiques, vol. 1, Gauthier Villars,‎ 1882, « Récréation n°4 : Le problème des huit reines au jeu des échecs »
  • Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6.

Liens vers les solutions[modifier | modifier le code]