You might be stuck on level 20 or 30 of Candy Crush Saga, but now you can take some small solace in the fact that science has proven that a computer would have just as hard a time beating the game.
Because science isn’t in the business of taking your word for it, a computer scientist from Australia took it upon himself to prove that Candy Crush belongs to a class of computational problems called “NP-hard”. Basically this means that even though verifying a solution to the problem is simple (a high score is achieved in a limited number of moves), finding the solution takes exponentially longer for each additional possible step (different matches).
As always, there’s an xkcd comic on the topic:
So, if I gave you a few appetisers, it would be trivial to add them up and see if they come to $15.05. But it would take far longer to try all the combinations of appetisers and see which add up to the desired total. Each appetiser you add makes the problem take far longer to solve.
Likewise, in Candy Crush, if you have a board with only two possible matches, it may seem like a simple problem. But to find out which match to choose, you have to see what candies will come next, then try all possible matches on the new board, all the way until the end of the game, at which point you have to go back and see if the other branch would result in a better score. The amount of possible outcomes quickly becomes so high that it would take longer than the universe is going to exist to try them all.
This puts it alongside other NP-complete games like Tetris, Minesweeper, Sudoku, and interestingly enough, other NP-hard games, as proved in a similar paper last year:
We prove NP-hardness results for five of Nintendo’s largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versions of Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games.
So what does this mean for you, the average Candy Crush player? Well… it gives you a scientific excuse to not feel bad if you get stuck. I assume for computer scientists, it gives them a change of pace as they try and solve the million dollar P=NP prize.
[via New Scientist]
The answer for the problem in the comic: Seven mixed fruit orders or two orders of hot wings, one mixed fruit, and one sampler plate
Comments