Numberlink/Flow Game: How to spot NP-Complete problems?

Question

I was trying to find a way to solve the problem in the famous game Flow. http://moh97.us/flow/

After googling I find out that this is a NP-complete problem. A good solution would make use of heuristics and cuts. How can I spot a NP-complete problem easily? Sometimes when I block, I can't see the obvious solution. When this happens with an NP-complete, it's better to recognise it quickly and move on to the next problem.

Answer 1

When you have an explosion of objects (say objects whose count grows exponentially based on some parameter or parameters), this should point you in the direction that it's an NP-complete problem. When you have to inspect, check too many objects (combinatorial or others). Usually these objects are subsets or sub-spaces of some initial object space. You should build some intuition for this. But as usual, the intuition lies sometimes (I've been lied like this by my intuition on 2-3 occasions).

Then once you suspect some problem is NP-complete, just Google for it and try finding more information about the same or about a similar problem.

This is what I do at least and I've been solving quite a few algorithmic problems some time ago.

Here is a nice problem which I am pretty sure is NP-complete but which can be solved through a genetic algorithm for example.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973

And as Dukeling said, there's no generic way of doing this.

Answer 2

There's no easy generic way of doing this. It basically comes down to reducing some known NP-complete problem to solving this problem, or showing that they are equivalent.

So, learn more about well-known NP-complete problems and get more experience with reducing a problem to solving another problem and identifying equivalent problems.

Disclaimer: You just have to be careful of special cases of NP-complete problems - while the generic case of the problem may require exponential time to be solved, these special cases may actually be solvable in polynomial time.