SET game: how to generate decks of 12 cards with 6 hidden sets?

Question

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?

Answer 1

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.