Un prix d’un million USD pour résoudre un problème d’échecs énoncé du XIXe siècle

Des spécialistes de l'Université St Andrews au Royaume-Uni encouragent des informaticiens à trouver la solution à un problème de jeu d'échecs énoncé au milieu du XIXe siècle, signale le site de l'établissement. L'Institut mathématique Clay, aux États-Unis, offre un prix d'un million de dollars à celui qui trouvera la bonne réponse.

Le «Problème des huit dames» (Eight Queens Puzzle), initialement formulé en 1850, propose de placer huit reines sur un échiquier standard de telle façon qu'elles ne puissent pas s'attaquer l'une l'autre. La version initiale du problème, c'est-à-dire sur un échiquier de 64 cases, a été résolue. Cependant, si les dimensions de l'échiquier augmentent trop, même de puissants ordinateurs ne peuvent résoudre le problème.

Ian Gent, professeur en sciences informatiques, et ses collègues lancent le défi à relever dans un article publié dans la revue Journal of Artificial Intelligence Research. Selon l'équipe, des avantages importants pourraient être retirés d'une solution du problème des huit reines placées sur un échiquier plus grand que celui à 64 cases.

Les chercheurs indiquent qu'une fois l'échiquier atteint les dimensions de 1.000 cases sur 1.000, les ordinateurs sont incapables de résoudre le problème. Selon Ian Gent, si un programme capable d'apporter une solution à ce casse-tête était conçu, il pourrait être adapté pour résoudre des problèmes importants auxquels tout le monde est confronté de façon quotidienne.