Possible NP-complete problem?

Question

I'd just like someone to verify whether the following problem is NP-complete or if there is actually a better/easier solution to it than simple brute-force combination checking.

We have a sort-of resource allocation problem in our software, and I'll explain it with an example.

Let's say we need 4 people to be at work during the day-shift. This number, and the fact that it is a "day-shift" is recorded in our database.

However, we don't require just anyone to fill those spots, there's some requirements that needs to be filled in order to fit the bill.

Of those 4, let's say 2 of them has to be a nurse, and 1 of them has to be doctors.

One of the doctors also has to work as part of a particular team.

So we have this set of information:

Day-shift: 4
   1 doctor
   1 doctor, need to work in team A
   1 nurse

The above is not the problem. The problem comes when we start picking people to work the day-shift and trying to figure out if the people we've picked so far can actually fill the criteria.

For instance, let's say we pick James, John, Ursula and Mary to work, where James and Ursula are doctors, John and Mary are nurses.

Ursula also works in team A.

Now, depending on the order we try to fit the bill, we might end up deducing that we have the right people, or not, unless we start trying different combinations.

For instance, if go down the list and pick Ursula first, we could match her with the "1 doctor" criteria. Then we get to James, and we notice that since he doesn't work in team A, the other criteria about "1 doctor, need to work in team A", can't be filled with him. Since the other two people are nurses, they won't fit that criteria either.

So we backtrack and try James first, and he too can fit the first criteria, and then Ursula can fit the criteria that needs that team.

So the problem looks to us as we need to try different combinations until we've either tried them all, in which case we have some criteria that aren't filled yet, even if the total number of heads working is the same as the total number of heads needed, or we've found a combination that works.

Is this the only solution, can anyone think of a better one?

---

Edit: Some clarification.

Comments to this question mentions that with this few people, we should go with brute-force, and I agree, that's probably what we could do, and we might even do that, in the same lane that some sort optimizations look at the size of the data and picks different sort algorithms with less initial overhead if the data size is small.

The problem though is that this is part of a roster planning system, in which you might have quite a few number of people involved, both as "We need X people on the day shift" as well as "We have this pool of Y people that will be doing it", as well as potential for a large "We have this list of Z criteria for those X people that will have to somehow match up with these Y people", and then you add to the fact that we will have a number of days to do the same calculation for, in real-time, as the leader adjusts the roster, and then the need for a speedy solution has come up.

Basically, the leader will see a live sum information on-screen that says how many people are still missing, both on the day-shift as a whole, as well as how many people is fitting the various criteria, and how many people we actually ned in addition to the ones we have. This display will have to update semi-live while the leader adjusts the roster with "What if James takes the day-shift instead of Ursula, and Ursula takes the night-shift".

But huge thanks to the people that has answered this so far, the constraint satisfaction problem sounds like the way we need to go, but we'll definitely look hard at all the links and algorithm names here.

This is why I love StackOverflow :)

Answer 1

What you have there is a constraint satisfaction problem; their relationship to NP is interesting, because they're typically NP but often not NP-complete, i.e. they're tractable to polynomial-time solutions.

As ebo noted in comments, your situation sounds like it can be formulated as an exact cover problem, which you can apply Knuth's Algorithm X to. If you take this tack, please let us know how it works out for you.

Answer 2

It does look like you have a constraint satisfaction problem.

In your case I would particularly look at constraint propagation techniques first -- you may be able to reduce the problem to a manageable size that way.

What happens if no one fits the criteria?