Un échiquier, huit dames et une contrainte, voilà tout ce que requiert le problème des huit dames. Pourtant, il continue à être étudié depuis plus de 150 ans. Suivons les traces d’un des plus grands mathématiciens pour dévoiler ses secrets.
Un problème bien spécial
Le problème des huit dames a été publiquement posé pour la première fois en 1848 par Max Bezzel (1824-1871) dans la revue allemande Schachzeitung (la revue des échecs). Il a été ensuite repris à maintes reprises dans plusieurs revues d’échecs et autres journaux.
Le problème des huit dames
Combien de façons y a-t-il de placer huit dames sur un échiquier sans qu’elles se menacent mutuellement ?
Une dame se déplace sur l’échiquier le long des diagonales, des colonnes et des rangées (voir figure 1).
Une dame en menace une autre si elle peut atteindre la case que l’autre occupe (voir figure 2).
S’il est (relativement) facile de trouver une solution, comment s’assurer de toutes les trouver ? Si vous avez un échiquier sous la main, c’est un bon moment pour déposer le magazine et essayer !
La solution du prince des mathématiques : Gauss
Pour donner la solution de ce problème, nous suivrons l’exemple de l’astronome Heinrich Christian Schumacher (1780- 1850). Schumacher était un passionné des énigmes, des échecs, un mathématicien amateur et un correspondant assidu. Parmi ses relations épistolaires les plus distinguées se trouvait le grand mathématicien allemand Carl Friedrich Gauss (1777-1855), vers qui il se tournait souvent pour discuter de science et d’énigmes. Faisons de même ici !
Le problème apparaît dans la correspondance de Gauss et Schumacher en septembre 1850 après que Gauss eut vu le problème dans un article de Franz Nauck dans la gazette Illustrirten Zeitung de Leipzig. Nauck y annonçait 60 solutions, mais Gauss put rapidement en trouver davantage. Il incita donc son ami Schumacher à considérer le problème. Quand Nauck corrigea son erreur quelques mois plus tard et donna les 92 solutions, Gauss fournit à Schumacher une méthode pour vérifier le résultat en lui laissant le soin de finir ses calculs; dans ses mots : « Par ces tâtonnements méthodiques, il ne devrait pas être difficile de trouver les solutions à ce problème si on est prêt à y passer une ou deux heures. » L’histoire ne dit pas si Schumacher releva le défi avant sa mort, mais la méthode de Gauss vaut certainement encore la peine d’être présentée.
La voici décomposée point par point :
- Le mouvement d’une dame est l’intersection de quatre droites : une verticale, une horizontale, et deux diagonales, une Nord-Est de pente 1 et l’autre Sud-Est de pente -1.
- Il faut une et une seule dame sur chaque colonne, et une et une seule dame sur chaque rangée, donc toutes les droites verticales et horizontales doivent être distinctes.
- De ce constat, on note la position des dames par des listes de huit chiffres
\[(D_1, D_2, D_3, D_4, D_5, D_6, D_7, D_8),\]
où \(D_i\) donne la rangée de la dame sur la colonne \(i\) en comptant du bas vers le haut. Ceci assure qu’il y ait une seule dame par colonne. Lorsqu’il y a une seule dame par rangée, tous les \(D_i\) sont distincts et on nomme une telle liste une permutation des chiffres de 1 à 8. Toutes les solutions doivent être des permutations, mais toutes les permutations ne sont pas des solutions. Pour s’assurer de cela, il faut vérifier les diagonales. - Deux dames en positions \((j,D_j)\) et \((k,D_k)\) sont sur la même diagonale Nord-Est si les deux paires de coordonnées respectent la même équation \(y=x+b,\) donc si les différences \(D_j − j\) et \(D_k − k\) sont égales. Par exemple, sur la figure 2, les dames en bleu sont en position (5,4) et (8,7). Les deux sont sur la droite \(y=x−1\) puisque 7−8=−1=4−5.
Les diagonales Sud-Est suivent le même raisonnement, mais pour la droite \(y=−x+b\), donc si les sommes \(D_j+j\) et \(D_k+k\) sont égales. Encore sur la figure 2, les dames en rouge (2, 6) et (6,2) sont sur la droite \(y=−x+8\).- La condition pour qu’une permutation soit une solution est donc : toutes les sommes \(D_k +k\) doivent être distinctes pour tout \(1 \leq k \leq 8\), tout comme toutes les différences \(D_k – k.\)
Exemples : Pour la figure 3 correspondant à la permutation (6,1,5,2,8,3,7,4), tous les nombres sont différents dans la différence (A) ainsi que dans la somme (B). C’est donc une solution.
Cependant, pour l’exemple fautif de la figure 4 correspondant à la permutation (1,7,4,6,2,8,5,3), dans la différence (C) il y a deux « 7 », donc les dames (3,4) et (5, 2) sont sur la même droite SE et dans la somme (D), il y a deux « 2 », donc les dames (4,6) et (6,8) sont sur la même droite NE. Ce n’est pas une solution.
À l’intersection des maths et des échecs
D’où vient donc cette association entre le monde des échecs et celui des mathématiques dans l’imaginaire collectif ? À regarder l’histoire, on peut comprendre ! Seulement dans les seize champions du monde depuis 1862, on retrouve deux mathématiciens professionnels : Emanuel Lasker (champion de 1894 à 1921) et Machgielis (Max) Euwe (champion de 1935 à 1937), et un ingénieur et informaticien : Mikhaël Boitvinnik (champion de 1948 à 1957, de 1958 à 1960 et de 1961 à 1963). Encore aujourd’hui, beaucoup de joueurs et de joueuses de très haut calibre ont étudié ou travaillé en mathématiques, par exemple les grands maîtres John Nunn, Thomas Ernst, Jonathan Speelman, Jonathan Mestel et Karsten Müller, pour en nommer quelques-uns, ont tous un doctorat en mathématiques.
D’autre part, le jeux des échecs, avec ses règles entourant le mouvement des pièces sur son espace de 64 cases, a inspiré au fil des années plusieurs problèmes mathématiquement riches. Au dix-huitième siècle, Leonhard Euler (1707-1783) étudia à l’aide de la théorie des graphes le tour du cavalier, un célèbre problème où on demande à faire le tour de l’échiquier avec un cavalier en visitant chaque case une et une seule fois. Le mathématicien allemand Ernst Zemerlo (1871-1953) quant à lui utilisa les échecs pour poser les fondements de la théorie des jeux en définissant mathématiquement le concept de position gagnante en 1913.
Vers le milieu du vingtième siècle, le jeu inspira beaucoup de mathématiciens et de mathématiciennes à appliquer leur expertise pour créer des programmes pour jouer aux échecs. Alan Turing (1912-1954) conçut, en 1948 avec un autre collègue statisticien, David G. Champernowne (1912-2000), un programme pour jouer. Fait remarquable, les ordinateurs de l’époque n’avaient pas la puissance requise pour effectuer les calculs, qui devaient donc être faits à la main. Le jeu resta longtemps un laboratoire pour tester l’intelligence artificielle. Par exemple, quand la mathématicienne et informaticienne Barbara Liskov (1939-) développa des heuristiques de recherche optimale pour sa thèse de doctorat en 1968, elle les appliqua à un programme spécifiquement créé pour jouer les fins de parties d’échecs.
- Après de longues vérifications, nous arrivons à 92 solutions que nous pouvons ensuite classer en 12 familles. Onze familles de huit solutions sont données par une solution de la famille ainsi que ses images sous les rotations de 90°, 180° et 270°, et sous les quatre réflexions par rapport aux axes vertical, horizontal et diagonaux. Une dernière famille de quatre solutions est donnée par une solution quelconque de la famille ainsi que ses images sous la rotation de 90° et sous les deux réflexions par rapport aux axes vertical et diagonal NE.Il y a en tout
\[8!=8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=40\,320\]
permutations des nombres de 1 à 8.Gauss était peut-être un peu optimiste quand il disait qu’il serait possible de tout vérifier en une heure ou deux… Mais on peut se douter que Gauss avait quelques astuces pour réduire les calculs !
Un pas en arrière, deux en avant
Disons que vous vouliez relever le défi de Gauss et trouver à la main toutes les solutions du problème des huit dames. Comme lui, vous dénicheriez certainement très vite des façons de vous économiser du travail. Par exemple, il est clair que si une permutation commence par (1,2,x,x,x,x,x,x), alors il n’y a pas de solution, peu importe les six autres dames, comme les deux premières dames sont sur la même diagonale. Déjà ainsi, vous auriez réduit de 6! = 720 le nombre de permutations à vérifier, pas mal !
Figure 5 : Algorithme de retour sur trace en images pour un échiquier 4 × 4.
- On place la première dame (1,x,x,x).
- La position (1,2,x,x) est testée et est invalide.
- On passe donc à (1,3,x,x).
- Aucune des possibilités (1,3,2,x) ou (1,3,4,x) ne fonctionne.
- On revient et on passe à (1,4,x,x).
- Alors, (1,4,2,x) passe le test, mais (1,4,2,3) non.
- On revient en arrière et il faut changer le premier choix : (2,x,x,x).
- On passe à (2,4,x,x) après avoir testé (2,1,x,x) et (2,3,x,x).
- De là on arrive à la solution (2,4,1,3) de la figure 7.
- L’algorithme continue pour (3,x,x,x) et trouvera rapidement l’autre solution (3,1,4,2), qui est une rotation de 180 degrés de celle qu’on a trouvée. Ceci donne les deux seules positions possibles.
Cela est bien, mais comment trouver et appliquer systématiquement ces heuristiques, et surtout, s’assurer de trouver toutes les solutions sans en oublier ? C’est une question communément étudiée en informatique et une des façons de la résoudre est connue sous le nom d’algorithme de retour sur trace. Le problème des huit dames est le classique par excellence pour illustrer cet algorithme.
Dans celui-ci, l’idée de l’algorithme est d’utiliser le fait qu’il faille que les \(k\) premières dames ne se menacent pas sur l’échiquier partiel \(k × n\). En pratique, au lieu de générer toutes les permutations et d’ensuite les vérifier, on les génère plutôt en plaçant une dame à la fois. La vérification se fait alors à chaque placement, seulement pour la nouvelle dame ajoutée. Si la position partielle est incorrecte, on revient en arrière et on place différemment la nouvelle dame si possible, ou on retourne à la précédente sinon. De cette façon, on ne vérifie jamais deux permutations contenant la même erreur, tout en s’assurant de bien trouver toutes les solutions.
Et pour plus grand ?
Le problème des \(n\) dames
Combien de façons y a-t-il de placer \(n\) dames sur un échiquier \(n×n\) sans qu’elles se menacent mutuellement ?
Maintenant, pour paraphraser Gauss, il suffirait à une personne qui s’y connaît un peu en programmation de seulement une heure ou deux pour écrire un algorithme de retour sur trace permettant de trouver toutes les solutions pour un échiquier \(n\times n.\) Il y a un petit problème de taille cependant. Malgré les améliorations apportées par l’algorithme, il faut tout de même vérifier un nombre considérable de positions. En fait, on ne connaît le nombre exact de solutions du problème des n dames que jusqu’à \(n = 27\). La complexité de l’algorithme est exponentielle.
On pourrait essayer de trouver de meilleurs algorithmes ou étudier plus profondément le problème pour trouver plus d’idées, mais on n’arrivera jamais à connaître la réponse pour tout \(n\). Il a été prouvé par Hsiang, Hsu et Shieh au début des années 2000 qu’il n’est pas possible de trouver une « formule » qui donnerait le nombre de solutions pour tout \(n\).
En informatique, c’est une version modifiée du problème qui est étudiée. On y demande de trouver une seule solution, plutôt que de toutes les trouver. Plusieurs algorithmes très sophistiqués ont été originellement créés à cette fin. L’intérêt de tels problèmes est d’inspirer des méthodes applicables ensuite à d’autres contextes; le résultat est moins intéressant que la manière d’y arriver.
Pour le problème des \(n\) dames, en fait, on sait depuis longtemps comment construire une solution, sans algorithme : déjà en 1873, le mathématicien amateur allemand Emil Pauls donna une construction pour \(n > 3\).
Elle n’est peut-être pas utile ailleurs que pour ce problème, mais elle est simple et élégante alors présentons-la. Elle dépend du reste de la division de \(n\) par 6.
- Pour \(n = 6k\) ou \(n = 6k + 4\). La permutation où la première moitié est constituée des nombres pairs et la deuxième des nombres impairs, soit \[ (2,4,…,n,1,3,…,n-1),\] est une solution. (La figure 7 pour \(n = 4\) en est un exemple.)
- \(n = 6k+1\) ou \(n=6k+5\). On place une dame dans le coin supérieur gauche, et on prend la solution précédente dans l’échiquier \(n–1×n –1\). (La figure 8 est un exemple pour \(n = 5.\))
- \(n = 6k+2\). C’est le cas le plus complexe, suivons-le sur la figure 9. Tout d’abord, aux deux extrémités, on place les dames (en vert) en (1, 4) et \((n, n – 3)\). Ensuite au milieu (en bleu), on place \((n/2-1,n), (n/2,2), (n/2+1,n–1)\) et \((n/2+2,1)\). Dans la partie de gauche (en rouge), on place ensuite une dame à \((i,n–2(i–1))\) pour \(i\) de \(2\) à \(n/2–2.\)Dans la partie de droite (en jaune), les dames \((j,2n–2j+1)\) pour \(j\) de \(n/2+3\) à \(n–1\).
- \(n=6k+3\). On place la solution pour \(n–1 = 6k+2\) et on ajoute une dame au coin supérieur droit comme la solution précédente n’occupe pas la grande diagonale NE.
La complexité algorithmique
Un ordinateur a une grande puissance de calcul, mais elle n’est pas illimitée. Le domaine de l’informatique s’est intéressé à définir la complexité des algorithmes par le nombre d’opérations qu’ils doivent accomplir selon la taille de la tâche. On divise les algorithmes selon le type de croissance qu’ils ont. Les meilleurs croissent lentement.
Le problème des \(n\) dames contient plusieurs exemples de complexité. D’astucieux algorithmes ont été créés afin de trouver une solution au problème en temps polynomial. Trouver toutes les solutions avec l’algorithme de retour sur trace demande un temps exponentiel. La méthode de Gauss suit un temps factoriel. Ce n’est pas la pire, la méthode par force brute dans laquelle on choisit, parmi les \(n^2\) cases de l’échiquier, \(n\) où placer les dames a un temps plus que factoriel. Pour celle-ci, le nombre de positions à vérifier est donné par la formule combinatoire :
\[ \displaystyle \begin{pmatrix} n^2 \\n \end{pmatrix} = \frac{n^2!}{n! \times (n^2-n)!}.\]
S’il est possible de résoudre ainsi le problème des 8 dames ainsi sur un ordinateur de bureau, le problème des 20 dames demanderait de vérifier plus de \(2,78\times 10^{33}\) positions, ce qui serait impossible au courant d’une vie humaine, même avec tous les superordinateurs de la planète !
Voici quelques comparaisons du nombre nécessaire de positions à vérifier selon la taille de l’échiquier pour les méthodes pour donner une idée de la croissance des différentes familles.
Conclusion
Il y a encore beaucoup à dire autour de ce problème. Si nous avons jusque là considéré seulement le problème de placer le plus grand nombre de dames possible sur l’échiquier, un autre problème, appelé « domination des dames », demande le nombre minimal de dames requis pour couvrir tout l’échiquier, c’est-à-dire que toute case de l’échiquier est menacée ou occupée par une dame.
On s’est aussi intéressé à considérer des échiquiers rectangulaires, ou même des polygones à angles droits quelconques. On peut aussi changer le pavage pour des hexagones par exemple. Plus encore, qu’arriverait-il si on changeait l’échiquier dans sa nature profonde, en le plaçant sur un cylindre, ou sur un beigne par exemple ? Un mathématicien hongrois, Georg Pólya (1887-1985), s’est intéressé précisément à cette dernière question et nous verrons dans un prochain épisode l’impact que ce nouvel échiquier a sur le problème.
Pour en s\(\alpha\)voir plus !
- RIVIN, I., VARDI, I., et ZIMMERMANN, P., The n-queens problem. The American Mathematical Monthly 101, 7 (1994), 629–639.
- WATKINS, J.J. The mathematics of chessboard problems. Princeton University Press (2004)
Pour jouer aux échecs : le site gratuit sans publicité et en logiciel libre lichess.org est un bon choix
