Search code examples
algorithmnp-completenp-hard

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


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.


Solution

  • 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.