Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package setgame;
import ilog.concert.IloAnd;
import ilog.concert.IloConstraint;
import ilog.concert.IloException;
import ilog.concert.IloIntVar;
import ilog.cp.IloCP;
/**
* CP implements a constraint programming model to find all set.
* @author Paul A. Rubin (rubin@msu.edu)
*/
public final class CP implements AutoCloseable {
private final IloCP model; // the CP model
private final IloIntVar[] cards; // the index of the card in each slot
private final IloIntVar[][] values; // the value of each feature (row) in
// each slot (column)
/**
* Constructs the CP model.
* @param game the game to solve
* @throws IloException if CPO objects to something
*/
public CP(final Set game) throws IloException {
model = new IloCP();
cards = new IloIntVar[Set.SETSIZE];
values = new IloIntVar[Set.NFEATURES][Set.SETSIZE];
// Define the variables.
for (int slot = 0; slot < Set.SETSIZE; slot++) {
cards[slot] = model.intVar(0, Set.NCARDS - 1, "card_in_slot_" + slot);
for (int feature = 0; feature < Set.NFEATURES; feature++) {
values[feature][slot] =
model.intVar(0, Set.NVALUES, "slot_" + slot + "_feature_" + feature);
}
}
// Constraint: No card can be used twice.
model.add(model.allDiff(cards));
// Constraint: To avoid finding all possible permutations of all possible
// hands, the slots must be filled in ascending card order.
for (int slot = 1; slot < Set.SETSIZE; slot++) {
model.add(model.lt(cards[slot - 1], cards[slot]));
}
// Constraint: The value of a feature in a slot is inherited from the
// card in that slot.
for (int feature = 0; feature < Set.NFEATURES; feature++) {
int[] v = game.getValues(feature);
for (int slot = 0; slot < Set.SETSIZE; slot++) {
model.add(model.eq(values[feature][slot],
model.element(v, cards[slot])));
}
}
// Constraint: For each feature, either all slots have the same value or
// all slots are different.
for (int feature = 0; feature < Set.NFEATURES; feature++) {
IloConstraint different = model.allDiff(values[feature]);
IloAnd same = model.and();
for (int slot = 0; slot < Set.SETSIZE - 1; slot++) {
same.add(model.eq(values[feature][slot], values[feature][slot + 1]));
}
model.add(model.or(different, same));
}
// Suppress output.
model.setOut(null);
}
/**
* Solves the model and returns the number of solutions found.
* @return the solution count
* @throws IloException if CPO pitches a fit
*/
public int solve() throws IloException {
int found = 0;
model.startNewSearch();
while (model.next()) {
found += 1;
}
return found;
}
/**
* Closes the model.
*/
@Override
public void close() {
model.end();
}
}