diff options
Diffstat (limited to 'src/jrummikub/ai/fdsolver/constraint')
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; + } +} |