Stories
Slash Boxes
Comments

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, Informative) by MrGuy on Wednesday March 12 2014, @07:40PM

    by MrGuy (1007) on Wednesday March 12 2014, @07:40PM (#15467)
    The question is whether we can find a polynomial formula to predict how many players we'll need to solve a known problem. Also, can predict with certainty before they start whether the players will give up before they finish the task? :)
    Starting Score:    1  point
    Moderation   +4  
       Informative=3, Funny=1, Total=4
    Extra 'Informative' Modifier   0  
    Karma-Bonus Modifier   +1  

    Total Score:   5  
  • (Score: 2, Informative) by slartibartfastatp on Wednesday March 12 2014, @07:51PM

    by slartibartfastatp (588) on Wednesday March 12 2014, @07:51PM (#15478) Journal

    I don't think the interesting thing here is to solve the general problem, but instances of it. You can generate a huge database of solutions, that could be used to solve other instances by approximation methods.

    • (Score: 2, Insightful) by space_in_your_face on Wednesday March 12 2014, @10:43PM

      by space_in_your_face (224) on Wednesday March 12 2014, @10:43PM (#15589)
      This idea is intersting in problems for which humans are good and computer bad (for example image recognition).

      In the case of NP-(hard|complete), humans can only solve small problems. And for those, computers are much faster. Try this game [nikoli.com] if you are not convinced (it's probably hard for you, but a computer can solve it in a fraction of a second).
  • (Score: 5, Interesting) by MrGuy on Wednesday March 12 2014, @08:21PM

    by MrGuy (1007) on Wednesday March 12 2014, @08:21PM (#15502)

    Lol. I make a bad NP joke, followed by a worse halting problem joke, and I wind up getting modded "informative."

    I need a serious rethink on what I consider funny, I guess...

    • (Score: 3, Funny) by Geotti on Wednesday March 12 2014, @08:40PM

      by Geotti (1146) on Wednesday March 12 2014, @08:40PM (#15512) Journal

      That must be, because you're One Double O Seven and we don't think you're a joke ; )

    • (Score: 1) by Nesh on Thursday March 13 2014, @08:11AM

      by Nesh (269) on Thursday March 13 2014, @08:11AM (#15759)

      Hey, I laughed! There's at least two who find this funny.