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.

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

Concepts associés (12)

Séances de cours associées (1)

MOOCs associés (1)

Problème des huit dames

Sudoku

thumb|Sudoku proposé par la presse. Le , est un jeu en forme de grille défini en 1979 par l’Américain Howard Garns, mais inspiré du carré latin, ainsi que du problème des du mathématicien suisse Leonhard Euler. Le but du jeu est de remplir la grille avec une série de chiffres (ou de lettres ou de symboles) tous différents, qui ne se trouvent jamais plus d’une fois sur une même ligne, dans une même colonne ou dans une même région (également appelée « bloc », « groupe », « secteur » ou « sous-grille »).

Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable.

Introduction to optimization on smooth manifolds: first order methods

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Choisir une taille d'étape MATH-512: Optimization on manifolds MOOC: Introduction to optimization on smooth manifolds: first order methods

Explore le choix d'une taille d'étape dans l'optimisation sur les collecteurs, y compris la recherche de ligne backtracking et la méthode Armijo.