Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème des huit dames
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.