When I used this algorithm, I would seed a random number generator, and if it failed to produce a result given a set of constraints, I'd increment the seed and try again up to ~1000 times or so.