Stories
Slash Boxes
Comments

SoylentNews is people

Candy Crush Proved to be NP-Hard

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.
Candy Crush Proved to be NP-Hard | Log In/Create an Account | Top | 25 comments | Search Discussion
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 bstamour on Wednesday March 12 2014, @07:42PM

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

    As I understand it (IANACS), the problem with using the game equivalent to "solve" equivalent NP-hard or NP-complete problems (for example, finding a hamiltonian path through an arbitrary connected graph) is that it's hard to "prove" the negative ("no path exists" or "this game of minesweeper is not solvable without guessing") without somehow forcing your "large array of monkeys" to try every single possibility. Proving the POSITIVE case (I solved it!) is much easier, but not guaranteed to happen.

    Sort of. By my understanding of complexity theory, it would be more like: one of your magical monkeys hands me a solution to the game, and I can verify that it is indeed a solution in polynomial time. However constructing the solution to begin with is still computationally very difficult.

    Consider minesweeper: if some oracle handed me a solution to the puzzle, I could quickly scan over it and say "yes this is a solution", or "no, you hit a bomb over there" pretty easily.

    --
    Peace, love, and Unix
    Starting Score:    1  point
    Moderation   +4  
       Interesting=3, Informative=1, Total=4
    Extra 'Interesting' Modifier   0  
    Total Score:   5  

  • (Score: 4, Interesting) by MrGuy on Wednesday March 12 2014, @07:49PM

    by MrGuy (1007) on Wednesday March 12 2014, @07:49PM (#15477)

    Right - get how NP-complete problems work.

    I'm referring to the suggestion in TFA/TFS that, since we've proven equivalency, if we were in a position where we had a specific instance of an NP-complete or NP-hard problem, we could construct a version of the game that was equivalent to that problem, and then use people playing the game to "solve" the NP-hard/NP-complete instance problem we care about. i.e. use humans playing a game as logical processing threads to find solutions to a more important but less fun version of the problem.