By Jacob Aron (Image: Simon Dawson/Bloomberg via Getty Images) Feeling guilty about the hours you’ve wasted on Candy Crush Saga? Relax. A mathematical analysis of the notoriously addictive video game reveals that it belongs to a class of fiendish computational problems – and playing it might one day help solve them. Launched in 2012, the Candy Crush Saga game draws a staggering 93 million players per day either via Facebook or a smartphone-specific app. For those who have somehow resisted the candy’s clutches, here are the basics. Players are presented with a board of different coloured candies and have to swap adjacent ones to make three or more of the same colour line up horizontally or vertically. There are restrictions, such as the number of moves allowed or the score you have to reach at the end of a level. Toby Walsh at the University of New South Wales and the computing research centre NICTA – both in Sydney, Australia – analysed the game and discovered that it belongs to a class of mathematical problems called NP-hard, meaning it can be very difficult to find a solution. Walsh studied a generalised version of Candy Crush Saga, in which the board has an unrestricted size, and asked whether it was possible to find a sequence of swaps which obtains a certain score. To turn this into a mathematical question, he created arrangements of candies that are equivalent to logical statements in a maths puzzle called the Boolean satisfiability problem, which asks whether a string of logical statements are compatible or will contradict each other. Computer scientists know that making this decision is NP-hard, which means playing Walsh’s version of Candy Crush Saga must be as well. The same strategy was used previously to show that classic Nintendo games like Super Mario Brothers and Zelda are also NP-hard. Walsh found that Candy Crush Saga belongs to a subset of NP-hard problems known as NP-complete. Solving these problems quickly becomes more difficult as their size increases, making larger versions of such problems impractical. However, finding a scalable way to solve one would work on all the rest. Many important real-world problems are NP-complete, such as scheduling or planning a travel route, so an efficient way to solve them would be massively useful – there’s even a million-dollar prize associated with a related puzzle known as P versus NP. Unfortunately, most researchers believe an efficient way to solve NP-complete problems can’t ever exist, but studying different versions of the problems might reveal that some examples are easier to solve than others. “It would be interesting to see if we can profit from the time humans spend solving Candy Crush problems,” writes Walsh, noting that people have collectively racked up millions of hours of playing time. “Perhaps we can put this to even better use by hiding some practical NP-hard problems within these puzzles?” Earning “NP-hard” status in a computational sense doesn’t exactly correlate with the game being difficult for human players, but the two are related, so the finding may also help explain Candy Crush Saga‘s enduring appeal, according to Walsh. “Part of its addictiveness may be that Candy Crush is a computationally hard puzzle to solve.” Reference: arxiv.org/abs/1403.1911 Update: Since this article was first published on 11 March 2014,