Quel utilisateur PC ne s’est pas adonné, à ses moments perdus, à une petite partie de démineur, ce petit jeu intégré aux versions successives de Windows ? Rien de tel pour tuer le temps quand le patron est de sortie... Certains sont même, paraît-il, de véritables experts en la matière : en un coup d’œil, ils arrivent à projeter mentalement la carte des mines à partir des indications fournies par les cases déjà déminées (si une case indique 3, c’est que 3 cases voisines sont piégées). Ces as du déminage doivent avoir une méthode... Si c’est le cas, toutes ces longues heures passées devant l’écran vont peut-être, enfin, être récompensées : le Clay Mathematics Institute (Massachusetts, ...tats-Unis) offre 1 million de dollars à quiconque proposera une méthode infaillible pour gagner au démineur, quelle que soit la taille de la grille.

Plus qu’un jeu : un problème

Ce défi a été lancé suite à un article paru cette année dans une revue de mathématiques (Mathematical Intelligencer). Le professeur Richard Kaye, de l’université de Birmingham (Angleterre), y démontrait qu’à grande échelle le démineur est plus qu’un jeu : c’est un véritable problème mathématique du type "P contre NP" dans le jargon spécialisé. Or ce type de problèmes est réputé insoluble : depuis 30 ans, et malgré l’utilisation d’ordinateurs puissants, aucune méthode digne de ce nom n’a pu être identifiée. Ne vous faîtes donc pas trop d’illusions. Mais ne perdez pas tout espoir non plus, car un pari du même genre a permis à un informaticien britannique de 28 ans de gagner un million de livres. Il lui a suffi pour cela d’assembler le puzzle Eternity de 209 pièces (sans motifs et aux formes géométriques particulièrement vicieuses). L’inventeur du puzzle avait lancé ce défi pour promouvoir son œuvre. Il a été contraint, paraît-il, de vendre sa maison pour payer son dû au gagnant...