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

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?

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.

• 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.
– prubin
Aug 12, 2023 at 20:33
• @prubin I think you are right, thanks! Aug 12, 2023 at 20:43