Search Heuristics Where the Search Space Has No Gradient
Search heuristics will be useless on those kinds of problems.  It will effectively degenerate to brute-force search: trying all possibilities in hopes that one of them works.  That's very unlikely to find you the solution, except in the smallest possible problems, as its running time is exponential.

What else can you do instead?  You'll need to consider other kind of approach: e.g., a  SAT solver or ILP solver, an approximation algorithm or any of the other standard methods of dealing with NP-hardness.