search - Scheduling Problems (shift planning), need in a fast algorithm -

i have problem i'll explain , don't know if scheduling problem :

for 30 or 31 days/month want assign doctors shifts constraints :

1-every doctor must assigned specific number of days (e.g 10 or 12)

2-everyday need specific number of doctors (e.g 3 doctors normal days , 4 tuesdays , 3

3-there's custom constraints : no 1 stay 2 continuous days or 3 in cases

4-special days holidays predefined, example doctors 1-4 must stay 2 holidays , doctors 5-8 must stay 1 holidays.

5-finally points of table predefined, example doctor 1 want stay 3th , want no shift 5th.

...

i myself trying treat problem csp :

a table[#doctors][#days]. each cell red green or white , doing dfs search :

1-start choosing cell assign 2-assigning red or green if valid (in stochastic order) or backtrack if not valid 3-check if solution reached

o( 2^(#days*#doctors) ) without invalidity prediction

now algorithm slow , don't know if faster using better function predicting invalid nodes , backtrack sooner, i'm in binary constraints csp not

i want algorithm finding solution in 10 minute or less

any idea or better algorithm class kind of problem ?

thanks alot

WIKI