Mathematicians Say Candy Crush Really Is Hard | Smart News | Smithsonian
Current Issue
July / August 2014  magazine cover
Subscribe

Save 81% off the newsstand price!

Keeping you current

Play on, my mathematicians! (MeLY3o)

Mathematicians Say Candy Crush Really Is Hard

You can feel better about your obsession with Candy Crush. The game isn’t just mindless swiping; it's an actually difficult math problem.

smithsonian.com

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?

Tags
About Rose Eveleth
Rose Eveleth

Rose Eveleth is 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.

Read more from this author |

Comment on this Story

comments powered by Disqus