Mathematicians Say Candy Crush Really Is Hard

Now you can play Candy Crush Saga without intellectual guilt: mathematicians say it’s actually pretty hard. Toby Walsh, a researcher at the University of New South Wales in Australia, took a look at the game with his mathematician goggles on and concluded that “it belongs to a class of mathematical problems called NP-hard, meaning it can be very difficult to find a solution,” according to Jacob Aron at New Scientist. 

Walsh published his little investigation on arXiv. The conclusion: “We have shown that the generalized version of Candy Crush is NP-hard to play.” Aaron explains:

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.

Candy Crush Saga is by far the most popular mobile game in the world. In the December quarter last year the game made $450 million in revenue, more than double what Twitter made. And it has about the same number of users: around 408 million every month. Some estimate that people play the game 700 million times every day on their phones and tablets.

But now you can feel a little better about your obsession with Candy Crush, knowing that the game isn’t just mindless candy swiping, but a difficult math problem. Walsh even suggests we could put all that candy-crushing work to good use:

Finally, it would be interesting to see if we can profit from the time humans spend solving Candy Crush problems. Many millions of hours have been spent solving Candy Crush. Perhaps we can put this to even better use by hiding some practical NP-hard problems within these puzzles?

Rose Eveleth | | READ MORE

Rose Eveleth was a writer for Smart News and a producer/designer/ science writer/ animator based in Brooklyn. Her work has appeared in the New York Times, Scientific American, Story Collider, TED-Ed and OnEarth.