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
|
package jrummikub.ai.fdsolver.constraint;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import jrummikub.ai.fdsolver.Constraint;
import jrummikub.ai.fdsolver.Propagator;
import jrummikub.ai.fdsolver.Satisfiability;
import jrummikub.ai.fdsolver.Var;
public class OffsetConstraint implements Constraint {
private Var<Integer> x, y;
int offset;
Propagator propX, propY;
public OffsetConstraint(int offset, Var<Integer> x, Var<Integer> y) {
this.offset = offset;
this.x = x;
this.y = y;
propX = new OffsetProp(offset, x, y);
propY = new OffsetProp(-offset, y, x);
}
@Override
public Collection<Var<?>> getWatchedVars() {
return Arrays.<Var<?>> asList(x, y);
}
private class OffsetProp implements Propagator {
private Var<Integer> x, y;
private int offset;
public OffsetProp(int offset, Var<Integer> x, Var<Integer> y) {
this.offset = offset;
this.x = x;
this.y = y;
}
@Override
public Collection<Var<?>> getWatchedVars() {
return Arrays.<Var<?>>asList(y);
}
@Override
public void propagate() {
for(Iterator<Integer> i = x.iterator(); i.hasNext();) {
if(!y.getRange().contains(i.next() + offset)) {
i.remove();
}
}
}
}
@Override
public Collection<Propagator> getPropagators(boolean negate) {
return Arrays.asList(propX, propY);
}
@Override
public Satisfiability getSatisfiability() {
HashSet<Integer> shiftedRange = new HashSet<Integer>();
for (int val : x.getRange()) {
shiftedRange.add(val + offset);
}
shiftedRange.retainAll(y.getRange());
if (shiftedRange.isEmpty()) {
return Satisfiability.UNSAT;
} else if (x.getRange().size() == 1 && y.getRange().size() == 1) {
return Satisfiability.TAUT;
} else {
return Satisfiability.SAT;
}
}
}
|
