Set Game

What is this repository for?

Set is a card game involving 81 cards, each containing four features, with each feature having three possible values. A "set" is a collection of three cards such that, for each feature, either all three cards are identical or all three are different. As noted in the Wikipedia entry, there are 1,080 possible "sets".

A question on OR Stack Exchange asked how to use an integer programming model to generate all possible sets. The code here actually investigates four approaches:

• brute force (using a recursive function);
• a constraint programming model;
• a binary integer program solved repeatedly, with "no good" constraints added after every solution; and
• the same binary integer program solved just once, using a callback to add the "no good" constraints.

Details

The code was developed in Java, using CPLEX 22.1.1 for the integer programs and CP Optimizer 22.1.1 for the constraint program. To run it, you will need a version of CPLEX recent enough to include generic callbacks. Details of the IP model can be found in my answer to the OR SE question. Information about the CP model can be found in my blog post.

License

The code here is copyrighted by Paul A. Rubin (yours truly) and licensed under a Creative Commons Attribution 3.0 Unported License.