[algorias]

I think you underestimate how hard the original problem is. Small decisions can cascade and have effects very far away on the map. Also, in what exact sense do you mean convex?

Furthermore, SAT is hard in theory but the kind of very structured instances found in practice tend to respond well to heuristics.