Le problème mathématique de la reine des échecs qu'un scientifique de Harvard a résolu après 150 ans sans solution

Il est très probable que lorsque le joueur d'échecs allemand Max Bezzel a conçu le problème des huit dames en 1848, il n'a jamais imaginé les tournures que prendrait son approche.

Il a finalement donné lieu au problème des reines, qui a poussé de nombreux mathématiciens (et ordinateurs) à se creuser la tête pour trouver une solution.

"En fait, Bezzel aurait aimé étudier les mathématiques, mais ses amis le lui ont déconseillé, 'parce que les perspectives pour un mathématicien en Bavière étaient terribles à l'époque'", écrit Hans Siegfried dans une brève biographie.

• "En tant que femme noire dans le domaine des STEM, je suis utilisée pour des séances de photos"
• Quatre secrets incroyables révélés par le décryptage de l'écriture de tablettes vieilles de 5 000 ans
• Qu'est-ce que la théorie de la panspermie et que dit-elle sur la possibilité que l'univers regorge de vie ?

Il devient avocat, mais n'abandonne pas pour autant sa passion pour les échecs et les mathématiques. C'est ainsi que naît le célèbre problème de la pièce la plus puissante de l'échiquier.

Un nouveau chapitre sur le problème des n-reines a été écrit par quelqu'un qui avoue ne pas être très bon aux échecs.Le 21 janvier, The Harvard Gazette, l'organe de presse officiel de l'université de Harvard, rapporte qu'un de ses mathématiciens, Michael Simkin, a "largement résolu un problème d'échecs vieux de 150 ans".

Il n'y a aucune certitude quant à la date à laquelle le problème des n-reines a été posé pour la première fois, bien que tout porte à croire que c'était avant 1869.

BBC World s'intéresse de plus près à ce problème fascinant, à son histoire et à la solution à laquelle le scientifique est parvenu après cinq ans de réflexion.

Quel est le problème ?

Bezzel "peut être considéré comme l'un des premiers maîtres d'échecs du monde", a écrit Max Lange, un autre grand joueur d'échecs allemand, dans un livre datant de 1860.

• Que sont la théorie du chaos et l'effet papillon (et comment ils nous aident à mieux comprendre l'univers) ?

Mais au-delà de son habileté au jeu, Bezzel s'est distingué en posant des problèmes ingénieux et complexes.

"C'est le côté mathématique des échecs qui le fascinait", écrit Siegfried sur le site du club d'échecs d'Ansbach.

C'est ainsi qu'il a proposé, dans une publication d'échecs, le problème de savoir de combien de façons huit dames pouvaient être placées sur un plateau de 8 x 8 cases sans qu'elles se heurtent les unes aux autres.

La reine peut avancer d'autant de cases qu'elle le souhaite de manière linéaire, soit horizontalement, soit verticalement, soit en diagonale.

L'histoire raconte que le problème est devenu si populaire que même l'extraordinaire mathématicien Carl Friedrich Gauss a essayé de le résoudre.

Mais c'est Franz Nauck, en 1850, qui a trouvé la solution : les huit dames peuvent être disposées de 92 façons.

C'est la première version du problème qui s'est généralisé sous le nom de problème des n-reines et que Simkin explique à la BBC Mundo comme suit :

"Supposons que n soit un nombre naturel, comme 1,2,8,100 ou un million. Maintenant, imaginez un échiquier avec n lignes et n colonnes.

• Les scientifiques qui croient que l'univers n'a pas de commencement

Combien de façons y a-t-il de placer n reines sur le plateau de sorte que deux reines ne se menacent pas l'une l'autre ?

En d'autres termes, combien de façons y a-t-il de placer n reines sur le plateau de manière à ce qu'il y ait une reine par ligne, une reine par colonne et pas plus d'une reine sur chaque diagonale ?

Le défi l'a captivé.

Le temps était venu pour les reines

Pour M. Simkin, l'approche présente de "belles caractéristiques", elle peut être expliquée rapidement à presque tout le monde, "même aux non-mathématiciens", ce qui est "inhabituel" lorsqu'on s'attaque à des problèmes de ce type.

Il souligne qu'il s'agit d'un exemple de "théorie de la conception combinatoire" et, compte tenu des progrès de la combinatoire probabiliste, il lui a semblé que "c'était le bon moment pour s'attaquer au problème des reines".

Il dit qu'il n'a jamais décidé de se concentrer sur le problème avant de savoir qu'il l'avait résolu.

Il s'est alors empressé de l'écrire, et le résultat a été publié en juillet 2021, dans l'article académique The number of n-queens configurations.

"Le problème me trottait dans la tête depuis environ cinq ans, mais je n'avais pas beaucoup avancé et je me concentrais sur d'autres projets.

Après avoir obtenu son doctorat en 2020, il a déménagé avec sa famille d'Israël à Boston pour occuper un poste postdoctoral à Harvard.

• La théorie des cordes ou comment comprendre l'univers à partir des "mathématiques de la musique" de Pythagore

En pleine pandémie, sans beaucoup d'occasions de socialiser, les reines lui font un nouveau clin d'œil.

"La majeure partie du travail consistait simplement à apprendre les nouvelles techniques de la combinatoire probabiliste", sans être pleinement conscient que leur apprentissage permettrait de résoudre le problème. "C'est venu plus tard.

Tout en réalisant qu'il était possible d'"attaquer le problème", il a dû "se battre pour régler de nombreux détails techniques" afin de pouvoir écrire et publier "la preuve".

L'instant eurêka

Le mathématicien explique que le moment "eurêka" s'est produit lorsqu'il a réalisé "la nécessité de comprendre où les dames "vivent" sur l'échiquier", alors qu'il descendait la montagne Wachusett dans le Massachusetts.

Il était monté avec sa femme et sa fille, mais au moment de redescendre, la fille était trop fatiguée et Simkin est parti vers la voiture.

"En marchant seul et en réfléchissant, j'ai réalisé que le principal obstacle des tentatives précédentes était de supposer que les reines étaient réparties de manière égale sur l'échiquier", explique-t-il.

"Et en réalité, elles ne le sont pas."

Il a "enfin" compris que la clé pour compter le nombre de configurations n-queen est d'abord de comprendre comment elles " se présentent ".

"Les dames sont-elles réparties uniformément sur le plateau ? Sont-elles regroupées au milieu, dans les coins, sur les côtés ?"

"Pour chaque modèle possible de placement des dames sur l'échiquier, j'ai calculé le nombre de configurations dans lesquelles les dames correspondent à ce modèle. De cette façon, le problème devient : quel est le modèle qui permet le plus grand nombre de placements ?"

"C'est ce que les informaticiens appellent un problème d'optimisation convexe. En particulier, vous pouvez utiliser un ordinateur pour le résoudre."

• Ces Kenyans qui aident des étudiants occidentaux à tricher
• Ces scientifiques qui prétendent avoir découvert "la formule mathématique de la forme des œufs"

La solution

Simkin a calculé que pour des échiquiers immenses (n par n cases) et avec de nombreuses reines, il existe environ (0,143n)^n façons de placer les reines sans qu'aucune d'entre elles ne soit menacée.

"Supposons que nous voulions savoir combien de configurations pour 1 000 000 de reines il y a", explique le chercheur.

Autrement dit, nous voulons déterminer le nombre de façons dont 1 000 000 de dames peuvent être placées sur un plateau de 1 000 000 x 1 000 000 (cases) sans s'attaquer les unes aux autres.

Pour calculer ce nombre, qui est une approximation, nous multiplions 1 000 000 par 0,143 et le résultat, 143 000, est élevé à la puissance de 1 000 000.

" En d'autres termes, multipliez 143 000 par lui-même un million de fois. Le résultat est un très grand nombre, avec environ cinq millions de chiffres."

Cela correspondrait approximativement au nombre de configurations.

• L'étudiante qui a résolu une équation mathématique vieille de 50 ans
• Des scientifiques percent les mystères du plus ancien "ordinateur" du monde

Vous voulez regarder un chiffre plus petit ? Prenons 1 000.

Dans une interview accordée à BBC Mundo, Jesús Fernando Barbero, mathématicien et chercheur au Consejo Superior de Investigaciones Científicas d'Espagne, a effectué le calcul en utilisant l'équation de Simkin.

Si l'on veut savoir approximativement combien de configurations il y a pour 1 000 reines, on met 1 000 à la place de n :

0,143 x 1000= 143 et le porter à 1 000.

Le professeur a utilisé son ordinateur et voici le résultat qu'il a obtenu :

"Cela me donne un nombre énorme, plus de 2 000 chiffres, mais très proche de la valeur réelle du nombre de configurations possibles pour une carte de taille 1000x1000".

"Une percée"

Avec l'équation finale de Simkin, on arrive à un résultat approximatif, ce n'est pas le nombre exact de configurations, mais c'est le chiffre le plus proche du nombre réel que l'on puisse obtenir jusqu'à présent.

Il souligne lui-même que "pour des problèmes de ce type, il est inhabituel d'avoir une solution exacte".

Pour Barbero, "c'est un grand pas en avant" en ce qui concerne l'approche n-queen.

"Ces problèmes peuvent avoir des énoncés très simples, mais ils peuvent être horriblement compliqués.

"Le problème était bloqué, vous aviez réussi à comprendre comment le résoudre exactement jusqu'au numéro 27."

"Ce qu'il (Simkin) a trouvé, c'est une procédure pour donner une expression qui, sans être exacte, fait une erreur qui est faible".

"Et c'est satisfaisant : on passe soudain de ne rien savoir du comportement du nombre de solutions, de ce problème de reines pour les grandes valeurs, à avoir une idée assez précise en termes quantitatifs du nombre de configurations possibles pour un plateau de taille arbitraire."

• La physique peut-elle prouver l'existence de Dieu ?
• L'astucieux système de numérotation utilisé en Europe pendant des siècles... qui a ensuite été entièrement oublié

"En ce sens, le problème est résolu, ce n'est pas une solution définitive, on pourrait aspirer à avoir une formule exacte qui aurait la propriété fantastique qu'en donnant la taille du plateau, on me donnerait le nombre exact de configurations de reines que je peux mettre".

Mais s'il est théoriquement possible de s'approcher d'une réponse beaucoup plus précise, la réalisation de Simkin est saluée par les connaisseurs.

"En gros, il l'a fait avec une précision que personne n'avait atteinte auparavant", a déclaré Sean Eberhard, chercheur postdoctoral à l'université de Cambridge, dans un article publié dans la revue Quanta. C'est "aussi réaliste qu'on peut l'espérer".

Selon M. Simkin, si la solution a pris "autant de temps", c'est parce qu'elle s'appuie sur des avancées récentes dans le domaine des mathématiques connu sous le nom de combinatoire probabiliste, notamment en ce qui concerne l'analyse des algorithmes informatiques aléatoires.

Pourquoi est-ce important ?

"En raison des méthodes qu'il (Simkin) a dû mettre au point pour résoudre un problème dont on savait si peu de choses", explique M. Barbero.

"Les méthodes peuvent avoir une application en dehors du contexte dans lequel elles ont été conçues, et on ne sait jamais quels problèmes elles peuvent résoudre, même s'il n'y a pas toujours de garantie qu'elles fonctionnent.

Pour M. Simkin, l'importance est due à un mélange de raisons :

"La principale est que faire des mathématiques est la combinaison de la créativité, dont vous avez besoin pour générer de nouveaux arguments, et de la rigueur, qui signifie qu'une fois que vous avez prouvé un résultat, ce que vous avez en main est un morceau de vérité absolue. Il ne peut être réfuté.

Mais il y a aussi le fait que le problème des n-reines "améliore notre compréhension des algorithmes aléatoires, qui sont utilisés dans presque toutes les applications, par exemple dans l'apprentissage machine ou l'apprentissage automatique".

Et il existe également des liens avec d'autres domaines, comme la conception de circuits.

"Que diriez-vous à quelqu'un qui voudrait prendre le relais de votre main et chercher une réponse encore plus précise ?

"Bonne chance ! Faites-moi savoir comment vous vous en sortez. Il serait très intéressant de voir quelles nouvelles idées seraient nécessaires pour améliorer les paramètres."

Si vous avez besoin de conseils, le mathématicien a résumé ce qu'il utilise : analyse des algorithmes aléatoires, combinatoire probabiliste, entropie, analyse fonctionnelle et optimisation convexe.

Et bien qu'il affirme être un "mauvais" joueur d'échecs et qu'il va se reposer des n-queens pour le moment, Max Bezzel serait certainement très fier de lui.