Un prix de 1 000 000 $ (773 100 £) pourrait être le vôtre si vous parvenez à résoudre ce puzzle d'échecs apparemment «simple».
Le Clay Mathematics Institute (CMI) en Amérique offre le prix en argent à quiconque peut proposer un programme informatique pour résoudre un problème connu sous le nom de Casse-tête des reines, inventé pour la première fois en 1850, qui est une forme de ce qu'on appelle un Problème P vs NP.
Le puzzle semble assez simple; placez huit reines sur le plateau de manière à ce qu'aucune reine ne puisse s'attaquer. La torsion, cependant, est que les chercheurs veulent que l'algorithme fonctionne sur un échiquier carré de 1 000 par 1 000. Au fur et à mesure que le nombre de cases augmente, le nombre de reines que vous devez placer augmente également.
Selon les estimations actuelles, placer 1 000 reines sur un plateau carré de 1 000 sur 1 000 pourrait prendre des milliers d'années - en raison du nombre considérable de possibilités à envisager.
Tout algorithme capable de résoudre rapidement le casse-tête serait également capable de casser les mesures de sécurité en ligne les plus strictes, ont déclaré les chercheurs, car il serait incroyablement puissant.
C'est un exemple d'un problème du prix du millénaire, dont il y en a sept au total. Ces énigmes ont été annoncées lors d'une réunion en 2000 et on dit qu'elles représentent les problèmes les plus difficiles auxquels sont confrontées les mathématiques. Le CMI a déclaré que c'était pour montrer aux gens qu'il y avait encore de nombreuses questions sans réponse en mathématiques.
Le conseil d'administration de CMI a désigné un fonds de prix de 7 millions de dollars pour les solutions aux problèmes, avec 1 million de dollars alloués à la solution de chaque problème. Le premier d'entre eux a été résolu en 2003 par Grigori Perelman, un mathématicien russe, mais il a décliné le prix.
L'Université de St Andrews a maintenant lancé un défi à quiconque pour résoudre ce puzzle à l'aide d'un ordinateur.
Ian Gent, professeur à l'Université de St Andrews, a eu l'idée après avoir été mis au défi par un ami Facebook de résoudre lui-même le puzzle d'échecs. Lui et ses collègues, le Dr Peter Nightingale et le Dr Christopher Jefferson, ont tenté d'écrire eux-mêmes un programme informatique.
Leurs solutions utilisent le "backtracking" - un algorithme utilisé dans la programmation où chaque option possible est examinés puis "reculés" jusqu'à ce que la solution correcte soit trouvée - et leurs idées sont décrites dans un papier, publié dans le Journal de recherche sur l'intelligence artificielle.
Cependant, dès que l'échiquier est devenu assez grand - 1 000 cases sur 1 000 - l'algorithme n'a pas pu faire face. Ces problèmes sont si difficiles pour les programmes informatiques car il y a trop d'options à considérer et cela peut prendre de nombreuses années.
"Si vous pouviez écrire un programme informatique capable de résoudre le problème très rapidement, vous pourriez l'adapter pour résoudre bon nombre des problèmes les plus importants qui nous affectent tous au quotidien", a déclaré le professeur Gent. "Cela inclut des défis triviaux comme travailler sur le plus grand groupe de vos amis Facebook qui ne le font pas connaissent les uns les autres, ou très importants comme casser les codes qui gardent toutes nos transactions en ligne sûr."
"Dans la pratique, personne n'a jamais été près d'écrire un programme capable de résoudre le problème rapidement", a déclaré le Dr Nightingale. "Donc, ce que nos recherches ont montré, c'est que - à toutes fins pratiques - cela ne peut pas être fait."
