Candy Crush Is Harder Than It Sounds - NP Hard
Written by Mike James   
Wednesday, 12 March 2014

Candy Crush is a phenomenon, if only for the amount of time the world has wasted on it. It seems to be a simple game but judging by the the number of downloads it has a quality that makes it addictive. Now we know why - it's NP-hard.

Toby Walsh at the University of New South Wales, Australia has a proof that puts Candy Crush in its place and might even suggest ways to make the game better. 

If you don't know Candy Crush then you can't be one of the estimated half a billion downloaders at Facebook or on iOS or Android. It is a variant of a class of match-three games. The game that was analysed has a board that isn't fixed in size, but otherwise it is the same game:

The board is filled with a selection of candies that come in six different colors. The challenge is to swap over neighboring  candies to create runs of three of the same color. When you get a set of three of one color they disappear and the candies above fall down to replace them. You score one for each set of three you make disappear.

The challenge is to achieve a set score s in k swaps.

 

candyinstruct

 

It is fairly easy to show that the problem is in NP. If you are given a set of k swaps that scores s then you can check that this is so in polynomial time and hence the problem is in NP.

In his paper, Walsh explains how to map the 3-SAT problem is of course known to be NP Complete, in polynomial time, to Candy Crush, which proves that Candy Crush is at least NP-hard.

NP-hard problems are roughly speaking at least as hard as the hardest problems in NP. The reduction from 3-SAT follows the usual route of creating "gadgets" that convert the game to a set of Boolean functions. 

From here the paper goes on to consider some of the modified game play in later levels of Candy Crush, such as having layers covered up - these too are NP-hard. 

The final question concerns whether there are multiple solutions to a given Candy Crush problem. Presumably the game is better to play if there is just one solution and so it would be nice to find out if a given problem has a unique solution. It turns out that this problem is co-NP-hard - that is proving that there are many solutions is NP-hard. 

Practical thoughts on Candy Crush? 

NP-hard is a worst case classification. How can we vary the difficult of Candy Crush problems? Could there be a "phase change" in parameters that turn easy problems into hard ones? The author of the paper has a nice idea:

"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?"

 candyicon

More Information

Candy Crush is NP-hard

Related Articles

Tensor Operations Are NP Hard       

Vertex Coverings And The Cool Kids Problem       

Finding Solutions To Diophantine Equations By Smell

Travelling Salesman - A Movie About P=NP

Physics Is NP Hard

Computational Complexity

Computability

Pancake flipping is hard - NP hard 

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter.

 

blog comments powered by Disqus

 

Banner


Google Frees Up More Patents
28/08/2014

Google has added 152 patents to the list of ones you can copy in your own open-source version and are covered by its OPN Pledge, whereby Google won't sue unless it is sued first.



This Year's Not-To-Miss AI Movie
24/08/2014

A new robot movie will be released soon and it provides a much deeper look at the robot future we are building for ourselves. It is worth seeing the trailer and tracking it down when it comes out.


More News

 

Last Updated ( Wednesday, 26 March 2014 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.