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 cre 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.

Il devient avocat, mais n'abandonne pas pour autant sa ion 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.

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.

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.

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 ");