Candy Crush Officially Declared as NP-HARD
Too much obsessed with playing Candy Crush? No worries, the game is an actually difficult math problem, say researchers.
Candy Crush Saga is by far the most popular mobile game in the world. It is a hugely popular game in which players move different coloured candies around a board to create lines of three in a row. Once you get a line of three matching candies is completed, they vanish and candies drop from the top of the screen to fill the gaps.
Toby Walsh, a researcher at the University of New South Wales, tested and concluded the game was NP-hard, which means difficult to solve without a computer.
He recreated the game using a theoretical board of candies and could turn it into a logical math puzzle, hence classifying the strategy alongside other complex problems, confirming it is NP. Toby Walsh from NICTA, wanted to test whether the game was a P math problem, or an NP problem. P problems are those easy to solve puzzles, while NP problems are the difficult ones which can only be solved by a computer because of the large amount of data produced.
Trying to solve this puzzle, Walsh concluded the entire data involved in each level were so high only a computer would be able to process the information, hence making the puzzle not only NP, but NP-complete.
NP-complete puzzles are those which have solutions that can be applied to all other NP problems, but finding that one solution is kind of impossible. For example, if Walsh found the solution to the Candy Crush problem, in theory, this same solution could be applied to other puzzles with enormous data.
Other popular games like Super Mario Brothers and Zelda are also proved to be NP-hard using the same strategy. Walsh says, ‘Part of its addictiveness may be that Candy Crush is a computationally hard puzzle to solve.’
Facebook Comments