# Does this constraint satisfaction problem have a name

I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution.

The problem is: I am making a card-playing AI, and at some point I need to guess a plausible solution to the other players hands. Given the history of the game, I can definitely say that some players don't have certain cards .

Put formally: I have a set of elements $S$ (the remaining cards in the game), and the goal is to partition $S$ into a fixed number of disjoint subsets $S_i$, for $i \in \{1...n\}$. For each subset, we have a set of elements $A_i$ that they may not have, and a number of elements $N_i$ that this subset must contain. Also, $|S| = \Sigma_i N_i$. Find a partition.

There are a number of extra conditions that could make this problem much easier:

• The initial conditions guarantee that there will always be a solution.
• All remaining cards are in other peoples hands. There is no deck, and so all other cards have either already been played, or are in my AI's hand.
• The number of cards to be distributed is $<24$.
• There is always exactly 3 opposing players, i.e. $n = 3$.
• For any $i, j$, $abs(|N_i| - |N_j|) <= 1$.

I am convinced that this problem has already been studied and has a name. Does anybody know if it exists? If not, is the problem is simple enough that there is a solution that does not require exponential search?

• Seems very specific, to me. Maybe it has a name but I'm not convinced. – David Richerby Aug 5 '18 at 10:47

Using pure set logic, I found a solution which runs in a time linear in the sizes of the sets $N_i$, but combinatorial in the number of players. Given that the number of players is always 3, this algorithm is quite fast for my use case.