Voir la source de Problème des huit dames

{{Diagramme d'échecs
| tright
|

|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|ql|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__

|Exemple de solution
}}

Le but du '''problème des huit dames'''<ref group=note>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.</ref> est de placer huit dames d'un jeu d'[[échecs]] sur un échiquier de 8 × 8 cases sans que les dames 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 doivent 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]]<ref group=note>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.</ref>.

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ématicien]]s, y compris [[Carl Friedrich Gauss|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éterminant (mathématiques)|déterminants]], et [[James Whitbread Lee Glaisher|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 ==
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 remarquera qu'on réduit encore le nombre de solutions si on s'interdit que 3 dames soient alignées par la marche du cheval par exemple.

On notera qu'une des solutions remarquables, quelle que soit la taille de l'échiquier, est que chaque dame ait sa [[Symétrie|symétrique]] dans une colonne mitoyenne, sauf pour les 2 qui touchent l'[[Symétrie axiale|axe de symétrie]] horizontale de l'échiquier (Solution unique 5).

{| border="0" backgroundcolor="transparent"
|--
|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|ql|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__

|Solution unique 1
}}
|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|__|ql|__|__|__
|__|ql|__|__|__|__|__|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|__|ql|__|__
|ql|__|__|__|__|__|__|__

|Solution unique 2
}}
|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|ql|__|__|__|__
|__|ql|__|__|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|ql|__|__|__
|ql|__|__|__|__|__|__|__

|Solution unique 3
}}


|---
|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|ql|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|__|__|__|__|__|__|ql
|__|__|ql|__|__|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|__|__|ql|__|__|__
|__|ql|__|__|__|__|__|__

|Solution unique 4
}}

|
{{Diagramme d'échecs petit
| tright
|

|__|__|ql|__|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|__|__|__|__|__|__|ql
|ql|__|__|__|__|__|__|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|__|__|ql|__|__|__
|__|ql|__|__|__|__|__|__

|Solution unique 5
}}

|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|__|ql|__|__|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|ql|__|__|__|__|__|__

|Solution unique 6
}}


|---
|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|__|ql|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|__|ql|__|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|__|ql|__|__
|__|ql|__|__|__|__|__|__

|Solution unique 7
}}

|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|ql|__|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|__|ql|__|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|ql|__|__|__|__|__|__

|Solution unique 8
}}

|
{{Diagramme d'échecs petit
| tright
|

|__|__|ql|__|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|__|__|ql|__|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|ql|__|__|__
|__|__|__|__|__|__|ql|__
|__|ql|__|__|__|__|__|__

|Solution unique 9
}}


|---
|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|__|__|ql|__|__
|__|ql|__|__|__|__|__|__
|__|__|__|__|__|__|ql|__
|ql|__|__|__|__|__|__|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|ql|__|__|__
|__|__|ql|__|__|__|__|__

|Solution unique 10
}}

|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|__|__|__|ql|__|__|__
|__|ql|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|__|ql|__|__|__|__|__

|Solution unique 11
}}

|
{{Diagramme d'échecs petit
| tright
|

|__|__|__|__|__|ql|__|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|ql|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|__|__|ql|__|__|__|__|__

|Solution unique 12
}}



|}

== Variantes ==
=== Avec des pièces différentes ===
[[Principe des tiroirs#Disposition de fous sur un échiquier|Quatorze  fous]]<ref name = "delahaye18">{{Article |langue=français |auteur=[[Jean-Paul Delahaye]] |périodique=[[Pour la science]]|titre =Logique et calcul|sous-titre = Le principe des tiroirs |numéro = 433|mois=janvier |année =2018|passage = 78}}.</ref>, trente-deux cavaliers ou seize rois peuvent être disposés sur un échiquier traditionnel sans qu'aucune pièce n'en menace une autre. Les [[pièce féerique|pièces d'échecs féeriques]] peuvent remplacer les dames.

=== Avec des échiquiers différents ===
[[George Pólya|Pólya]] a étudié le problème des ''n''-dames sur un échiquier [[tore|toroïdal]]. D'autres supports ont été utilisés, comme les échiquiers [[Trois dimensions|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 ===
On cherche à placer neuf dames et un pion sur un échiquier classique, en évitant que les dames ne puissent se prendre<ref>{{en}} [http://www.chessvariants.org/problems.dir/9queens.html The 9 Queens Problem] sur chessvariants.org</ref>. 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 se menacent.
=== Les carrés magiques ===
En 1992, Demirörs, Rafraf et Tanik ont publié une méthode de conversion de [[Carré magique (mathématiques)|carrés magiques]] en solutions du problème des ''n''-dames, et réciproquement<ref>{{Article
 | langue          =en 
 | nom1            =O. Demirörs, N. Rafraf, M. M. Tanik 
 | titre           =Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions
 | périodique      =[[Journal of Recreational Mathematics]]
 | volume          =24 
 | année           =1992
 | pages           =272-280 
 | url texte       = 
 | consulté le     = 
}}
</ref>.
=== Les carrés latins ===
{{Article détaillé |Carré latin}}

=== Les problèmes d'échecs ===
{{Article détaillé |Problème d'échecs }}

== En informatique ==
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 [[algorithme génétique|algorithmes génétiques]].

Le plus souvent, il est employé comme exemple d'un problème qui peut être résolu avec un [[Algorithmique|algorithme]] [[récursivité|récursif]], en exprimant qu'une solution du problème des ''n''-dames peut être obtenue, par [[raisonnement par récurrence|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 64<sup>8</sup> = 2<sup>48</sup> = {{formatnum:281474976710656}} placements possibles des huit dames, pour retirer tous ceux pour lesquels plusieurs dames se trouvent sur une même case (laissant seulement <math>A_{64}^8=64!/56! = </math> {{formatnum:178462987637760}} [[arrangement]]s possibles) ou pour lesquels des dames se menacent mutuellement.

Au regard de la [[Théorie de la complexité (informatique théorique)|complexité algorithmique]], 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 8<sup>8</sup> = 2<sup>24</sup> = {{formatnum:16777216}} placements possibles.

Il est possible de faire beaucoup mieux que cela. Par exemple, un programme de [[Algorithme de parcours en profondeur|recherche en profondeur]] examinerait seulement {{formatnum:15720}} 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 le placement 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 {{formatnum:1000000}} × {{formatnum:1000000}} cases) en moins de 50 étapes en moyenne{{Référence nécessaire}}.

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.

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 et références ==
=== Notes ===
{{Références|groupe=note|colonnes=1}}

=== Références ===
{{Références|colonnes=1}}

== Annexes ==
=== Bibliographie ===
* {{ouvrage|prénom=Édouard |nom=Lucas|lien auteur1=Édouard Lucas|titre=Récréations mathématiques|volume=1|année=1882|éditeur = Gauthier Villars|chap=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}}.

=== Articles connexes ===
* [[Jeu mathématique]]
* [[Programmation par contraintes]]

=== Lien externe ===

* {{en}} [http://rosettacode.org/wiki/N-queens_problem N-queens problem] sur [[Rosetta Code]]
* {{en}} [https://www.csplib.org/Problems/prob054/ 054: N-Queens] sur [https://www.csplib.org/ CSPLib]

{{Portail|échecs|mathématiques|jeux|informatique}}

{{DEFAULTSORT:Huit dames, Probleme des}}
[[Catégorie:Mathématiques récréatives]]
[[Catégorie:Problème d'échecs]]
[[Catégorie:Problème algorithmique]]
[[Catégorie:Combinatoire]]