diff options
Diffstat (limited to 'src/jrummikub/ai/fdsolver')
| -rw-r--r-- | src/jrummikub/ai/fdsolver/Constraints.java | 56 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/Solver.java | 19 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/Var.java | 16 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/constraint/IfConstraint.java | 108 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java | 134 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java | 77 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/constraint/SameConstraint.java | 70 | ||||
| -rw-r--r-- | src/jrummikub/ai/fdsolver/constraint/SumConstraint.java | 51 |
8 files changed, 519 insertions, 12 deletions
diff --git a/src/jrummikub/ai/fdsolver/Constraints.java b/src/jrummikub/ai/fdsolver/Constraints.java new file mode 100644 index 0000000..0885d2a --- /dev/null +++ b/src/jrummikub/ai/fdsolver/Constraints.java @@ -0,0 +1,56 @@ +package jrummikub.ai.fdsolver; + +import java.util.List; + +import jrummikub.ai.fdsolver.constraint.Filter; +import jrummikub.ai.fdsolver.constraint.FilterConstraint; +import jrummikub.ai.fdsolver.constraint.IfConstraint; +import jrummikub.ai.fdsolver.constraint.IndexConstraint; +import jrummikub.ai.fdsolver.constraint.LessThan; +import jrummikub.ai.fdsolver.constraint.OffsetConstraint; +import jrummikub.ai.fdsolver.constraint.SameConstraint; +import jrummikub.ai.fdsolver.constraint.SumConstraint; + +public class Constraints { + public static Constraint when(Var<Boolean> cond, Constraint c) { + return new IfConstraint(false, cond, c); + } + + public static Constraint unless(Var<Boolean> cond, Constraint c) { + return new IfConstraint(true, cond, c); + } + + + public static <T> Constraint index(Var<T> target, Var<Integer> index, List<Var<T>> list) { + return new IndexConstraint<T>(target, index, list); + } + + public static <T> Constraint constant(Var<T> target, final T constant) { + return new FilterConstraint<T>(new Filter<T>() { + @Override + public boolean accept(T value) { + return value.equals(constant); + } + }, target); + } + + public static Constraint offset(int offset, Var<Integer> x, Var<Integer> y) { + return new OffsetConstraint(offset, x, y); + } + + public static <T> Constraint same(Var<T> x, Var<T> y) { + return new SameConstraint<T>(x, y); + } + + public static Constraint sum(Var<Integer> x, Var<Integer> y, Var<Integer> z) { + return new SumConstraint(x, y, z); + } + + public static <T extends Comparable<T>> Constraint lessThan(Var<T> x, Var<T> y) { + return new LessThan<T>(false, x, y); + } + + public static <T extends Comparable<T>> Constraint lessThanEq(Var<T> x, Var<T> y) { + return new LessThan<T>(true, x, y); + } +} diff --git a/src/jrummikub/ai/fdsolver/Solver.java b/src/jrummikub/ai/fdsolver/Solver.java index c47b1c1..c3ede1b 100644 --- a/src/jrummikub/ai/fdsolver/Solver.java +++ b/src/jrummikub/ai/fdsolver/Solver.java @@ -11,6 +11,10 @@ import java.util.Map; import java.util.Set; import static jrummikub.ai.fdsolver.Satisfiability.*; +/** + * The Solver class is the Main Constraint Propagator (MCP) that tries to find a + * labeling of all variables that satisfies all given constraints. + */ public class Solver { Set<Var<?>> vars = new HashSet<Var<?>>(); @@ -80,9 +84,10 @@ public class Solver { } public void propagateOnce() { - Var<?> dirtyVar = Collections.max(dirtyVars); + Var<?> dirtyVar = Collections.min(dirtyVars); dirtyVars.remove(dirtyVar); - outerLoop: for (Iterator<Constraint> i = dirtyVar.getConstraints().iterator(); i.hasNext();) { + outerLoop: for (Iterator<Constraint> i = dirtyVar.getConstraints() + .iterator(); i.hasNext();) { Constraint constraint = i.next(); Satisfiability sat = constraint.getSatisfiability(); if (sat == UNSAT) { @@ -130,14 +135,14 @@ public class Solver { // backtracking and logging void branch() { - branchOn(unsolvedVars.iterator().next()); + branchOn(Collections.min(unsolvedVars)); } @SuppressWarnings("unchecked") void branchOn(Var<?> var) { - + Set<?> range = var.getRange(); - int n = (int)(Math.random() * range.size()); + int n = (int) (Math.random() * range.size()); Iterator<?> it = range.iterator(); for (int i = 0; i < n; i++) { it.next(); @@ -230,13 +235,13 @@ public class Solver { public <T> Var<T> makeVar(T... range) { return makeVar(Arrays.asList(range)); } - + public void record() { for (Var<?> var : vars) { var.record(); } } - + public void restore() { for (Var<?> var : vars) { var.restore(); diff --git a/src/jrummikub/ai/fdsolver/Var.java b/src/jrummikub/ai/fdsolver/Var.java index e023f34..3124e8b 100644 --- a/src/jrummikub/ai/fdsolver/Var.java +++ b/src/jrummikub/ai/fdsolver/Var.java @@ -38,7 +38,7 @@ public class Var<T> implements Comparable<Var<T>> { this.solver.dirtyVars.add(this); } - void invalidate(T value) { + public void invalidate(T value) { range.remove(value); solver.logInvalidation(this, value); makeDirty(); @@ -92,19 +92,25 @@ public class Var<T> implements Comparable<Var<T>> { } private int neighborCount() { - int count = 0; + /* int count = 0; for (Constraint constraint : constraints) { count += constraint.getWatchedVars().size(); - } - return count; + } */ + return constraints.size(); + } + + private double fitness() { + return range.size();//neighborCount(); } @Override public int compareTo(Var<T> other) { + return ((Double)fitness()).compareTo(other.fitness()); + /* int rangeCompare = ((Integer)range.size()).compareTo(other.range.size()); if (rangeCompare != 0) return rangeCompare; - return ((Integer)neighborCount()).compareTo(other.neighborCount()); + return -((Integer)neighborCount()).compareTo(other.neighborCount());*/ } } 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; + } +} |