[EdiX]

> These days, when you have a SAT-like problem, you're often done because you can throw a SAT solver at it, and it will give you an answer in a reasonable time

I don't know. All my experiences with SAT solvers have been bad. Sometimes adding constraints (and making the problem overconstrained) makes them orders of magnitude faster, sometimes it makes them orders of magnitude slower. Same goes for changing variables from integer to real or vice versa. And it varies from SAT solver to SAT solver, even on the same problem. I know enough about SAT solvers to know why this might happen but they're complete black boxes (as far as I can tell) and I can't predict their performance at all nor can I predict if a change I attempt will make them behave better or worse. I can't even tell if the bad performance is my fault or just the problem being legitimately to hard. And when it works I'm never sure if it will always work or if there are some inputs we have that will slip through the cracks of the heuristics it's using and hit us with a running time measured in days. If I could never use a SAT solver ever again I wouldn't.