Candy Crush’s Puzzling Mathematics » American Scientist
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.
"}}