Candy Crush is a phenomenon; the game is played by over 93 million players on Facebook and mobile devices. For those who aren’t aware of the game, Candy Crush is a puzzle game that follows a relatively simple concept. In the game, players are presented with a board of candies of a variety of different colors. The player swaps adjacent candies with each other, and the goal of the game is to line up matching colors so that they line up either horizontally or vertically. There are restrictions however, such as the number of allowed moves, or a score that the player has to reach to beat the level.
A lot of core gamers scoff at the game for being simple and not very difficult. However, a new scientific study shows that Candy Crush may actually be considered mathematical hard. In an article from New Scientist, Toby Walsh from the University of New South Wales in Sydney, Australia has done a mathematical analysis on Candy Crush which reveals something quite interesting. The game belongs to a special class of mathematical problems called “NP-hard,” which means that finding a solution in the game can be quite difficult. Classic games such as Super Mario Bros. and The Legend of Zelda are also classified as NP-hard.
To analyze Candy Crush, Walsh studied a generalized version of the game in which the board is unrestricted in size. Walsh asked whether it was possible to find a specific sequence of candy swaps that allowed the player to achieve a specific score. In order to make a mathematical question out of this, Walsh created certain arrangements of the candies that are the same as logical statements known as the Boolean satisfiability problem. This problem simply asks whether or not a string of logical statements make sense together, or if they contradict each other. Making this decision is considered by computer scientists to be NP-hard. Thus, Walsh concluded that Candy Crush Saga must be NP-hard. Specifically, Candy Crush is considered to be NP-complete, which is a specific set of NP-hard. This means that it becomes more difficult to solve the problem as its scale increases; very large-scale problems are considered impractical to solve.
Most researchers believe that finding an efficient way to solve NP-complete problems can’t exist. However, studying some NP-complete cases can reveal that some problems are easier to solve than others.
“It would be interesting to see if we can profit from the time humans spend solving Candy Crush problems,” Walsh wrote, referencing the millions of collective hours that people have put into playing Candy Crush. “Perhaps we can put this to even better use by hiding some practical NP-hard problems within these puzzles?”
Finally, Walsh wrote that the fact that Candy Crush is such a hard puzzle to solve may be one of the reasons that the game is so addicting, and why it has such a mass appeal.
“Part of its addictiveness may be that Candy Crush is a computationally hard puzzle to solve.”