Compromise and Conceit

Awww, look at Snoopy trying to solve a commutativity problem!

I have been playing Snoopy Drops (スヌーピー・ドロップス), which is a cute variant of Candy Crush Saga with a deep story (Snoopy is seeking Bell). It has all the same essential properties, and a fiendishly addictive bent to it, along with a pay-for-boostups routine that must surely make it a huge money-spinner. I guess Candy Crush Saga is the same …

As I was playing it I started wondering about the patterns and structures within the game, and started thinking – is this game actually a problem in group theory? If you think of each colour of object as a group, it is largely a closed Abelian group with various operations acting within the group. Essentially, aligning the objects is like addition, but they take on special properties after some operations (yet remain within the group). Some functions apply across groups (the line-breaker objects, portrayed by the white-and-yellow-striped Woodstock in the above picture, for example, eliminate objects from as many groups as there are in the line), and the group is not convex – there are objects from other groups in between the objects of any one group. I guess this means that there is some kind of concept of a finite geometry within which the group structure operates. Hmmm … I did a brief google search on this and couldn’t find anything, but I was originally inspired to think of this by the group theoretic solution of the Rubik’s cube, which seems somehow similar (though perhaps less complex?) I found a paper, described in outline in the Daily Mail, which showed that the game might be NP-Hard, but nothing about possible group theory aspects of the game.

I wonder if the game really is NP-Hard, or if it doesn’t permit such a simplistic description, because of its stochastic properties. The classic NP-hard problem is the Travelling Salesperson Problem, but this problem has a big difference with Snoopy Drops: although the landscape of the problem may be determined randomly (e.g. by random selection of the number of cities the salesperson has to visit), it doesn’t change once the game starts. The linked paper seems to have solved the Snoopy Drops problem by drawing circuits and gates within the board, but these change with every round – I’m not sure how the mathematicians handle this. This is also true of the Rubik’s cube, which can be handed to an enterprising mathematician with its faces randomly jumbled up, but doesn’t randomly rejumble them every time you line up three squares. Also Snoopy Drops comes with multiple conditions (in the picture above there are three: the number of moves required to complete the puzzle, the number of jellies to destroy, and a minimum score to complete the level). For the Travelling Salesperson Problem there is only one condition (time required). So I suppose Snoopy Drops is actually a multiply-constrained problem in stochastic group theory (does such a field exist?).

I think we can agree that even someone as cool as Snoopy can’t fathom the maths of that! But I wonder if this group-theoretic aspect of the game is part of the reason for its addictive properties – when we solve it we are essentially attempting to intuitively solve enormously complex mathematical problems through cute visuals, and to the extent that our brains are keyed in to the way the world around us works, I think they must get some basic biological pleasure from revealing the fundamental building blocks of that world.

I also wonder, if Snoopy Drops is an NP-Hard problem, and if some very smart mathematician could find an expression for its parameters, could the distributed nature of the game mean that other complex NP-Hard problems could be solved by re-expressing them as Snoopy Drops problems, then shipping them out to thousands of players as free levels? Given the number of people playing Candy Crush Saga at any time, if someone could do that they could probably solve all the world’s existing NP-Hard problems in a weekend …