Does this constraint satisfaction problem have a name

Question

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?

Answer 1

This is a special case of perfect matching in bipartite graphs and could be solved using standard algorithms for that problem (e.g., the Hungarian algorithm). It is not the perfect matching problem (it looks easier; and it is much more specific), but it is a special case of it.

Answer 2

I couldn't quite understand how this problem was a special case of perfect matching, however, I found my own solution, which is too detailed to describe here.

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.

Thanks anyway