If you have such constraints, why not use a proper constraint system? Prolog is in a (sometimes not so) sweet spots in terms of exploring search spaces.

For a problem like you've described, just write a SAT instance and be done with it. And if you don't know how large your solution/search space is (even a bound), then there's no alternative to creating lists and giving recursion hints.