I created the Model Synthesis algorithm which Wave Function Collapse is based on. While I really like this algorithm I would suggest something slightly different when it's likely the problem is not solvable. I've tried this other approach before and it works surprisingly well.

I use something like the Metropolis algorithm. It's actually really simple. To start, come up with any random solution, it doesn't matter what it is. Then modify that solution over many iterations. Each time you modify the solution, count the number of constraints that are broken both before and after the modification. If the count is lower, keep the modification. If the count is higher, accept it with a certain probability based on how much higher it is. (You may need to play with the probabilities). I tried this and it actually often came up with a perfect solution when one was possible. And unlike Model Synthesis or WFC it won't break down when there's a single failure.