Losowanie i sprawdzenie będzie w porządku o ile prawdopodobieństwo
wylosowania dostatecznie dobrego układu nie jest zbyt małe. Jak będzie
zbyt małe to zwykle nie doczekasz się wylosowania dobrego grafiku i
twój program powie "niedasie". Ile wynosi to prawdopodobieństwo,
zależy od przyjętych ograniczeń, więc trudno powiedzieć.

Losując warto też przemyśleć sposób losowania, żeby było
"sprawiedliwie". W przypadku uwzględniania przy losowaniu na wstępie
"kilku prostszych warunków" wypada uważać, żeby niechcący nie zaburzyć
tej "sprawiedliwości".

Co do lepszego algorytmu - niestety nikt z nas grupowiczów nie zna tak
dobrze kodeksu pracy, a już na pewno życzeń pracowników i szefostwa. I
nie będziemy za ciebie analizować przepisów polskiego kodeksu pracy.
Jeśli te reguły ograniczeń są dowolnej postaci, to problem jest NP-
trudny (tak jak SAT), co nie znaczy, że nie da się go rozwiązywać
szybciej lub wolniej. A możliwe, że te reguły ograniczeń są tak
specyficzne, że wychodzi algorytm wielomianowy (np. problem 2-SAT), co
też nie znaczy, że nie da się go implementować szybciej lub wolniej.

Jeśli zależy ci na prędko napisanym jako-takim prototypie, możesz np.
przekształcać ograniczenia na wejscie do SAT-solvera czy czegoś w tym
stylu.