Derrière ce jeu tout simple en apparence se dissimulent des problèmes calculatoires difficiles. C'est probablement pourquoi Candy Crush est aussi addictif.
Il paraît qu'en ville, on n'est jamais à plus de quelques mètres d'un rat. Mais de nos jours, il est encore plus probable que l'on ne soit jamais à plus de quelques mètres de quelqu'un qui joue à Candy Crush Saga. C'est actuellement le jeu le plus populaire sur Facebook. Il a été téléchargé et installé sur des téléphones, des tablettes et des ordinateurs plus d'un demi-milliard de fois. Essentiellement sur la base de ce succès, son développeur Global King a récemment été introduit à la Bourse de New York avec une valorisation initiale de plusieurs milliards de dollars. Pas mal pour un petit jeu consistant simplement à échanger des bonbons virtuels pour former des chaînes d'au moins trois pièces identiques !
Une grande partie de l'attrait de Candy Crush pour les joueurs est liée à la complexité qui sous-tend ce passe-temps apparemment si simple. De façon surprenante, le jeu est aussi intéressant pour les chercheurs : il apporte un éclairage original sur l'un des problèmes ouverts les plus importants des mathématiques, ainsi que sur la sécurité des systèmes informatiques.

Lire la suite de l'article de Toby Walsh sur espace-turing.fr. L'article a été publié dans Pour la Science d'août 2015.
On peut aussi lire l'article de T. Walsh "Candy Crush is NP-hard", prépublication arXiv du 11 mars 2014