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.
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 :
- le 1er septembre 1850, Gauss écrit que le nombre n'est pas 60, mais 76 ;
- le 12 septembre, il corrige : il faut descendre à 72 ;
- le 27 septembre, il rapporte que Nauck annonce désormais 92 solutions et recopie les 12 essentiellement différentes ; mais comme Nauck n'explique pas comment il s'est assuré qu'il n'y en a pas d'autres, et qu'il avait d'abord annoncé 60 à tort, Gauss juge qu'on peut encore en douter.
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'échiquier | Solutions | Solutions fondamentales |
|---|---|---|
| 4 | 2 | 1 |
| 5 | 10 | 2 |
| 6 | 4 | 1 |
| 7 | 40 | 6 |
| 8 | 92 | 12 |
| 9 | 352 | 46 |
| 10 | 724 | 92 |
| 11 | 2 680 | 341 |
| 12 | 14 200 | 1 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 :
- essayer toutes les façons de poser 8 dames sur 64 cases : 4 426 165 368 positions, environ 2 puissance 32 ;
- imposer une dame par colonne : il reste 8 puissance 8, soit 16 777 216 positions ;
- poser les dames une à une, colonne après colonne, et revenir en arrière dès qu'une dame n'a plus de case sûre. Le programme n'examine alors que 876 positions partielles avant de trouver la première solution.
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 |
|---|---|
| 1848 | Max Bezzel (« Schachfreund ») pose la question dans la Schachzeitung de Berlin. |
| 1er juin 1850 | Franz Nauck annonce 60 solutions dans l'Illustrirte Zeitung de Leipzig. |
| Septembre 1850 | Gauss écrit à Schumacher : 76, puis 72 solutions. Nauck publie les 92. |
| 1874 | Gü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. |
| 1971 | Wirth (avril) et Dijkstra (août) en font l'exemple du retour sur trace. |
| 1977 | Paul Campbell démonte l'attribution du problème à Gauss. |
| 2016 | Le projet Q27 compte les solutions de l'échiquier de 27 × 27. |
Ce qu'il faut retenir
- Le problème est posé par Max Bezzel en 1848 et les 92 solutions sont publiées par Franz Nauck en 1850 ; la preuve qu'il n'y en a pas d'autres date de 1874.
- Gauss s'y est intéressé, l'a traduit en problème de nombres et a décrit une méthode d'essais, mais il n'en est ni l'auteur ni le premier à l'avoir résolu.
- Les 92 solutions se ramènent à 12 fondamentales, dont une seule est symétrique.
- Wirth et Dijkstra en ont fait, en 1971, l'exemple type du retour sur trace.
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
- T. B. Sprague, « On the Eight Queens Problem », Proceedings of the Edinburgh Mathematical Society, séance du 10 février 1899, p. 43 et suivantes : doi.org/10.1017/S0013091500029096
- C. Bowtell et P. Keevash, « The n-queens problem », 2021, section historique et bibliographie (Bezzel 1848, Nauck 1850, Peters 1865, Campbell 1977, Glaisher et Pauls 1874, Dijkstra) : arxiv.org/abs/2109.08083
- N. Wirth, « Program Development by Stepwise Refinement », Communications of the ACM, vol. 14, n° 4, avril 1971, p. 221 à 227 : doi.org/10.1145/362575.362577
- E. W. Dijkstra, A Short Introduction to the Art of Programming (EWD 316), août 1971, chapitre 9 « The problem of eight queens » : archives E. W. Dijkstra, université du Texas
- OEIS, suites A000170 (nombre de solutions) et A002562 (solutions fondamentales), dont le calcul du projet Q27 (2016).
- Wikipédia (allemand), article Damenproblem, pour recouper Bezzel, Nauck, Gauss et Pauls.