Stories
Slash Boxes
Comments

SoylentNews is people

SoylentNews is powered by your submissions, so send in your scoop. Only 15 submissions in the queue.
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: 4, Funny) by Anonymous Coward on Wednesday March 12 2014, @07:52PM

    by Anonymous Coward on Wednesday March 12 2014, @07:52PM (#15480)

    There is a porn star named CandyCrush, and she does the most amazing things...NP-complete

    Starting Score:    0  points
    Moderation   +4  
       Funny=4, Total=4
    Extra 'Funny' Modifier   0  

    Total Score:   4  
  • (Score: 5, Funny) by bstamour on Wednesday March 12 2014, @07:55PM

    by bstamour (3803) <bryan@bryanstamour.com> on Wednesday March 12 2014, @07:55PM (#15485) Homepage

    But what input does she take? Oh, wait... Nevermind.

    --
    Peace, love, and Unix
    • (Score: 0) by Anonymous Coward on Wednesday March 12 2014, @09:50PM

      by Anonymous Coward on Wednesday March 12 2014, @09:50PM (#15558)

      Like all problems, it is dependent on size of the input...