summaryrefslogtreecommitdiffstats
path: root/src/jrummikub/ai/fdsolver/constraint
diff options
context:
space:
mode:
Diffstat (limited to 'src/jrummikub/ai/fdsolver/constraint')
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/IfConstraint.java108
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java134
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java77
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/SameConstraint.java70
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/SumConstraint.java51
5 files changed, 440 insertions, 0 deletions
diff --git a/src/jrummikub/ai/fdsolver/constraint/IfConstraint.java b/src/jrummikub/ai/fdsolver/constraint/IfConstraint.java
new file mode 100644
index 0000000..802acc2
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/IfConstraint.java
@@ -0,0 +1,108 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.concurrent.locks.Condition;
+
+
+import jrummikub.ai.fdsolver.Constraint;
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Satisfiability;
+import jrummikub.ai.fdsolver.Var;
+
+public class IfConstraint implements Constraint {
+ Var<Boolean> condition;
+ Constraint child;
+ Collection<Var<?>> vars;
+ boolean negateCond;
+
+ public IfConstraint(boolean negateCond, Var<Boolean> condition, Constraint child) {
+ this.condition = condition;
+ this.child = child;
+ this.negateCond = negateCond;
+ vars = new ArrayList<Var<?>>();
+ vars.addAll(child.getWatchedVars());
+ vars.add(condition);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return vars;
+ }
+
+ private class IfPropagator implements Propagator {
+ Propagator child;
+ Collection<Var<?>> vars;
+ public IfPropagator(Propagator child) {
+ this.child = child;
+ vars = new ArrayList<Var<?>>();
+ vars.addAll(child.getWatchedVars());
+ vars.add(condition);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return vars;
+ }
+
+ @Override
+ public void propagate() {
+ if(condition.getRange().contains(negateCond)) {
+ return;
+ }
+ child.propagate();
+ }
+ }
+
+ private class FailPropagator implements Propagator {
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return child.getWatchedVars();
+ }
+
+ @Override
+ public void propagate() {
+ if (child.getSatisfiability() == Satisfiability.UNSAT) {
+ condition.invalidate(!negateCond);
+ }
+ }
+ }
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ List<Propagator> props = new ArrayList<Propagator>();
+ if (negate) {
+ props.add(new FilterPropagator<Boolean>(new Filter<Boolean>() {
+ @Override
+ public boolean accept(Boolean value) {
+ return value ^ negateCond;
+ }
+ }, condition));
+ props.addAll(child.getPropagators(true));
+ } else {
+ for (Propagator p : child.getPropagators(false)) {
+ props.add(new IfPropagator(p));
+ }
+ props.add(new FailPropagator());
+ }
+ return props;
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ if (condition.getRange().contains(negateCond)) {
+ if (condition.getRange().size() == 1) {
+ return Satisfiability.TAUT;
+ } else {
+ if (child.getSatisfiability() == Satisfiability.TAUT) {
+ return Satisfiability.TAUT;
+ } else {
+ return Satisfiability.SAT;
+ }
+ }
+ }
+ return child.getSatisfiability();
+ }
+
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java b/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java
new file mode 100644
index 0000000..999924f
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java
@@ -0,0 +1,134 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+
+import jrummikub.ai.fdsolver.Constraint;
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Satisfiability;
+import jrummikub.ai.fdsolver.Var;
+
+public class IndexConstraint<T> implements Constraint {
+ Var<T> target;
+ Var<Integer> index;
+ List<Var<T>> list;
+ Collection<Var<?>> vars = new ArrayList<Var<?>>();
+ Collection<Var<?>> varsNoTarget = new ArrayList<Var<?>>();
+ Collection<Var<?>> varsNoIndex = new ArrayList<Var<?>>();
+
+ public IndexConstraint(Var<T> target, Var<Integer> index, List<Var<T>> list) {
+ this.target = target;
+ this.index = index;
+ this.list = list;
+ vars.addAll(list);
+ vars.add(index);
+ vars.add(target);
+ varsNoTarget.addAll(list);
+ varsNoTarget.add(index);
+ varsNoIndex.addAll(list);
+ varsNoIndex.add(target);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return vars;
+ }
+
+ private class UnionProp implements Propagator {
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return varsNoTarget;
+ }
+
+ @Override
+ public void propagate() {
+ HashSet<T> union = new HashSet<T>();
+ for (int i : index.getRange()) {
+ union.addAll(list.get(i).getRange());
+ }
+ for (Iterator<T> i = target.iterator(); i.hasNext();) {
+ T val = i.next();
+ if (!union.contains(val)) {
+ i.remove();
+ }
+ }
+ };
+ }
+
+ private class IndexProp implements Propagator {
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return varsNoIndex;
+ }
+
+ @Override
+ public void propagate() {
+ for (Iterator<Integer> i = index.iterator(); i.hasNext();) {
+ int id = i.next();
+ HashSet<T> range = new HashSet<T>(target.getRange());
+ range.retainAll(list.get(id).getRange());
+ if (range.isEmpty()) {
+ i.remove();
+ }
+ }
+ }
+ }
+
+ private class VarProp implements Propagator {
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.asList(target, index);
+ }
+
+ @Override
+ public void propagate() {
+ if (index.getRange().size() != 1)
+ return;
+ int id = index.getValue();
+ Var<T> var = list.get(id);
+ for(Iterator<T> i = var.iterator(); i.hasNext();) {
+ if (!target.getRange().contains(i.next())) {
+ i.remove();
+ }
+ }
+ }
+
+ }
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ if (negate) {
+ return Collections.emptyList();
+ }
+ return Arrays.<Propagator> asList(new UnionProp(), new IndexProp(), new VarProp());
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ HashSet<T> union = new HashSet<T>();
+ for (int i : index.getRange()) {
+ union.addAll(list.get(i).getRange());
+ }
+ boolean isSat = false;
+ for (T val : target.getRange()) {
+ if (union.contains(val)) {
+ isSat = true;
+ break;
+ }
+ }
+ if (!isSat) {
+ return Satisfiability.UNSAT;
+ } else {
+ if (union.size() == 1 && target.getRange().size() == 1) {
+ return Satisfiability.TAUT;
+ } else {
+ return Satisfiability.SAT;
+ }
+ }
+ }
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java b/src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java
new file mode 100644
index 0000000..f91dcda
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java
@@ -0,0 +1,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;
+ }
+ }
+
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/SameConstraint.java b/src/jrummikub/ai/fdsolver/constraint/SameConstraint.java
new file mode 100644
index 0000000..7fc8961
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/SameConstraint.java
@@ -0,0 +1,70 @@
+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 SameConstraint<T> implements Constraint {
+ private Var<T> x, y;
+ Propagator propX, propY;
+
+ public SameConstraint(Var<T> x, Var<T> y) {
+ this.x = x;
+ this.y = y;
+ propX = new SameProp<T>(x, y);
+ propY = new SameProp<T>(y, x);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>> asList(x, y);
+ }
+
+ private class SameProp<T> implements Propagator {
+ private Var<T> x, y;
+ public SameProp(Var<T> x, Var<T> y) {
+ this.x = x;
+ this.y = y;
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>>asList(y);
+ }
+
+ @Override
+ public void propagate() {
+ for(Iterator<T> i = x.iterator(); i.hasNext();) {
+ if(!y.getRange().contains(i.next())) {
+ i.remove();
+ }
+ }
+ }
+ }
+
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ return Arrays.asList(propX, propY);
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ HashSet<T> range = new HashSet<T>(x.getRange());
+ range.retainAll(y.getRange());
+ if (range.isEmpty()) {
+ return Satisfiability.UNSAT;
+ } else if (x.getRange().size() == 1 && y.getRange().size() == 1) {
+ return Satisfiability.TAUT;
+ } else {
+ return Satisfiability.SAT;
+ }
+ }
+
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/SumConstraint.java b/src/jrummikub/ai/fdsolver/constraint/SumConstraint.java
new file mode 100644
index 0000000..80b19e2
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/SumConstraint.java
@@ -0,0 +1,51 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+
+import jrummikub.ai.fdsolver.Constraint;
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Satisfiability;
+import jrummikub.ai.fdsolver.Var;
+
+public class SumConstraint implements Constraint {
+ Var<Integer> x, y, z;
+
+ public SumConstraint(Var<Integer> x, Var<Integer> y, Var<Integer> z) {
+ this.x = x;
+ this.y = y;
+ this.z = z;
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>> asList(x, y, z);
+ }
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ // TODO Auto-generated method stub
+ return Collections.emptyList();
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ // HashSet<Integer> intersection = new HashSet<Integer>();
+ for (int xv : x.getRange()) {
+ for (int yv : y.getRange()) {
+ if (z.getRange().contains(xv + yv)) {
+ if (z.getRange().size() == 1 && x.getRange().size() == 1
+ && y.getRange().size() == 1) {
+ return Satisfiability.TAUT;
+ } else {
+ return Satisfiability.SAT;
+ }
+
+ }
+ }
+ }
+ return Satisfiability.UNSAT;
+ }
+}