Why Candy Crush is so difficult – and popular?

If the evidence of my commute is any guide then Candy Crush Saga probably uses as much compute cycles as any other program in London – it is wildly popular.

And if you are player (I am not) then you shouldn’t be surprised or disappointed if you actually struggle with it – because, in fact, there are no obvious “solutions” to the “problems” you face as a player.

Toby Walsh of the University of South Wales has published a paper than shows that the “problems” of Candy Crush are in the class of what is known as “NP”.

NP problems are those which we do not know in advance what the solution is, but for which we can relatively quickly check that the solution applied is correct. In fact NP problems are at the core of internet (and most serious) encryption – internet encryption is difficult to crack in an attack but decryption is easy if the keys  are known.

NP problems are in distinction from “P” problems for which we know, in advance, both a procedure to solve the problem and to check our answer is correct. The “P” here stands for “polynomial time” – meaning we can tell how long the problem will take to solve at the start because it is some multiple (a polynomial) of its initial complexity – long division by pen and paper is a good example from everyday life – we know how to do it and we can instinctively tell how long it will take just by looking at the length of the numbers we are dividing.

Some – but not many – mathematicians believe that NP problems are really just P problems in disguise – it is just that we have not just discovered the way to solve them. In fact it can be shown that if we could find a means of solving a special class of NP problems known as “NP complete” problems then we could solve all NP problems. But most mathematicians believe that NP problems are inherently not amenable to being solved by simple procedures in polynomial time, while yet others think that such a procedure might exist but that the polynomial will be so large that we might see little advantage in cracking the problem.

In the meantime a whole industry has arisen to offer software to solve – though heuristics (informed guesses) and approximations some of the most important NP problems – such as scheduling school or train timetables.

It’s probably not an unreasonable assumption that people like Candy Crush precisely because it is so difficult and because, it would appear, no one is ever going to come up with a way of quickly solving the problems. We can get better by playing more – so that our heuristic sense of what works increases, but no one is going to emerge as an invincible player – because that is inherently not possible. Probably.

(If you want to know more and are not afraid of some maths, then P, NP, and NP-Completeness: The Basics of Computational Complexity might be worth having a look at.)

An NP-complete problem from the world of embedded computing

First of all – a quick explanation of P and NP. The class of problems known as ‘P’ – for polynomial (as in they can be solved in a time which is dependent on a polynomial of their complexity) – are those for which a known algorithm – a sequence of mathematical steps – to solve them exists. For instance, solving (i.e., finding the value of x where the formula evaluates to zero) x – 2 is a P class problem. NP (not P) problems are much more interesting – these are problems for which an algorithm exists but which is unknown at the time the problem is posed. In the worst case the only way of solving the problem may be to try all the potential algorithms until we find the one that solves the problem. That said, once a potential solution is found it can be verified ‘simply’ (i.e. in polynomial time). It is not known if, in fact NP problems (such as drawing up school timetables or cracking internet public key encryption) are really P type problems after all and we just have not found the solution or are permanently excluded from ‘simple’ (P) solutions. A class of NP problems called ‘NP complete‘ are those that, if shown to really be P class problems, would indicate P=NP. Most, but not all, mathematicians think, in fact P!=NP.

So, here’s the problem. It sounds simple, but as it is NP, it’s not! (I got this from Making Embedded Systems: Design Patterns for Great Software)

You have a micro controller with a timer of fixed 4MHz frequency and two 8 bit registers, a and b, such that (a) counts ticks and (b) is a match register that triggers an interrupt when the count register matches the tick count stored and a 16 bit prescaler (that allows the scaling of the ticks e.g. – if set to 2 then twice as many ticks are required to trigger the interrupt).

So how can you set the match and prescaler to work for an arbitrary frequency? Sounds like it should be easily algorithmically managed, but it’s not.