## Addictive Candy Crush video game is officially hard - New Scientist

#### J Thoendell stashed this in Video Games

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

**Stashed in:** Software!, Candy Crush!

11:58 AM Mar 12 2014