Un mathématicien de Harvard a pratiquement résolu un problème d’échecs vieux de 150 ans
À première vue, les échecs semblent être un jeu simple : 64 cases individuelles noires ou blanches, 16 pièces par côté, et deux concurrents en quête de conquête.
Mais si l’on creuse un peu plus, le jeu offre des possibilités incroyablement complexes, posant aux théoriciens des échecs et aux mathématiciens des défis qui peuvent rester sans solution pendant des décennies, voire des siècles.
En juillet 2021, l’un de ces défis a finalement été résolu – du moins, jusqu’à un certain point. Le mathématicien Michael Simkin, de l’université Harvard (Massachusetts), s’est attaqué au problème des huit dames (n-queens problem), qui intrigue les experts depuis qu’il a été imaginé dans les années 1840.
Si vous connaissez les échecs, vous savez que la reine est la pièce la plus puissante de l’échiquier, capable de se déplacer d’un nombre quelconque de cases dans n’importe quelle direction. Le problème des huit dames pose cette question : Avec un certain nombre de reines (n), combien d’arrangements sont possibles où les reines sont suffisamment éloignées les unes des autres pour qu’aucune d’entre elles ne puisse prendre une des autres ?
Pour huit dames sur un plateau standard de 8 x 8, la réponse est 92, bien que la plupart d’entre elles soient des variantes tournées ou réfléchies de seulement 12 solutions fondamentales.
Mais qu’en est-il de 1 000 dames sur un plateau de 1 000 x 1 000 cases ? Qu’en est-il d’un million de dames ? La solution approximative de Simkin à ce problème est (0,143n)n – le nombre de dames multiplié par 0,143, élevé à la puissance n.
La réponse que vous obtenez n’est pas précise, mais elle est aussi proche que possible de la réponse actuelle. Avec un million de reines, le chiffre obtenu est un nombre suivi de cinq millions de chiffres – nous ne le reproduirons donc pas ici.
Il a fallu près de cinq ans à Simkin pour trouver l’équation, en utilisant diverses approches et techniques, et en rencontrant quelques obstacles sur le chemin de la solution. Au final, le mathématicien a pu calculer les limites inférieures et supérieures des solutions possibles en utilisant différentes méthodes, et a constaté qu’elles correspondaient presque.
“Si vous me disiez que je veux que vous placiez vos reines de telle ou telle manière sur l’échiquier, je serais alors capable d’analyser l’algorithme et de vous dire combien de solutions il y a qui correspondent à cette contrainte”, explique Simkin.
“En termes formels, cela réduit le problème à un problème d’optimisation.”
Très tôt, Simkin et son collègue Zur Luria, de l’École polytechnique fédérale de Zurich, ont collaboré à une variante du problème des n-reines, connue sous le nom de problème torodial ou modulaire. Dans ce problème, les diagonales s’enroulent autour du plateau, de sorte qu’une reine peut se déplacer en diagonale du bord droit du plateau et réapparaître sur le bord gauche, par exemple.
Cela confère à chaque reine une symétrie d’attaque, mais ce n’est pas la façon dont fonctionne un échiquier normal : une reine dans un coin de l’échiquier n’a pas autant d’angles d’attaque qu’une reine au centre.
En fin de compte, les travaux du couple sur le problème toroïdal se sont arrêtés (bien qu’ils aient publié quelques résultats), mais Simkin a fini par adapter certains des fruits de ce travail dans sa solution finale.
Lorsque les plateaux deviennent plus grands et que le nombre de reines augmente, les recherches montrent que dans la plupart des configurations admissibles, les reines ont tendance à se rassembler le long des côtés du plateau, avec moins de reines au milieu, où elles sont exposées aux attaques. Cette connaissance permet une approche plus pondérée.
En théorie, il devrait être possible de trouver une réponse plus précise à l’énigme des n-reines, mais M. Simkin nous en a rapprochés plus que jamais, et il est heureux de transmettre le défi à quelqu’un d’autre pour qu’il l’étudie plus avant.
“Je pense personnellement en avoir fini avec le problème des n-reines pour un certain temps, non pas parce qu’il n’y a plus rien à en faire, mais simplement parce que j’ai rêvé d’échecs et que je suis prêt à passer à autre chose”, déclare M. Simkin.
L’article de Simkin sur la solution est disponible sur le serveur de préimpression arXiv.
Lire aussi : L’hypothèse de Riemann n’est toujours pas prouvée, selon le Math Institute
Source : ScienceAlert – Traduit par Anguille sous roche
