1
$\begingroup$

This question was initially the second part of another question and justifies a new post.

The context is a game called Set:

In the game, certain combinations of three cards are said to make up a "set". For each one of the four categories of features — color, number, shape, and shading — the three cards must display that feature as either a) all the same, or b) all different. Put another way: For each feature the three cards must avoid having two cards showing one version of the feature and the remaining card showing a different version.

Apps online generate decks of $12$ cards with exactly $6$ hidden sets. The goal is to find the $6$ hidden sets, and once all $6$ are found, a new deck of 12 cards is generated, with $6$ hidden sets. And so forth.

Is it possible to generate such decks with a MIP?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $\Omega$ be the set of all the sets, and let $C$ the complete deck of cards. Let $y_s$ be a binary variable that takes value $1$ if and only if set $s \in \Omega$ is used. And let $x_c$ be a binary variable that takes value $1$ if and only if card $c\in C$ is used.

To generate a deck of $12$ cards with $6$ sets, minimize a dummy objective function subject to:

  • The deck must have $12$ cards: $$ \sum_{c\in C} x_c = 12 $$
  • The deck must have $6$ sets: $$ \sum_{s\in \Omega} y_s= 6 $$
  • If set $s$ is selected, then cards from this set are selected: $$ y_s\le x_c \quad \forall s\in \Omega, \quad\forall c \in s $$
  • If a set $s$ is not selected, then its $3$ cards can not be selected (courtesy of @prubin): $$ \sum_{c\in s}x_c \le 2+y_s \quad \forall s \in \Omega $$

To generate a new deck given a solution $\hat{y}$, you can add a no good cut: $$ \sum_{s\in \Omega|\hat{y_s}=1}y_s \le 5 $$

Note that brute force would require generating decks from the $\binom{81}{12}=7.07243201847 × 10^{13}$ possible decks of $12$ cards, and checking if they contain $6$ of the $1 080$ sets.

$\endgroup$
2
  • $\begingroup$ I think you also need a constraint saying that if set $s$ is not selected, then the three cards in $s$ cannot all be present. Otherwise, your deck might contain more than 6 sets. $\sum_{c\in s} x_c \le 2 + y_s\, \forall s\in \Omega$ should do it, I think. $\endgroup$
    – prubin
    Aug 12, 2023 at 20:33
  • $\begingroup$ @prubin I think you are right, thanks! $\endgroup$
    – Kuifje
    Aug 12, 2023 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.