← Retour au blog

Le problème des huit dames : histoire, 92 solutions et part réelle de Gauss

Prends huit dames et un échiquier vide. Peux-tu les poser toutes les huit sans qu'aucune ne puisse en prendre une autre, ni en ligne, ni en colonne, ni en diagonale ? La question a l'air d'un passe-temps de salon. Elle a pourtant occupé un compositeur de problèmes d'échecs, un collaborateur d'un journal de Leipzig, Gauss lui-même, puis, cent vingt ans plus tard, deux informaticiens qui en ont fait un exemple d'école. Voici son histoire, avec ce qu'on sait vraiment et ce qu'on a souvent raconté de travers.

Jouer à Échec Royal Les règles des échecs

Une question posée en 1848

Le problème est publié pour la première fois en 1848 par Max Bezzel, compositeur de problèmes d'échecs, dans la revue mensuelle de la Société d'échecs de Berlin, la Schachzeitung (devenue en 1872 la Deutsche Schachzeitung). Il signe d'un pseudonyme, « Schachfreund », l'ami des échecs. Bezzel pose la question sans donner la réponse : combien y a-t-il de façons de placer les huit dames ?

Deux ans plus tard, Franz Nauck reprend le problème dans l'Illustrirte Zeitung de Leipzig. Selon T. B. Sprague, qui a reconstitué la chronologie devant la Société mathématique d'Édimbourg en 1899 à partir des extraits réunis par August Pein, Nauck annonce d'abord 60 solutions le 1er juin 1850, puis le bon nombre, 92, en septembre. Il donne la liste, mais ne démontre pas qu'il n'en existe pas d'autres.

La part réelle de Gauss

On lit souvent que Carl Friedrich Gauss a inventé ce problème, ou qu'il l'a résolu le premier. C'est faux, et c'est même devenu un cas d'école : en 1977, Paul Campbell lui a consacré un article de la revue Historia Mathematica au titre explicite, « Gauss et le problème des huit dames : une étude en miniature de la propagation d'une erreur historique ». Dès 1899, Sprague relevait que les affirmations de Glaisher et de Rouse Ball, pour qui la première solution venait de Gauss, « paraissent erronées » (en anglais : « appear to be erroneous »).

Ce que Gauss a réellement fait se lit dans sa correspondance avec son ami l'astronome H. C. Schumacher, publiée en 1865. D'après les extraits rapportés par Sprague :

Gauss n'a donc ni posé le problème, ni trouvé le premier les 92 solutions. Son apport est ailleurs. Il remarque que le problème peut s'énoncer sans échiquier, comme une question sur les nombres. Numérote les colonnes de 1 à 8 et note, pour chacune, la rangée de sa dame : tu obtiens un ordre des chiffres 1 à 8 (une seule dame par rangée et par colonne). Ajoute à chaque chiffre son numéro de colonne : tous les totaux doivent être différents. Ajoute-lui ensuite 8, 7, 6... jusqu'à 1 : là encore, tous différents. Ces deux conditions disent simplement que deux dames ne partagent jamais une diagonale. Il décrit aussi une méthode d'essais systématiques, colonne après colonne, en abandonnant un début dès qu'il bloque. Le survol de Bowtell et Keevash (2021) note, d'après Campbell, que cette reformulation ne l'a semble-t-il mené ni au dénombrement complet, ni à une preuve.

Une solution sur l'échiquier

Voici la solution que Sprague donne en premier et sur laquelle il illustre la règle de Gauss : en notation des échecs, a1, b5, c8, d6, e3, f7, g2, h4. Lue en chiffres, colonne par colonne, c'est 15863724.

Vérifie la règle de Gauss : 1+1, 5+2, 8+3, 6+4, 3+5, 7+6, 2+7, 4+8 donnent 2, 7, 11, 10, 8, 13, 9, 12, tous différents. C'est aussi la toute première solution qu'on rencontre si l'on essaie les colonnes de gauche à droite en commençant chaque fois par la rangée la plus basse.

92 solutions, mais seulement 12 vraiment différentes

Une solution en donne d'autres : tourne l'échiquier d'un quart de tour, d'un demi-tour, de trois quarts de tour, ou regarde-le dans un miroir, et les dames ne se menacent toujours pas. Une solution produit ainsi jusqu'à 8 variantes. En regroupant les 92 solutions par familles de variantes, on trouve 12 solutions fondamentales.

Le compte ne tombe pas juste (12 × 8 = 96) parce qu'une seule des douze est symétrique : un demi-tour la laisse identique. Elle n'a donc que 4 variantes, et 11 × 8 + 1 × 4 = 92. Sprague la qualifie de « centrique » : la voici.

Tu peux vérifier la symétrie : la dame en a3 a pour image, après un demi-tour, la case h6, où se trouve une autre dame, et ainsi de suite pour chaque paire. Nous avons recompté ces chiffres avec un petit programme qui passe en revue tous les placements possibles, une dame par colonne : il retrouve bien 92 solutions, 12 familles, dont une seule de 4 variantes.

Reste la preuve. En 1874, Siegmund Günther propose une méthode fondée sur les déterminants, et J. W. L. Glaisher la perfectionne dans le Philosophical Magazine pour démontrer qu'il n'y a pas plus de 92 solutions. La même année, Emil Pauls le démontre aussi dans la Deutsche Schachzeitung, et va plus loin, comme on va le voir.

Et sur un échiquier de n cases de côté ?

La question se généralise : combien de façons de placer n dames sur un échiquier de n × n cases ? Les sources attribuent cette généralisation à des auteurs différents (Nauck, ou Lionnet en 1869). Pauls montre en 1874 qu'il existe au moins une solution pour toute taille à partir de 4. Il n'y en a aucune sur les échiquiers de 2 et de 3 cases de côté.

Côté de l'échiquierSolutionsSolutions fondamentales
421
5102
641
7406
89212
935246
1072492
112 680341
1214 2001 787

Note la curiosité du 6 × 6, qui a moins de solutions que le 5 × 5. Ensuite le nombre explose, et les valeurs exactes connues ont été obtenues par calcul, taille par taille. En 2016, le projet Q27 (Thomas Preußer et ses collègues) a ainsi obtenu le total pour un échiquier de 27 cases de côté. En 2021, Michael Simkin a montré que, pour les grands échiquiers, le nombre de solutions se comporte comme (0,143 × n) puissance n, à un facteur près qui devient négligeable dans l'exposant.

Le cas d'école du retour sur trace

Le problème connaît une seconde vie en 1971, quand deux pionniers de l'informatique le choisissent comme exemple pour enseigner la façon de construire un programme.

En avril 1971, Niklaus Wirth publie dans les Communications of the ACM « Program Development by Stepwise Refinement » (le développement de programme par raffinements successifs). Tout l'article est bâti sur les huit dames, avec cette note de bas de page : « This problem was investigated by C. F. Gauss in 1850 » (Gauss s'est penché sur ce problème en 1850). Wirth compare trois façons de chercher :

Cette technique, écrit Wirth, s'appelle backtracking, en français le retour sur trace. Il précise que ses deux programmes trouvent les 92 solutions en testant des cases 15 720 fois. Notre script, qui suit la même méthode, retombe exactement sur 876 et sur 15 720.

En août 1971, Edsger Dijkstra consacre lui aussi un chapitre aux huit dames dans son texte A Short Introduction to the Art of Programming (EWD 316). Il y écrit que l'algorithme final illustre une technique « so general that it has a well-established name: it is called "backtracking" » (si générale qu'elle porte un nom établi : le retour sur trace), et recommande au lecteur de bien la connaître, parce qu'elle s'applique à une foule de problèmes en apparence très différents. Son programme, précise-t-il, produit 92 configurations.

Le problème est resté depuis un exemple courant pour illustrer des techniques de programmation, comme le rappelle le survol de Bowtell et Keevash. Et la méthode de Wirth et Dijkstra ressemble beaucoup à celle que Gauss décrivait à Schumacher : selon Sprague, Gauss traçait sur du papier quadrillé ou une ardoise une croix sur la case supposée occupée par une dame, un zéro sur chaque case qu'elle interdit, puis effaçait au fur et à mesure les marques devenues inutiles.

Chronologie

DateÉvénement
1848Max Bezzel (« Schachfreund ») pose la question dans la Schachzeitung de Berlin.
1er juin 1850Franz Nauck annonce 60 solutions dans l'Illustrirte Zeitung de Leipzig.
Septembre 1850Gauss écrit à Schumacher : 76, puis 72 solutions. Nauck publie les 92.
1874Günther et Glaisher : la méthode des déterminants, et la preuve qu'il y en a 92. Pauls : une solution existe pour tout échiquier à partir de 4 × 4.
1971Wirth (avril) et Dijkstra (août) en font l'exemple du retour sur trace.
1977Paul Campbell démonte l'attribution du problème à Gauss.
2016Le projet Q27 compte les solutions de l'échiquier de 27 × 27.

Ce qu'il faut retenir

Le problème repose tout entier sur la portée de la dame, la pièce qui contrôle à la fois les lignes, les colonnes et les diagonales. Pour revoir ses déplacements et ceux des autres pièces, passe par les règles des échecs, puis lance une partie d'Échec Royal et regarde, à chaque coup, quelles cases ta dame tient vraiment.

Sources

À lire aussi

← Retour au blog Jouer à Échec Royal
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →