Small NP-hard problems aren't actually that bad. You can usually formulate them as eg a integer programming problem or a SMT problem, and throw an off-the-shelf solver at them.

You only need to learn the solver once, and you can re-use it for all kinds of problems. (Assuming that your instances don't have to be solved with low latency. Eg only as part of your level generation process, or at most when loading a randomly generated level, but not every frame or so.)

https://developers.google.com/optimization has a decent collection of tools.