Ce petit exercice de logique occupe l’esprit des plus grands mathématiciens depuis 150 ans. L’énoncé est simpliste : il faut poser 8 reines sur un échiquier sans qu’elles ne s’attaquent entre elles. Un jeu simple donc, et les premières combinaisons se trouvent assez facilement quand on connaît, même de loin, le monde des échecs. Mais le reste du problème s’avère bien plus compliqué. Au point que le nombre total de combinaisons vient d’être découvert par le mathématicien Michael Simkin.
Dans sa démonstration il explique ainsi qu’il existe 92 solutions possibles pour répondre à ce problème, pas une de plus. Mais l’ancien élève d’Harvard ne s’arrête pas là. En effet, si la variante la plus connue du problème des reines se pose sur un échiquier classique de 64 cases (8 par 8), avec huit reines donc, d’autres formats de plateaux, plus exotiques, sont également admis par l’énoncé. L’idée est ainsi de placer 1000 milles reines sur un hypothétique échiquier de 1000 cases par 1000, ou 100 sur un échiquier de 100 par 100…
Difficile alors de tester toutes les options une à une. C’est là que le talent mathématique de Simkin rentre en compte. Le doctorant explique ainsi que pour un nombre n de reines, il existe (0.143n)n compositions. Une solution universelle qui vient résoudre ce problème. Si cette découverte ne révolutionnera surement pas grand chose, elle permet d’étendre un peu plus nos connaissances mathématiques.
Un problème historique des échecs
L’énigme des huit reines est apparue pour la première fois en 1848, dans un magazine allemand dédié aux échecs. Dès 1869 le problème devient très populaire et passionne aussi bien les curieux que les plus grands joueurs d’échecs.
Depuis des générations de mathématiciens, aidés d’ordinateurs de calculs plus puissants les uns que les autres, ont cherché la solution tant convoitée. Après 150 ans de recherche, Simkin vient de clore la discussion autour de ce problème.
Aujourd’hui encore les mathématiques regorgent de problèmes en tout genre, dont beaucoup n’ont jamais été résolu. Les plus connus sont surement les Problèmes du millénaire, sept questions mathématiques toujours sans réponse. Chaque découverte est récompensée par une prime d’un million de dollars, remise par l’institut de mathématiques Clay. Sur ces sept énigmes, seule la conjecture de Poincaré a été résolue à ce jour.
Parmi ces sept problèmes, Le problème dit “P=NP” est reconnue par le monde scientifique comme le plus accessible de tous. Avec un énoncé simple, il est un fondement de l’informatique théorique et de très nombreuses conjectures ont déjà été émises à son sujet. Pour beaucoup de mathématiciens ce problème est la clé de voute des sept problèmes du millénaire, et s’il était finalement prouvé que P=NP alors les autres problèmes devraient se trouver rapidement à leur tour. Si au contraire la conjecture P=NP se révèle incorrecte, c’est tout un pan des mathématiques qui serait à remettre en question.
🟣 Pour ne manquer aucune news sur le Journal du Geek, abonnez-vous sur Google Actualités. Et si vous nous adorez, on a une newsletter tous les matins.
“… seule la conjecture de Poincaré, aussi appelée problème de “P=NP” a été résolue à ce jour…”
…. et s’il était finalement prouvé que P=NP alors …”
Du coup il est résolu le problème ou pas ? C’est pas très clair le dernier chapitre.
L’ensemble de l’article n’est pas clair. On parle des 7 problèmes du millénaire. On dit qu’un seul a été résolu. Puis ensuite on parle des 5 problèmes restant. Il faudrait savoir…
L’article doit être entièrement réécrit.
En France, il faudrait savoir qu’on dit Dame et non pas Reine. Celui qui a écrit l’article ne sait donc pas jouer aux Échecs.
Bonjour,
Avez-vous fait le calcul? Ça ne fonctionne pas pour 8 reines.
Une simple recherche permet de découvrir que cette approximation, car c’en est une, ne fonctionne qu’avec un n très grand ( au moins 50)….
Bonne journée
Pour répondre à Sosh, la conjecture de Poincaré et P=NP sont deux problèmes distincts. La conjecture a été démontrée en 2003 par Perelman (qui a en outre refusé le million de dollars et la médaille Fields qui lui étaient attribués pour cette démonstration). On l’appelle d’ailleurs désormais le théorème de Perelman.
@Jacti, tout l’article il ne faut rien exagérer mais les deux derniers paragraphes, qui n’ont en outre pas grand chose à voir avec le problème des 8 reines, méritent sans doute relecture et correction.
Article bâclé
Le but de cet article est de faire un titre : l’information apporté (?) n’a pas voix au chapitre ici. Son seul intérêt est de donner le nom du matheux : Simkin. Une recherche rapide sur “simkin 8 queens problem” donne le résultat “A lower bound for the $n$-queens problem – arXiv” : la formule ne donne qu’une borne inférieure et si on est intéressé google donne des références (l’article de Quanta Magazine par exemple).
P=PNn’ est pas la conjoncture de Poincaré. Mais il font tous les deux parties des problème du millénaire.
Et l’équation donnée est très bancale car pour 4 reines ça donne 0 possibilité alors qu’en réalité il y en a deux…
Si n=1 alors p=np
Surtout ne me remerciez pas, c’était un vrai plaisir quand je peux rendre service…
Tellement déçu de lire des affirmations fausses -_- le 0,143n puissance n n’est même pas valable pour l’exemple des 8 reines (et de loin).
Perdu mon temps, le rédacteur ne s’est pas foulé
Bonjour Aless, je pense que l’équation n’est pas linéaire. Cela fonction donc pour les grands nombres seulement …
(0,143*8) puissance 8 , ne fait pas 92
Bonjour Aless, je pense que l’équation n’est pas linéaire. Cela fonctionne seulement donc pour les grands. La bonne question est à partir de quand est-ce que cette aproximation commence à fonctionner
En optimisation, les problèmes sont classés des problèmes P et des problèmes NP et d’autres genres ..
Une fois vous avez su de quel genre est le problème vous trouvez le cheminement de la résolution et sa complexité…
Les commentaires sont finalement plus intéressants que l’article