"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?'"
(Score: 5, Informative) by lhsi on Wednesday March 12 2014, @09:13PM
It's not solving a NP problem, but Cancer Research UK have an app to help analyse data: https://play.google.com/store/apps/details?id=com
. guerillatea.elementalpha [google.com]
It's a space game but the course plotting bit is helping analyse one of many cancer samples. The app is based around this and up front about it instead of trying to sneak it in though.
(Score: 1) by NezSez on Thursday March 13 2014, @06:15PM
I heard about this project on Ted Talks. A project for mapping 3d neural pathways in the human brain by people playing a game called "Eyewire" http://blog.eyewire.org/about/ [eyewire.org]
Links to youtube videos are on the site.
No Sig to see here, move along, move along...