Vous pourriez gagner 1 million de dollars en résolvant cette énigme

jeu d'échecs

Alléchante idée que de devenir millionnaire en jouant aux échecs. A se demander pourquoi Kasparov n'a pas encore tenté sa chance. Cependant, il n'y a même pas vraiment besoin de comprendre les règles des échecs pour participer. Le hic, c'est que le casse-tête est tellement complexe qu'il faudra sans doute des milliers d'années pour en venir a bout et un algorithme sacrément costaud. 

« Le but du problème des huit dames est de placer huit dames d’un jeu d’échecs sur un échiquier de 8 × 8 cases sans que les dames ne puissent se menacer mutuellement, conformément aux règles du jeu d’échecs (la couleur des pièces étant ignorée). Par conséquent, deux dames ne devraient jamais partager la même rangée, colonne, ou diagonale. Ce problème appartient au domaine des problèmes mathématiques et non à celui de la composition échiquéenne »

Publié à l’origine en 1848, c’est un véritable défi. En effet, la reine est la pièce maîtresse du plateau, elle peut se déplacer car dans huit directions et sur une distance illimitée (dans la limite des cases s’entend). Il existe 92 manières différentes de résoudre le puzzle. De ce fait, les mathématiciens se sont dit qu’il était temps de corser un peu les choses… avec un plateau de 64 cases : 20 reines sur une carte 20 x 20. Voici le défi à relever, celui du « n-QSueens ».

Deux solutions pour gagner, soit en prouvant qu’aucun algorithme ne peut résoudre le puzzle dans un délai raisonnable, soit en développant un algorithme qui peut le résoudre rapidement. En effet dans sa version de base, problème a été résolu par les humains, mais une fois que l’échiquier impliqué augmente de taille, aucun logiciel informatique ne parvient le résoudre. Il faut ainsi concevoir un algorithme apte à résoudre ce challenge sur un plateau de 1000 cases par 1000, et seulement à ce moment, le Clay Mathematics Institute de Peterborough, dans le New Hampshire versera la somme promise. 

Tags :Sources :dailymail
Dernières Questions sur UberGizmo Help
  1. Je suis désolée, mais c’est totalement faux. D’accord, le problème est intéressant, mais en aucun cas le Clay Mathematics Institute de Peterborough ne donnera un million de dollar pour sa résolution, et ce pour plusieurs raisons. La première, et pas des moindres, est que ce problème est d’ores et déjà résolu. Deux minutes de recherche sur google auraient pu vous permettre de trouver la solution en ligne.
    Ensuite, la liste des problèmes pour lesquels le Clay Mathematics Institute de Peterborough offre 1 million de dollars est également disponible en ligne, on les appelle les « Millenium Problems » et jusqu’à peu il y en avait huit; il en reste 7, et celui auquel vous faites allusion ici est le « P vs NP problem ».

    Le problème des « n-Queen » tombe, selon moi, dans la classe des P-problem, à savoir les problèmes faciles à résoudre: il existe un algorithme pour les résoudre en temps polynomial (je n’ai pas vérifié le temps nécessaire à la résolution du problème, ceci dit).
    En revanche, le problème des « n-Queens Completion », qui est à peu près le même sauf que certaines reines sont déjà placées, tombe dans la classe des NP-Problem, à savoir les problèmes dont il est facile de vérifier une solution, mais pas facile d’en trouver une…

    Donc, pour obtenir le million de dollars, il faudrait non pas résoudre le « n-Queens Completion problem », mais créer un algorithme permettant de le résoudre EN TEMPS POLYNOMIAL. Ou bien démontrer qu’un tel algorithme n’existe pas. Dans ce cas seulement, on pourra considérer que vous aurez résolu le « P vs NP problem » et vous pourrez obtenir la récompense (en sachant que le premier – et dernier à ce jour – à avoir résolu un des huit problèmes a refusé ladite récompense…)

    Ceci n’a donc strictement rien à voir avec ce que vous dites ici, et un tout petit tour sur le site du Clay Mathematics Institute vous aurait permis rapidement de vous en rendre compte, puisqu’ils ont eux-même fait un article à ce sujet cinq jours avant le vôtre: http://www.claymath.org/events/news/8-queens-puzzle

    D’autre part, le « n-Queens problem » n’est certainement pas un « casse-tête est tellement complexe qu’il faudra sans doute des milliers d’années pour en venir a bout et un algorithme sacrément costaud ». Il est considérablement simple, je pense que n’importe quel étudiant de maths ou informatique niveau licence – master pourrait le résoudre (quoique le temps polynomial est peut-être difficile à obtenir) s’il y prenait le temps.

    Bref, si le titre est bien accrocheur (ce qui était sans doute le but), il est doublement faux; d’une part parce que résoudre ce problème ne donne pas accès au million, d’autre part parce que ça n’a considérablement rien à voir avec le jeu d’échecs. En plus de ça, il donne une vision très négative de ce que l’on sait actuellement faire au niveau mathématiques….
    Lorsqu’on publie un article, la moindre des choses est de vérifier ses infos. encore une fois, deux minutes sur google auraient évité ça. Je trouve ça vraiment dommage; et dévalorisant pour le reste de vos articles.

    1. Je trouve que vous chipotez un peu. Votre article semble plus complet mais Flo dit beaucoup de choses comme vous. Vous ramenez votre science mais on s’en fou.
      Dans votre dernière phrase, vous avez mis un point virgule en trop. Soit vous le supprimez, soit vous le laissez et enlevez le « et » ; c’est plus français… mais je chipote.

      Ce commentaire a reçu trop de votes négatifs. Cliquez ici pour voir le message.
  2. J’ai résolu ce problème il y a environ 25 ans, à l’aide d’un Atari ST, en Stos Basic.
    Temps de calcul : environ 18 heures.

    Je l’ai refait sur un PC (un des premiers pentium) il y a environ 20 ans. Temps de calcul : moins de 5 minutes.

    Je le faisais en « brute force » : en comptant un pion par ligne et en testant toutes les valeurs possibles.

    De mémoire, il y avait 64 solutions (avec toutes les symétries possibles)

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Publicité