Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Huit dames

Ce problème consiste à placer huit dames sur un échiquier de telle façon qu'elles ne sachent pas se capturer entre-elles. Autrement dit, deux dames ne peuvent partager la même colonne, rangée ou diagonale.

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

Historique

En 1850, Franz Nauck énonce la forme généralisée de ce problème : placer n dames sur un échiquier n sur n. Au fil du temps, plusieurs mathématiciens, dont Gauss s'y sont attaqué. En 1874, S. Gunther a proposé une méthode de résolution basée sur les déterminants. J.W.L. Glaisher a raffiné son approche.

Solutions

Exemple de solution

À partir des douze solutions distinctes, on peut en former nonante-deux par le biais de rotations et de symétries axiales.

Variantes

Pièces différentes

Trente-deux cavaliers, quatorze fous ou seize rois peuvent être disposés sur un échiquier traditionnel, sans oublier les échecs féériques.

Échiquiers différents

Polya a étudié le « N-dames » sur un échiquier toroïdal. D'autres formes ont été abordées, comme les échiquiers à tridimentionnels.

Domination

Nombre minimal de dames nécéssaires au contrôle de toutes les cases d'un échiquier NxN. Pour un « 8x8 », il vaut cinq.

Nine queens problem

Placer neuf dames et un pion sur un échiquier classique, en évitant que les dames ne puissent se prendre.

Carré magique

En 1992, Demirörs, Rafraf et Tanik ont publié une méthode de conversion de carrés magiques en solutions N-dames, et réciproquement.