ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Problème des 8 reines

 ➔  Ce célèbre problème aurait été posé pour la première fois en 1848 dans un journal d'échecs et résolu en 1850 par le Dr. Nauck (publié dans la revue allemande "Illustrierten Zeitung"). Gauss, intéressé par cette "colle" n'aurait trouvé que 72 solutions. Source : Arthur Engel,  Mathématique et informatique , Ed. Cedic/Nathan, Paris - 1985. Voir aussi le même problème exposé par Lucas.sur le site Gallica de la BnF : Récréations mathématiques (2ème éd.) / par Édouard Lucas.

Dans le jeu d'échecs, une "reine" peut se déplacer en ligne droite sur toute ligne, colonne ou diagonale de l'échiquier. Dans le cas ci-dessous, aucune reine ne peut en "prendre" une autre. Il y a 92 possibilités.

La programmation du problème n'est pas très complexe : il suffit de procéder par essais et éliminations des cas. Mais elle peut être plus ou moins élégante. La plus belle n'étant pas la mienne, je me permets de donner celle de Arthur Engel, à ma connaissance la plus élégante, extraite de son livre cité supra.

Le principe est simple : il est clair qu'il y aura une dame et une seule par colonne et ligne. La variable d() désigne la place d'une dame à la ligne d(i) de la colonne i, l'origine du repère est en (1,1) en bas à gauche (image ci-contre).

Au départ, on place une dame en (1,1) puis on tente d'en placer une dans la colonne suivante en évitant de la mettre sur la même ligne et en utilisant cette astuce superbe pour éviter la prise en diagonale : la pente de la droite définie par d(i) et d(j) ne doit pas être 1 ou -1. D'où le très court programme :

FOR i = 1 TO 8
  d(i) = 1
  cherche:
  FOR j = 1 TO i - 1
    IF d(i) = d(j) OR ABS(d(i) - d(j)) = i - j GOTO decale
  NEXT j
NEXT i
PRINT d(1);d(2);d(3);d(4);d(5);d(6);d(7);d(8)
i = i - 1
decale:
  d(i) = d(i) + 1
  IF d(i) <= 8 GOTO cherche
   i = i - 1
  IF i <> 0 GOTO decale
END

15863724
16837425
...
82531746
83162574 : c'est la solution correspondant à l'image en tête de page.
84136275