diff options
Diffstat (limited to 'src/jrummikub/ai/fdsolver/constraint')
9 files changed, 278 insertions, 0 deletions
diff --git a/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java b/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java new file mode 100644 index 0000000..24e7ecf --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java @@ -0,0 +1,67 @@ +package jrummikub.ai.fdsolver.constraint; + +import static jrummikub.ai.fdsolver.Satisfiability.*; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; + +import jrummikub.ai.fdsolver.Constraint; +import jrummikub.ai.fdsolver.Propagator; +import jrummikub.ai.fdsolver.Satisfiability; +import jrummikub.ai.fdsolver.Var; + +public class ComparatorConstraint<T> implements Constraint { + Var<T> x, y; + Comparator<T> comparator, reverseComparator; + ComparatorPropagator<T> trueX, trueY, falseX, falseY; + boolean allowEqual; + + ComparatorConstraint(final Comparator<T> comparator, boolean allowEqual, Var<T> x, Var<T> y) { + this.x = x; + this.y = y; + this.comparator = comparator; + this.allowEqual = allowEqual; + reverseComparator = new Comparator<T>() { + @Override + public int compare(T o1, T o2) { + return comparator.compare(o2, o1); + } + }; + trueX = new ComparatorPropagator<T>(comparator, allowEqual, x, y); + trueY = new ComparatorPropagator<T>(reverseComparator, allowEqual, y, x); + falseX = new ComparatorPropagator<T>(reverseComparator, !allowEqual, x, y); + falseY = new ComparatorPropagator<T>(comparator, !allowEqual, y, x); + } + + @Override + public Collection<Var<?>> getWatchedVars() { + return Arrays.<Var<?>>asList(x,y); + } + + @Override + public Collection<Propagator> getPropagators(boolean negate) { + if (negate) { + return Arrays.<Propagator>asList(falseX,falseY); + } else { + return Arrays.<Propagator>asList(trueX,trueY); + } + } + + @Override + public Satisfiability getSatisfiability() { + T maxX = Collections.max(x.getRange(), comparator); + T minY = Collections.min(y.getRange(), comparator); + if (comparator.compare(maxX, minY) < (allowEqual ? 1 : 0)) { + return TAUT; + } + T minX = Collections.min(x.getRange(), comparator); + T maxY = Collections.max(y.getRange(), comparator); + if (comparator.compare(maxY, minX) < (allowEqual ? 0 : 1)) { + return UNSAT; + } + return SAT; + } + +} diff --git a/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java b/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java new file mode 100644 index 0000000..b3a3089 --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java @@ -0,0 +1,42 @@ +package jrummikub.ai.fdsolver.constraint; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; + +import jrummikub.ai.fdsolver.Propagator; +import jrummikub.ai.fdsolver.Var; + +public class ComparatorPropagator<T> implements Propagator { + private Var<T> x, y; + private Comparator<T> comparator; + private boolean allowEqual; + public ComparatorPropagator(Comparator<T> comparator, boolean allowEqual, Var<T> x, Var<T> y) { + this.comparator = comparator; + this.allowEqual = allowEqual; + this.x = x; + this.y = y; + } + + @Override + public Collection<Var<?>> getWatchedVars() { + return Arrays.<Var<?>>asList(y); + } + + @Override + public void propagate() { + T maxY = Collections.max(y.getRange(), comparator); + + for(Iterator<T> i = x.iterator(); i.hasNext();) { + T value = i.next(); + int comparision = comparator.compare(value, maxY); + if (comparision > 0 || comparision == 0 && !allowEqual) { + i.remove(); + } + } + } +} diff --git a/src/jrummikub/ai/fdsolver/constraint/Filter.java b/src/jrummikub/ai/fdsolver/constraint/Filter.java new file mode 100644 index 0000000..59c880a --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/Filter.java @@ -0,0 +1,5 @@ +package jrummikub.ai.fdsolver.constraint; + +public interface Filter<T> { + public boolean accept(T value); +} diff --git a/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java b/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java new file mode 100644 index 0000000..e676882 --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java @@ -0,0 +1,65 @@ +package jrummikub.ai.fdsolver.constraint; + +import static jrummikub.ai.fdsolver.Satisfiability.SAT; +import static jrummikub.ai.fdsolver.Satisfiability.TAUT; +import static jrummikub.ai.fdsolver.Satisfiability.UNSAT; + +import java.util.Arrays; +import java.util.Collection; + +import jrummikub.ai.fdsolver.Constraint; +import jrummikub.ai.fdsolver.Propagator; +import jrummikub.ai.fdsolver.Satisfiability; +import jrummikub.ai.fdsolver.Var; + +public class FilterConstraint<T> implements Constraint { + private Var<T> var; + private Propagator trueProp, falseProp; + private Filter<T> filter; + + public FilterConstraint(final Filter<T> filter, Var<T> var) { + this.var = var; + this.filter = filter; + trueProp = new FilterPropagator<T>(filter, var); + falseProp = new FilterPropagator<T>(new Filter<T>() { + @Override + public boolean accept(T value) { + return !filter.accept(value); + } + }, var); + } + + @Override + public Collection<Var<?>> getWatchedVars() { + return Arrays.<Var<?>> asList(var); + } + + @Override + public Collection<Propagator> getPropagators(boolean negate) { + return Arrays.asList(negate ? falseProp : trueProp); + } + + @Override + public Satisfiability getSatisfiability() { + boolean any = false; + boolean all = true; + + for (T value : var.getRange()) { + boolean accepted = filter.accept(value); + if (accepted) { + any = true; + } else { + all = false; + } + } + + if (all && any) { + return TAUT; + } else if (any) { + return SAT; + } else { + return UNSAT; + } + } + +} diff --git a/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java b/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java new file mode 100644 index 0000000..80518c9 --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java @@ -0,0 +1,31 @@ +package jrummikub.ai.fdsolver.constraint; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; + +import jrummikub.ai.fdsolver.Propagator; +import jrummikub.ai.fdsolver.Var; + +public class FilterPropagator<T> implements Propagator { + private Filter<T> filter; + private Var<T> var; + + public FilterPropagator(Filter<T> filter, Var<T> var) { + this.filter = filter; + this.var = var; + } + + @Override + public Collection<Var<?>> getWatchedVars() { + return Arrays.<Var<?>>asList(var); + } + + @Override + public void propagate() { + for(Iterator<T> i = var.iterator(); i.hasNext();) { + if(!filter.accept(i.next())) + i.remove(); + } + } +} diff --git a/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java b/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java new file mode 100644 index 0000000..9bdccd2 --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java @@ -0,0 +1,18 @@ +package jrummikub.ai.fdsolver.constraint; + +import java.util.Comparator; + +import jrummikub.ai.fdsolver.Var; + +public class GreaterThan<T extends Comparable<T>> extends + ComparatorConstraint<T> { + + public GreaterThan(boolean allowEqual, Var<T> x, Var<T> y) { + super(new Comparator<T>() { + @Override + public int compare(T o1, T o2) { + return o2.compareTo(o1); + } + }, allowEqual, x, y); + } +} diff --git a/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java b/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java new file mode 100644 index 0000000..6b00ee3 --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java @@ -0,0 +1,15 @@ +package jrummikub.ai.fdsolver.constraint; + +import jrummikub.ai.fdsolver.Var; + +public class GreaterThanConst<T extends Comparable<T>> extends + FilterConstraint<T> { + public GreaterThanConst(final boolean allowEqual, Var<T> x, final T y) { + super(new Filter<T>() { + @Override + public boolean accept(T value) { + return y.compareTo(value) < (allowEqual ? 1 : 0); + } + }, x); + } +} diff --git a/src/jrummikub/ai/fdsolver/constraint/LessThan.java b/src/jrummikub/ai/fdsolver/constraint/LessThan.java new file mode 100644 index 0000000..b79252c --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/LessThan.java @@ -0,0 +1,17 @@ +package jrummikub.ai.fdsolver.constraint; + +import java.util.Comparator; + +import jrummikub.ai.fdsolver.Var; + +public class LessThan<T extends Comparable<T>> extends ComparatorConstraint<T> { + + public LessThan(boolean allowEqual, Var<T> x, Var<T> y) { + super(new Comparator<T>() { + @Override + public int compare(T o1, T o2) { + return o1.compareTo(o2); + } + }, allowEqual, x, y); + } +} diff --git a/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java b/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java new file mode 100644 index 0000000..18d8827 --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java @@ -0,0 +1,18 @@ +package jrummikub.ai.fdsolver.constraint; + +import java.util.Collection; + +import jrummikub.ai.fdsolver.Propagator; +import jrummikub.ai.fdsolver.Solver; +import jrummikub.ai.fdsolver.Var; + +public class LessThanConst<T extends Comparable<T>> extends FilterConstraint<T> { + public LessThanConst(final boolean allowEqual, Var<T> x, final T y) { + super(new Filter<T>() { + @Override + public boolean accept(T value) { + return value.compareTo(y) < (allowEqual ? 1 : 0); + } + }, x); + } +} |