Problème des huit dames

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 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. Simple mais non trivial, ce problème sert souvent d'exemple pour illustrer 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é). 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étrique dans une colonne mitoyenne, sauf pour les 2 qui touchent l'axe de symétrie horizontale de l'échiquier (Solution unique 5). Quatorze fous, 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èces d'échecs féeriques peuvent remplacer les dames. 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.