there's also a bunch of dedicated constraint programming solvers / high level modelling languages for these kinds of constraint-y combinatorial optimisation problems

e.g. https://www.minizinc.org/ offers a high level modelling language that can target a few different solver backends

might be pretty good results to completely ignore writing a custom algorithm and drop in an existing industrial-grade constraint programming solver, model your procgen problem using a high level language, and use the existing solver to find you random solutions (or exhaustively enumerate them). then more time to iterate on changing the problem definition to produce more interesting maps rather than getting bogged down writing a solver.