Slash Boxes

SoylentNews is people

posted by janrinok on Wednesday March 12 2014, @06:59PM   Printer-friendly
from the so-my-childhood-wasn't-wasted dept.

nobbis writes:

"Toby Walsh at the University of NSW Australia has, as reported in New Scientist, studied a generalized version of the popular game Candy Crush Saga and found it be an NP-hard problem, indeed he suggests 'Part of its addictiveness may be that Candy Crush is a computationally hard puzzle to solve.'

His paper shows that early rounds in the game can be modeled as a collection of 'wires' transmitting information across the board, with candies forming inputs and outputs, which can be seen as equivalent to logical statements, this reduces the game to an example of a Boolean satisfiability problem which is known to be NP-complete. A similar technique has been used to show that Super Mario Brothers and Zelda are also NP-hard.

Given that people have spent millions of hours playing the game he notes 'It would be interesting to see if we can profit from the time humans spend solving Candy Crush problems, perhaps we can put this to even better use by hiding some practical NP-hard problems within these puzzles?'"

This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 5, Interesting) by Snotnose on Wednesday March 12 2014, @07:27PM

    by Snotnose (1623) on Wednesday March 12 2014, @07:27PM (#15458)

    Think I got up to a level in the mid-70s when the chocolate finally cheesed me off too much. The game is basically punishing you for losing.

    I didn't rage quit the thing, one day I just didn't fire it up. It's been a couple months since I've played.

    Fun game though, just get rid of the chocolate.

    20 years ago we had Johnny Cash, Bob Hope, and Steve Jobs. Now we have no Jobs, Hope, or Cash. Stay safe Kevin Bacon.
    Starting Score:    1  point
    Moderation   +4  
       Insightful=1, Interesting=2, Informative=1, Total=4
    Extra 'Interesting' Modifier   0  

    Total Score:   5  
  • (Score: 2) by hubie on Wednesday March 12 2014, @08:00PM

    by hubie (1068) Subscriber Badge on Wednesday March 12 2014, @08:00PM (#15491) Journal

    I have never played the game, but I have played something similar where you try to line up 3 or more like-objects. Could you explain your chocolate comment, as in, what properties does it do or not do that changes the gameplay?

    • (Score: 3, Informative) by cyborg_zx on Wednesday March 12 2014, @08:06PM

      by cyborg_zx (3450) on Wednesday March 12 2014, @08:06PM (#15495)

      Basically it spreads out each turn unless you make a match next to it or otherwise destroy it. You can't swap it and it can block incoming candies so if it grows too much you can lose by default.

  • (Score: 3, Interesting) by Fluffeh on Wednesday March 12 2014, @10:38PM

    by Fluffeh (954) Subscriber Badge on Wednesday March 12 2014, @10:38PM (#15586) Journal

    Really? I thought it was a logical factor to put in to make the level more difficult. It was also innovative. That sort of thing didn't really kick in again until somewhere in the 400's where you started getting poly-colored candy (it flucuates between two colors, flipping once a move is made) but even that then generally makes for unexpected slides that generally help more than they hinder.

    The hurricanes further in the 400's were somewhat annoying though, they randomly jump to anywhere on the board, delete the candy and leave a "scar" for one move which candy cannot fall into. There are a few levels with five or ten of the buggers flying around.

    Having said that, I have been waiting for the last few weeks for another patch to come out so that I can continue past 530 where I am currently waiting.