Candy Crush’s Puzzling #Mathematics http://www.americanscientist.org/issues/id.16278,y.2014,no.6,content.true,page.1,css.print/issue.aspx Game reducible to a NP-hard logic circuit; maybe useful in solving other problems

QT:{{"

To show that Candy Crush is a mathematically hard problem, we could

reduce to it from any problem in NP. To make life simple, my

colleagues and I started from the granddaddy of all problems in NP,

finding a solution to a logical formula. This is called the

satisfiability problem. You will have solved such a problem if you

ever tackled a logic puzzle. You have to decide which propositions to

make true, and which to make false, to satisfy some set of logical

formulae: The Englishman lives in the red house. The Spaniard owns the

dog. The Norwegian lives next to the blue house. Should the

proposition that the Spaniard owns the zebra be made true or false?

To reduce a logic puzzle to a Candy Crush problem, we exploit the

close connection between logic and electrical circuits. Any logical

formula can simply be represented with an electrical circuit.

Computers are, after all, just a large collection of logic gates—ANDs,

ORs, and NOTs—with wires connecting them together. So all we need to

do is show that you could build an electrical circuit in a Candy Crush

game.

…

The idea of problem reduction offers an intriguing possibility for

Candy Crush addicts. Perhaps we can profit from the millions of hours

humans spend solving Candy Crush problems? By exploiting the idea of a

problem reduction, we could conceal some practical computational

problems within these puzzles. Other computational problems benefit

from such interactions: Every time you prove to a website that you’re

a person and not a bot by solving a CAPTCHA (one of those ubiquitous

distorted images of a word or number that you have to type in) the

answer helps Google digitize old books and newspapers. Perhaps we

should put Candy Crush puzzles to similar good uses.

"}}