2
$\begingroup$

I am playing around with the 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.

Given the $81$ cards of the game, is it possible to generate the possible different sets of the game with a MIP (or a sequence of MIPs)?


Follow up question is posted here.

$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by "decks with exactly 6 sets"? Given 81 cards with all possible combinations of four features (three values each), there are way more than six possible sets. $\endgroup$
    – prubin
    Aug 11, 2023 at 16:22
  • $\begingroup$ @prubin when playing solo online, there is a version of the game where the app generates a deck of 12 cards, and the goal is to find the 6 hidden sets. Once you have found all 6, a new deck of 12 cards in generated, with 6 hidden sets. And so forth. $\endgroup$
    – Kuifje
    Aug 11, 2023 at 16:50
  • $\begingroup$ The answer to the second part is "yes" but the model is substantially different, so it really should be a separate question. $\endgroup$
    – prubin
    Aug 11, 2023 at 18:10

1 Answer 1

4
$\begingroup$

Let me start with the advisory that "can do" and "should do" are distinct concepts. We can find all 1,080 sets in a full deck using an integer programming model ... or a constraint programming model ... or brute force. I think that list is in ascending order of speed.

For the IP approach, define the following variables:

  • $x_c=1$ if card $c$ is included in the set, 0 if not;
  • $y_{f,v}=1$ if value $v$ of feature $f$ appears in the set; and
  • $z_f=1$ if feature $f$ is all different in the set and 0 if all the same.

The objective function is irrelevant, so we can minimize 0.

Constraints are as follows:

  • Exactly three cards must be in the set: $$\sum_c x_c = 3.$$
  • For each feature, either one or three values must be present: $$\sum_v y_{f,v} = 1 + 2z_f\quad \forall f.$$
  • A value of a feature appears in the set if and only if a card with that value is included in the set: $$y_{f,v} \ge x_c\quad \forall c\in C_{f,v}$$ $$y_{f,v} \le \sum_{c\in C_{f,v}} x_c.$$

Here $C_{f,v}$ denotes the set of cards with value $v$ of feature $f.$

Solving the model finds a single valid set. To avoid repeating the set, after getting a solution $(\bar{x}, \bar{y}, \bar{z})$ we add a "no good" constraint $$\sum_{c : \bar{x}_c =1} x_c \le 2$$ and then solve again. After finding 1,080 solutions, the model becomes infeasible.

If your IP solver supports callbacks, rather than solving 1,081 models you can solve one model, adding the no good constraints via callback (and in the process rejecting the solutions that generated the constraints), again until the problem becomes infeasible.

Addendum: I tried this in Java using CPLEX 22.1.1. Brute force enumeration (done recursively) required about 0.1 seconds. Using a single IP model with a generic callback (and limiting CPLEX to one thread so that I didn't have to deal with thread-safety problems) took about 1.4 seconds (so roughly an order of magnitude slower). Solving an IP model over and over while adding constraints took about 56 seconds.

Addendum 2: I tried CP Optimizer 22.1.1 (constraint programming solver), and it found all 1,080 solutions in about 0.1 seconds, roughly tying it with brute force.

$\endgroup$

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.