Image by Ian Hughes, Flickr
Is Candy Crush Saga appealing to our mathematical brains?
I like puzzles, but rarely take the time to focus on them unless I am somewhere with no duties to perform. So I have ignored my friend’s invitation to play Candy Crush Saga, thinking the picture of the Candy Crush square would soon vanish from my sidebar. Well, it hasn’t, and the invitations to play keep coming.
Then, I saw Toby Walsh’s intriguing article, entitled “Candy Crush’s Puzzling Mathematics,” with the assertion that “This simple game has deceptively difficult computational problems behind it, which might be why it’s so addictive.”
Addictive? Persistence on my sidebar? Persistent invitations to play? Maybe I’m not up to playing it, but Walsh had me in the palm of his hand. A better writer about mathematics you could rarely find.
But wait!!! If you prefer comedy to analysis, go here first! Disclaimer: This link is posted for your entertainment only, and is not meant to draw any parallel between the subject of this post and the linked comic strip.
Warning: Don’t be distracted and miss taking a look at Walsh’s engrossing article:
It’s been said that in a city, you’re never more than a few feet away from a rat. But these days it seems more likely that you’re never more than a few feet away from someone playing Candy Crush Saga. It is currently the most popular game on Facebook. It has been downloaded and installed on phones, tablets, and computers more than half a billion times. Largely based on this success, its developer, Global King, listed recently on the New York Stock Exchange in an initial public offering valuing the company in the billions of dollars. That’s not bad for a simple game of swapping candies to form chains of three or more identical pieces.
A big part of the appeal of Candy Crush for players is that there are complex underpinnings to the seemingly simple puzzle. Surprisingly, the game holds a lot of interest for researchers as well: It offers insight into one of the most important open problems in mathematics, as well as into the security of computer systems.
In a recent proof, I demonstrated that Candy Crush is a mathematically hard puzzle to solve (the paper is available at this link). To prove this point, I needed to call upon one of the most important and beautiful concepts in the whole of computer science, the idea of a problem reduction. This idea maps one problem onto another, or as computer scientists like to say, it reduces one problem into another. At its heart, this concept arises because computer code is versatile: You can use the same type of code to solve more than one problem, even if the variables differ. If the problem you started with was hard, then the problem you map onto must be at least as hard. The second problem can’t be easier because you must be able to solve the first problem with a computer program that can solve the second problem. And if you can show the reverse, that the second problem can also be reduced to the first problem, then in some sense the two problems are equally as hard as each other, and take a similar time to solve.
Determining the difficulty of a problem is a fundamental tenet of mathematics. But it’s not a semantic point. If you can classify a problem by how hard it should be to solve, you know what kind of computing power to throw at it—and even if it’s worth trying to solve at all. In some ways, at least for mathematicians, looking at Candy Crush as a math problem can be as addictive as playing it.
Source: American Scientist, November-December 2014
Click the next page number to see how Walsh moves from classifying the problem to cracking code.
