Candy Crush (n.): the deceptively mathematical candy-swiping game that took the world by storm.
On the surface, Candy Crush is purely a marketing strategy. Bright, colourful candy, well-placed power-ups, progressively harder levels that exploit pattern recognition and repetition- the system's rigged. But, what if I told you that the maths in Candy Crush is directly related to a million-dollar problem?
Now that I have your interest, let’s see how the maths in Candy Crush works.
If I gave you a particular level in Candy Crush and asked you if it was possible to find a unique solution to it, you might take a while. But if I gave you the solution (an algorithm, essentially) and asked you to verify if it was unique, you’d obviously be a lot quicker.
If we wanted to measure how long it must take to execute this algorithm, we could say it is relative to the number of elements that it has to handle to find a solution. If the algorithm has “N” elements then the time may be proportional to something like N*log(N) or N^x. Problems with algorithms that have “N” as a base are said to take “polynomial time”. But if the base and the exponent of N^x, which could be something like 50 and 2, were flipped then the execution time would get really scary, really quickly because 50^2 is 2500 but 2^50 is 1.2 x 10^15! So, problems with “N” as their exponent are said to take “exponential time”.
A problem is said to be “P” if it can be solved in polynomial time. An “NP” problem can be verified in polynomial time but, most probably, takes exponential time to solve. Most NP problems are NP-Complete problems, meaning they can be solved by non-deterministic algorithms (which give different outputs even when given the same input) in polynomial time. Proving P = NP, saying that NP-Complete problems can be solved using deterministic algorithms and verified in polynomial time will earn you a million dollars from the Clay Maths Institute.
An important part of proving that P could be equal to NP depends on showing that all the NP problems are similar in some way. That is, showing that the polynomial-time solution for one NP-complete problem can also be used for the other problems. Doing this makes work infinitely easier because as soon as one NP problem is solved in polynomial time, all the other NP problems can be solved in polynomial time too. Finding these similarities i.e., rewriting problems to show that they are, in fact, one NP problem masquerading as another is known as “reduction” (on a slightly related note: reduction is actually quite common, simplifying an equation by removing its common factors and making it an easier one is also an example of reducing a problem). When a problem can be reduced to an NP-Complete one, it is said to be NP-Hard.
But how does this relate to Candy Crush, you ask? Well, let’s try to reduce the game and see for ourselves. For the sake of simplicity: the game will involve only a rectangular board, candy will be destroyed when a chain of 3 identical candies is formed, and everything else i.e, things like striped candy and wrapped candy are all strictly off-limits. Now, if we take a look at this simplified version we can think of the game as a “circuit” of sorts. This “circuit” has two important features: wires, to convey information across the board, and gadgets. A gadget refers to an object in the reduced problem that is used to simulate an object in the original problem which, in our case, is Candy Crush. The two gadgets being used in the circuit are clause gadgets, which represent the clauses of the reduced problem, and variable gadgets, which represent the variables of the reduced problem. The clause gadgets go on the right half of the board while the variable gadgets go on the left half. The settings of these variable gadgets can be changed which, in turn, return “true” or “false” values. So, certain moves on this board will return "true" while others return "false". The clause gadgets are used to determine if each clause of the reduced problem is satisfied or not. The variable gadgets can be moved by the player for wires to communicate information across the board. When this happens one chain of candy is deleted (for which the player will be awarded a certain score). The clause gadgets are connected in such a way that the biggest change that can be made to the score will be by satisfying clauses. By doing this we can see that the only way for a player to obtain the maximum score is by making sure that all the variable gadgets are moved in such a way that they satisfy all the clause gadgets.
Achieving this maximum possible score determines the satisfiability of a co-NP Hard problem, the 3-SAT. This means that Candy Crush is reducible to an NP Problem and is hence, co-NP Hard too.
This explanation is a highly reduced version of the original paper written by Toby Walsh of UNSW and you can find his original paper here.