From 7568f3782466531fe04fc14a40dc4d3a393c1fb9 Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Tue, 14 Jun 2011 17:48:22 +0200 Subject: Added TurnLogic with rule variables and constraints git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@436 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/fdsolver/Constraints.java | 56 +++++++++ src/jrummikub/ai/fdsolver/Solver.java | 19 +-- src/jrummikub/ai/fdsolver/Var.java | 16 ++- .../ai/fdsolver/constraint/IfConstraint.java | 108 +++++++++++++++++ .../ai/fdsolver/constraint/IndexConstraint.java | 134 +++++++++++++++++++++ .../ai/fdsolver/constraint/OffsetConstraint.java | 77 ++++++++++++ .../ai/fdsolver/constraint/SameConstraint.java | 70 +++++++++++ .../ai/fdsolver/constraint/SumConstraint.java | 51 ++++++++ 8 files changed, 519 insertions(+), 12 deletions(-) create mode 100644 src/jrummikub/ai/fdsolver/Constraints.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/IfConstraint.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/SameConstraint.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/SumConstraint.java (limited to 'src/jrummikub/ai/fdsolver') 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 cond, Constraint c) { + return new IfConstraint(false, cond, c); + } + + public static Constraint unless(Var cond, Constraint c) { + return new IfConstraint(true, cond, c); + } + + + public static Constraint index(Var target, Var index, List> list) { + return new IndexConstraint(target, index, list); + } + + public static Constraint constant(Var target, final T constant) { + return new FilterConstraint(new Filter() { + @Override + public boolean accept(T value) { + return value.equals(constant); + } + }, target); + } + + public static Constraint offset(int offset, Var x, Var y) { + return new OffsetConstraint(offset, x, y); + } + + public static Constraint same(Var x, Var y) { + return new SameConstraint(x, y); + } + + public static Constraint sum(Var x, Var y, Var z) { + return new SumConstraint(x, y, z); + } + + public static > Constraint lessThan(Var x, Var y) { + return new LessThan(false, x, y); + } + + public static > Constraint lessThanEq(Var x, Var y) { + return new LessThan(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> vars = new HashSet>(); @@ -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 i = dirtyVar.getConstraints().iterator(); i.hasNext();) { + outerLoop: for (Iterator 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 Var 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 implements Comparable> { 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 implements Comparable> { } 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 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 condition; + Constraint child; + Collection> vars; + boolean negateCond; + + public IfConstraint(boolean negateCond, Var condition, Constraint child) { + this.condition = condition; + this.child = child; + this.negateCond = negateCond; + vars = new ArrayList>(); + vars.addAll(child.getWatchedVars()); + vars.add(condition); + } + + @Override + public Collection> getWatchedVars() { + return vars; + } + + private class IfPropagator implements Propagator { + Propagator child; + Collection> vars; + public IfPropagator(Propagator child) { + this.child = child; + vars = new ArrayList>(); + vars.addAll(child.getWatchedVars()); + vars.add(condition); + } + + @Override + public Collection> getWatchedVars() { + return vars; + } + + @Override + public void propagate() { + if(condition.getRange().contains(negateCond)) { + return; + } + child.propagate(); + } + } + + private class FailPropagator implements Propagator { + @Override + public Collection> getWatchedVars() { + return child.getWatchedVars(); + } + + @Override + public void propagate() { + if (child.getSatisfiability() == Satisfiability.UNSAT) { + condition.invalidate(!negateCond); + } + } + } + + @Override + public Collection getPropagators(boolean negate) { + List props = new ArrayList(); + if (negate) { + props.add(new FilterPropagator(new Filter() { + @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 implements Constraint { + Var target; + Var index; + List> list; + Collection> vars = new ArrayList>(); + Collection> varsNoTarget = new ArrayList>(); + Collection> varsNoIndex = new ArrayList>(); + + public IndexConstraint(Var target, Var index, List> 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> getWatchedVars() { + return vars; + } + + private class UnionProp implements Propagator { + @Override + public Collection> getWatchedVars() { + return varsNoTarget; + } + + @Override + public void propagate() { + HashSet union = new HashSet(); + for (int i : index.getRange()) { + union.addAll(list.get(i).getRange()); + } + for (Iterator i = target.iterator(); i.hasNext();) { + T val = i.next(); + if (!union.contains(val)) { + i.remove(); + } + } + }; + } + + private class IndexProp implements Propagator { + @Override + public Collection> getWatchedVars() { + return varsNoIndex; + } + + @Override + public void propagate() { + for (Iterator i = index.iterator(); i.hasNext();) { + int id = i.next(); + HashSet range = new HashSet(target.getRange()); + range.retainAll(list.get(id).getRange()); + if (range.isEmpty()) { + i.remove(); + } + } + } + } + + private class VarProp implements Propagator { + @Override + public Collection> getWatchedVars() { + return Arrays.asList(target, index); + } + + @Override + public void propagate() { + if (index.getRange().size() != 1) + return; + int id = index.getValue(); + Var var = list.get(id); + for(Iterator i = var.iterator(); i.hasNext();) { + if (!target.getRange().contains(i.next())) { + i.remove(); + } + } + } + + } + + @Override + public Collection getPropagators(boolean negate) { + if (negate) { + return Collections.emptyList(); + } + return Arrays. asList(new UnionProp(), new IndexProp(), new VarProp()); + } + + @Override + public Satisfiability getSatisfiability() { + HashSet union = new HashSet(); + 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 x, y; + int offset; + Propagator propX, propY; + + public OffsetConstraint(int offset, Var x, Var 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> getWatchedVars() { + return Arrays.> asList(x, y); + } + + private class OffsetProp implements Propagator { + private Var x, y; + private int offset; + public OffsetProp(int offset, Var x, Var y) { + this.offset = offset; + this.x = x; + this.y = y; + } + + @Override + public Collection> getWatchedVars() { + return Arrays.>asList(y); + } + + @Override + public void propagate() { + for(Iterator i = x.iterator(); i.hasNext();) { + if(!y.getRange().contains(i.next() + offset)) { + i.remove(); + } + } + } + } + + + @Override + public Collection getPropagators(boolean negate) { + return Arrays.asList(propX, propY); + } + + @Override + public Satisfiability getSatisfiability() { + HashSet shiftedRange = new HashSet(); + 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 implements Constraint { + private Var x, y; + Propagator propX, propY; + + public SameConstraint(Var x, Var y) { + this.x = x; + this.y = y; + propX = new SameProp(x, y); + propY = new SameProp(y, x); + } + + @Override + public Collection> getWatchedVars() { + return Arrays.> asList(x, y); + } + + private class SameProp implements Propagator { + private Var x, y; + public SameProp(Var x, Var y) { + this.x = x; + this.y = y; + } + + @Override + public Collection> getWatchedVars() { + return Arrays.>asList(y); + } + + @Override + public void propagate() { + for(Iterator i = x.iterator(); i.hasNext();) { + if(!y.getRange().contains(i.next())) { + i.remove(); + } + } + } + } + + + @Override + public Collection getPropagators(boolean negate) { + return Arrays.asList(propX, propY); + } + + @Override + public Satisfiability getSatisfiability() { + HashSet range = new HashSet(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 x, y, z; + + public SumConstraint(Var x, Var y, Var z) { + this.x = x; + this.y = y; + this.z = z; + } + + @Override + public Collection> getWatchedVars() { + return Arrays.> asList(x, y, z); + } + + @Override + public Collection getPropagators(boolean negate) { + // TODO Auto-generated method stub + return Collections.emptyList(); + } + + @Override + public Satisfiability getSatisfiability() { + // HashSet intersection = new HashSet(); + 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; + } +} -- cgit v1.2.3