Comment arrangeriez-vous 8 reines sur un échiquier sans qu’elles ne puissent s’attaquer entre-elles ? Et combien y-a-t-il de combinaisons possibles ? Il s’agit ici d’un problème qui date d’il y a 150 ans, une version ancienne du problème dénommé n-queens. Ce dernier problème, un chercheur postdoctoral du nom de Michael Simkin, travaillant au Center of Mathematical Sciences and Applications du Harvard University, l’a résolu, comme on peut le voir dans son article publié en juillet dernier.
Au lieu de placer 8 reines sur un échiquier standard 8 sur 8, un problème avec 92 solutions, le problème n-queens s’intéresse au nombre de possibilités pour placer n reines sur un échiquier n sur n. Par exemple, on peut choisir 15 reines sur un échiquier 15 sur 15 ou 1000 reines sur un échiquier 1000 sur 1000. La solution ? Simkin a prouvé qu’il y avait approximativement (0,143n)n configurations possibles.
Le problème original avec l’échiquier 8 sur 8 est apparu pour la première fois dans un magazine allemand sur les échecs en 1848, le problème n-queens a ensuite émergé vers 1869. Depuis, de nombreux mathématiciens ont proposé des solutions. Même si des chercheurs ont déjà utilisé des simulations informatiques pour trouver le même résultat que Simkin, l’on sait que ce dernier est le premier à l’avoir prouvé.
Selon Sean Eberhard, un chercheur postdoctoral à l’Université de Cambridge, Simkin a trouvé la solution de façon plus pointue que les autres chercheurs.
A lire aussi : Votre QI ne dépend pas de votre niveau en maths
La difficulté du problème
Selon les spécialistes, la vraie difficulté pour résoudre le problème n-queens vient du fait qu’il n’y a pas de manière évidente de le simplifier. Même sur un échiquier de petite taille, le nombre d’arrangements potentiels peut être très élevé. Les mathématiciens essaient souvent de trouver une structure de base au niveau du problème qui va permettre de diviser les calculs en de petites portions plus faciles à gérer.
Mais il semble que le n-queens n’en possède aucune.
Apparemment, l’échiquier ne possède pas de structure symétrique, ce qui pourrait simplifier le problème. C’est cette absence de structure qui a poussé Simkin, il y a 4 ans, à aller rendre visite au mathématicien Zur Luria du Swiss Federal Institute of Technology Zurich, et ainsi collaborer pour résoudre le problème. Initialement, ils ont essayé de trouver une solution au n-queens « toroïdal » qui est symétrique. Dans cette version modifiée, l’échiquier s’enroule comme un tore, c’est-à-dire que si l’on tombe à droite, on réapparait sur le côté gauche.
La symétrie de l’échiquier toroïdal a permis d’avoir une nouvelle base pour trouver une solution au problème. Toutefois, cette version réduit la liberté, ce qui a causé d’autres problèmes. Les deux mathématiciens ont alors dû s’arrêter lorsqu’ils n’ont pas pu trouver de la place pour les quelques reines restantes dans une configuration donnée.
A lire aussi : Un problème de maths résolu par un meurtrier en prison
La solution
Plus tard, Simkin s’est rendu compte que l’approche qui n’a pas fonctionné avec le problème toroïdal convenait en fait pour l’échiquier normal. Selon lui, 2 à 3 ans après avoir laissé tomber, il a réalisé que la méthode facilitait la résolution du problème classique. Simkin et Luria ont ainsi essayé de terminer leur configuration sur un échiquier classique. Ils ont trouvé qu’ils pouvaient en général réussir en ajustant certaines des pièces qu’ils avaient déjà placées.
L’absence de symétrie au niveau du problème classique est toutefois réapparue. A cause de cette limitation, Simkin et Luria ont juste fini par améliorer la limite inférieure connue du problème. Ils avaient publié ces résultats en mai dernier.
Simkin n’a pas arrêté de réfléchir au problème. Eventuellement, il a pensé qu’il pouvait adapter l’algorithme à l’environnement asymétrique de l’échiquier standard. Le chercheur a divisé l’échiquier n sur n en sections faites de milliers de cases. Puis, au lieu de spécifier exactement quels espaces avaient des reines, il a cherché à trouver combien de reines il y avait dans chaque section. Il a ensuite réutilisé les techniques qu’ils avaient employées avec Luria. Cela lui a permis de déterminer une formule pour le nombre minimal de configurations valides. Il a ensuite prouvé que cette formule était plus qu’un minimum en utilisant une stratégie connue sous le nom de « la méthode de l’entropie ».
Simkin a pu calculer le nombre maximal de configurations en cherchant le nombre d’espaces qui n’étaient pas attaqués après que la position de chaque reine additionnelle ait été révélée. Cette valeur maximale a correspondu au minimum, permettant au chercheur de conclure qu’il a pu trouver le nombre de configurations pou n-queens.