[bald]

This. I worked with a company that used this method to generate timetables for schools with way more variables and constraints. They often found working plans when other solutions did not.

Maybe a little overengineered for your problem though