I thought about finding an elegant solution, but in the end decided that just doing a (psuedo-)random selection of the remaining set and then running through the resulting ordered list checking each one for all the constraints (ie, random sort). As soon as it failed a hard constraint, or failed > x soft constraints, toss the list and do another random sort.
Ugly, but it worked. Chose this solution because 1) I knew how big the data set would be, and I knew it would not change size enough to matter; 2) The other, very jr developer could understand the method; 3) The constraints, while semi-complex, were simple to check; 4) would be needed once or twice a year, could run completely off-line, and could be started well in advance of when it was needed; 5) and finally computers are fast & cheap, while my time is finite and valuable
As a result, the decision that "brute force" running on any available workstation for a weekend was an acceptable solution. In it's lifetime, I think the longest time it took to find an acceptable solution was a few hundred thousand sorts, finished in a few minutes.
It's now been retired as the program it supported went away.
I wish I'd had the time to explore better, more proper solutions, but at the time, quick and dirty and done was more important.
Of course, many special cases you care about can be expressed much more simply. E.g. with the adjacent-suits example you can deterministically generate such decks pretty easily by appropriately composing uniform integer partition sampling, uniform combination sampling, and uniform permutation sampling. For a standard 52-card deck you can basically lay out suit#1, then suit#2, do a little finicky magic to make sure suit#3 is placed uniformly in such a way that a solution exists (at least one always will), and then fill the remaining slots with suit#4.