Candy Crush Saga is officially hard

GUILTY about the hours you’ve spent playing Candy Crush Saga? Relax. The addictive video game belongs to a class of fiendish maths problems and playing it might one day help to solve them. Launched in 2012, the game draws 93 million players per day. Players  see a board of coloured candies and must swap adjacent ones to line up three or more of the same colour. Toby Walsh at the University of New South Wales in Sydney, Australia, created a version with patterns of candies equivalent to certain logical statements. Gaining a certain score in a certain number of moves proves that these statements agree. This logic puzzle belongs to a class of problems called NP-hard: Walsh was able to show that Candy Crush does too (arxiv.org/abs/1403.1911). Walsh also found that Candy Crush is NP-complete, a subset of problems that includes many real-world tasks such as route planning. Finding a way to solve one such problem could solve the rest: studying how people play Candy Crush might provide clues. ”It would be interesting to see if we can profit from the time humans spend solving Candy Crush,” says Walsh.