Source: http://www.newscientist.com/article/dn25...

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 ofCandy 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.