Thanks to researchers in England and Australia, we now have definitive proof of what Candy Crush fans have known for years: this game is incredibly hard. Researchers at the Australian computing research center NICTA, along with Toby Walsh from the University of South Wales, have analyzed the game exhaustively and concluded that Candy Crush belongs to a very specific subset of intensely difficult mathematic problems.
These math problems are known as “NP-hard,” which means they can be extremely tough to solve. Walsh conducted a study that classified Candy Crush within NP-hard problems as a “NP-complete” scenario. These problems become more complex and difficult to solve as they increase in size, but all of them could be solved with a single scalable solution. Unfortunately, most scientists currently believe that there is no way to efficiently solve NP-complete problems, so there’s no magic formula to beat all of Candy Crush forever.
To figure out how mathematically tough Candy Crush was, Walsh used his own version of the game which utilized a board of unrestricted size and then made arrangements of pieces that could correspond with logic from the “Boolean satisfiability problem.” The same strategy has previously been used to establish that other popular video games are also NP-hard math problems in disguise, like Super Mario Bros. and The Legend of Zelda, placing Candy Crush Saga in the same category as some very time-honored games.
Furthermore, other NP-complete problems include societal stumbling blocks like scheduling public transportation, so finding a scalable solution for Candy Crush (assuming, of course, that such a thing is possible) could have incredible side effects for all of humanity. As Walsh puts it:
“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?
If King Digital Entertainment could insert a way to solve real-world problems into their game, 90 million people could change the world overnight. This isn’t just a neat factoid about a casual game–with the right application, Candy Crush might be a major force for good in the world. Even we didn’t see that one coming.
For more on this exciting development, read Jacob Aron’s article on New Scientist.