Dernières nouvelles de l'homme

Difficile d’ignorer Candy Crush, difficile de ne pas y jouer et encore plus difficile de ne pas tomber dans l’addiction. C’est un jeu de bonbons virtuels. Il semble bien que ce jeu séduise plus les femmes que les hommes. Téléchargeable gratuitement sur smartphones, tablettes et Facebook, Candy Crush était joué 700 millions de fois chaque jour dans le monde en décembre dernier.

Le problème semble simple, il suffit d’aligner le plus de bonbons par 3, 4 ou 5. Chaque mouvement change la configuration du jeu, il faut donc anticiper les alignements futurs et c’est ici que l’on tombe sur un sacré problème de math. Un chercheur australien a démontré que ce problème est de la classe des problèmes NP-complets donc très complexes.

Toby Walsh, le chercheur australien a étudié le jeu et découvert qu'il faisait partie d'une classe de problèmes mathématiques dits NP-difficiles et que si on ne limitait pas la taille du tableau de bonbons ce problème devient NP-complet.

Je n’entrerai pas ici dans l’explication sur les problèmes P et NP, disons que les NP-Complets sont des problèmes aux solutions difficiles à trouver mais faciles à prouver. On peut citer, le problème du voyageur de commerce, Les problèmes de coloration de graphe, le problème du sac à dos…

Walsh se demande s'il serait possible de tirer profit du temps que les gens passent à résoudre les problèmes de Candy Crush. Les adeptes cumulent plusieurs millions d'heures de jeu. Peut-être pourrait-on en profiter pour glisser quelques problèmes NP-difficiles concrets au milieu du jeu et ainsi faire avancer les mathématiques sur un des problèmes à 1 million de dollars.