Candy Crush Saga : la difficulté du jeu scientifiquement prouvée

Qui aurait cru que classer des bonbons par couleur pouvait relever d'une grande complexité ? "Candy Crush Saga", le "jeu le plus doux", serait aussi l'un des plus addictifs et des plus compliqués, selon Tom Walsh, de l'université de Nouvelle Galle du sud. Y trouver une solution serait un énorme casse-tête, même pour un spécialiste des Mathématiques. Ainsi, le chercheur australien l'a-t-il classé dans la catégorie NP (problèmes non résolus). Selon lui , la difficulté du jeu augmente continuellement au fur et à mesure que celui-ci grandit en taille et en nombre de variantes. Dans Candy Crush, il faut ranger les bonbons par couleur, en rangées verticales et horizontales. Le nombre de mouvements et le score finale sont illimités.  

En repoussant indéfiniment les dimensions du cadre et en se demandant si on pouvait élaborer une série de mouvements donnant un certain score, Tom Walsh a abouti à reproduire un problème SAT, l' un des plus compliqués au monde, du niveau NP.

Lancé en 2012, Candy Crush compte désormais 93 millions d'adeptes via Facebook ou des applications spécifiques aux smartphones, ce qui en fait le jeu le plus populaire du monde. La Terre pullulerait-t-elle de grands mathématiciens qui s'ignorent ?