From e06ba8ea1346e5045a34508648ac93150aacb01a Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Fri, 17 Jun 2011 17:41:52 +0200 Subject: Reimplemented AI (old one was too slow) git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@443 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/fdsolver/Constraint.java | 17 -- src/jrummikub/ai/fdsolver/Constraints.java | 61 ----- src/jrummikub/ai/fdsolver/Propagator.java | 9 - src/jrummikub/ai/fdsolver/Satisfiability.java | 5 - src/jrummikub/ai/fdsolver/Solver.java | 268 --------------------- src/jrummikub/ai/fdsolver/SolverMain.java | 42 ---- src/jrummikub/ai/fdsolver/Var.java | 113 --------- .../fdsolver/constraint/ComparatorConstraint.java | 74 ------ .../fdsolver/constraint/ComparatorPropagator.java | 42 ---- src/jrummikub/ai/fdsolver/constraint/Filter.java | 5 - .../ai/fdsolver/constraint/FilterConstraint.java | 65 ----- .../ai/fdsolver/constraint/FilterPropagator.java | 31 --- .../ai/fdsolver/constraint/GreaterThan.java | 18 -- .../ai/fdsolver/constraint/GreaterThanConst.java | 15 -- .../ai/fdsolver/constraint/IfConstraint.java | 108 --------- .../ai/fdsolver/constraint/IndexConstraint.java | 140 ----------- src/jrummikub/ai/fdsolver/constraint/LessThan.java | 17 -- .../ai/fdsolver/constraint/LessThanConst.java | 18 -- .../ai/fdsolver/constraint/ListSumConstraint.java | 91 ------- .../ai/fdsolver/constraint/OffsetConstraint.java | 90 ------- .../ai/fdsolver/constraint/SameConstraint.java | 69 ------ .../ai/fdsolver/constraint/SumConstraint.java | 51 ---- 22 files changed, 1349 deletions(-) delete mode 100644 src/jrummikub/ai/fdsolver/Constraint.java delete mode 100644 src/jrummikub/ai/fdsolver/Constraints.java delete mode 100644 src/jrummikub/ai/fdsolver/Propagator.java delete mode 100644 src/jrummikub/ai/fdsolver/Satisfiability.java delete mode 100644 src/jrummikub/ai/fdsolver/Solver.java delete mode 100644 src/jrummikub/ai/fdsolver/SolverMain.java delete mode 100644 src/jrummikub/ai/fdsolver/Var.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/Filter.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/GreaterThan.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/IfConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/LessThan.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/LessThanConst.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/SameConstraint.java delete mode 100644 src/jrummikub/ai/fdsolver/constraint/SumConstraint.java (limited to 'src/jrummikub/ai/fdsolver') diff --git a/src/jrummikub/ai/fdsolver/Constraint.java b/src/jrummikub/ai/fdsolver/Constraint.java deleted file mode 100644 index a046324..0000000 --- a/src/jrummikub/ai/fdsolver/Constraint.java +++ /dev/null @@ -1,17 +0,0 @@ -package jrummikub.ai.fdsolver; - -import java.util.Collection; - -public abstract class Constraint { - Collection cachedPropagators; - - public abstract Collection> getWatchedVars(); - - public abstract Collection getPropagators(boolean negate); - - public abstract Satisfiability getSatisfiability(); - - public boolean isSatisfiable() { - return getSatisfiability() != Satisfiability.UNSAT; - } -} diff --git a/src/jrummikub/ai/fdsolver/Constraints.java b/src/jrummikub/ai/fdsolver/Constraints.java deleted file mode 100644 index caa8cfa..0000000 --- a/src/jrummikub/ai/fdsolver/Constraints.java +++ /dev/null @@ -1,61 +0,0 @@ -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.ListSumConstraint; -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 sum(Var sum, List> list) { - return new ListSumConstraint(sum, list); - } - - 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/Propagator.java b/src/jrummikub/ai/fdsolver/Propagator.java deleted file mode 100644 index dfe720a..0000000 --- a/src/jrummikub/ai/fdsolver/Propagator.java +++ /dev/null @@ -1,9 +0,0 @@ -package jrummikub.ai.fdsolver; - -import java.util.Collection; - -public interface Propagator { - public abstract Collection> getWatchedVars(); - - public abstract void propagate(); -} diff --git a/src/jrummikub/ai/fdsolver/Satisfiability.java b/src/jrummikub/ai/fdsolver/Satisfiability.java deleted file mode 100644 index 9f3a23a..0000000 --- a/src/jrummikub/ai/fdsolver/Satisfiability.java +++ /dev/null @@ -1,5 +0,0 @@ -package jrummikub.ai.fdsolver; - -public enum Satisfiability { - TAUT, SAT, UNSAT -} diff --git a/src/jrummikub/ai/fdsolver/Solver.java b/src/jrummikub/ai/fdsolver/Solver.java deleted file mode 100644 index 0bdb344..0000000 --- a/src/jrummikub/ai/fdsolver/Solver.java +++ /dev/null @@ -1,268 +0,0 @@ -package jrummikub.ai.fdsolver; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.List; -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>(); - - Set> dirtyVars = new HashSet>(); - - Set> unsolvedVars = new HashSet>(); - - Set constraints = new HashSet(); - - Set dirtyConstraints = new HashSet(); - - ArrayList stack = new ArrayList(); - - boolean contradiction = false; - - static private class StackFrame { - Map, HashSet> invalidatedValues = new HashMap, HashSet>(); - Var branchVar; - Object branchValue; - HashSet finishedConstraints = new HashSet(); - - public void invalidate(Var var, T invalid) { - HashSet values = (HashSet) invalidatedValues.get(var); - if (values == null) { - invalidatedValues.put(var, - new HashSet(Arrays.asList(invalid))); - } else { - values.add(invalid); - } - } - - @Override - public String toString() { - return "StackItem [invalidatedValues=" + invalidatedValues + "]"; - } - } - - public Solver() { - stack.add(new StackFrame()); - } - - private boolean isSolved() { - return dirtyVars.isEmpty() && unsolvedVars.isEmpty(); - } - - public boolean solve() { - do { - solveStep(); - } while (!(contradiction || isSolved())); - return !contradiction; - } - - public void solveStep() { - if (isSolved()) { - contradiction = true; - } else { - propagateAll(); - } - if (contradiction) { - if (stack.size() == 1) { - return; - } - backtrack(); - } else if (unsolvedVars.isEmpty()) { - return; - } else { - branch(); - } - } - - public void propagateEach() { - List> oldDirtyVars = new ArrayList>(dirtyVars); - dirtyVars.clear(); - Collections.sort(oldDirtyVars); - outerLoop: for(Var dirtyVar : oldDirtyVars) { - for (Constraint constraint : dirtyVar.getConstraints()) { - dirtyConstraints.add(constraint); - for (Propagator propagator : constraint.cachedPropagators) { - if (propagator.getWatchedVars().contains(dirtyVar)) { - propagator.propagate(); - if (contradiction) { - break outerLoop; - } - } - } - } - } - } - - public void propagateAll() { - int i = 0; - while (!(dirtyVars.isEmpty() || contradiction)) { - i++; - if (i == 50) { - cleanUpConstraints(); - i = 0; - } else { - propagateEach(); - } - } - cleanUpConstraints(); - } - - private void cleanUpConstraints() { - for (Constraint constraint : dirtyConstraints) { - Satisfiability sat = constraint.getSatisfiability(); - if (sat == UNSAT) { - contradiction = true; - break; - } - if (sat == TAUT) { - finishedConstraint(constraint, null); - } - } - dirtyConstraints.clear(); - } - - public void addVar(Var var) { - vars.add(var); - if (var.getRange().size() != 1) { - unsolvedVars.add(var); - } - } - - public void addConstraint(Constraint constraint) { - constraint.cachedPropagators = constraint.getPropagators(false); - constraints.add(constraint); - for (Var var : constraint.getWatchedVars()) { - var.makeDirty(); - var.getConstraints().add(constraint); - } - } - - // backtracking and logging - - void branch() { - branchOn(Collections.min(unsolvedVars)); - } - - @SuppressWarnings("unchecked") - void branchOn(Var var) { - - Set range = var.getRange(); - int n = (int) (Math.random() * range.size()); - Iterator it = range.iterator(); - for (int i = 0; i < n; i++) { - it.next(); - } - Object value = it.next(); - branchWith((Var) var, value); - } - - void branchWith(Var var, T value) { - StackFrame stackFrame = new StackFrame(); - stackFrame.branchVar = var; - stackFrame.branchValue = value; - stack.add(stackFrame); - var.choose(value); - } - - private StackFrame getTopStackFrame() { - return stack.get(stack.size() - 1); - } - - void logInvalidation(Var var, T invalid) { - getTopStackFrame().invalidate(var, invalid); - if (var.getRange().size() == 1) { - unsolvedVars.remove(var); - } - } - - private void finishedConstraint(Constraint constraint, Var currentVar) { - for (Var var : constraint.getWatchedVars()) { - if (var != currentVar) { - var.getConstraints().remove(constraint); - } - } - constraints.remove(constraint); - getTopStackFrame().finishedConstraints.add(constraint); - } - - @SuppressWarnings("unchecked") - // This would need rank-2 types which java lacks - private void rollback(StackFrame item) { - for (Map.Entry, HashSet> entry : item.invalidatedValues - .entrySet()) { - Var var = (Var) entry.getKey(); - HashSet values = (HashSet) entry.getValue(); - var.getRange().addAll(values); - if (var.getRange().size() != 1) { - unsolvedVars.add(var); - } else { - unsolvedVars.remove(var); - } - var.makeDirty(); // TODO think a bit more about this - } - for (Constraint constraint : item.finishedConstraints) { - for (Var var : constraint.getWatchedVars()) { - var.getConstraints().add(constraint); - } - constraints.add(constraint); - } - } - - @SuppressWarnings("unchecked") - void backtrack() { - contradiction = false; - StackFrame topFrame = getTopStackFrame(); - rollback(topFrame); - stack.remove(stack.size() - 1); - ((Var) topFrame.branchVar).invalidate(topFrame.branchValue); - } - - // factory methods for vars - - public Var makeRangeVar(int low, int high) { - ArrayList range = new ArrayList(); - for (int i = low; i <= high; i++) { - range.add(i); - } - return makeVar(range); - } - - public Var makeBoolVar() { - return makeVar(true, false); - } - - public Var makeVar(Collection range) { - Var var = new Var(this, range); - addVar(var); - return var; - } - - 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/SolverMain.java b/src/jrummikub/ai/fdsolver/SolverMain.java deleted file mode 100644 index 4750675..0000000 --- a/src/jrummikub/ai/fdsolver/SolverMain.java +++ /dev/null @@ -1,42 +0,0 @@ -package jrummikub.ai.fdsolver; - - -public class SolverMain { - - /* - * eingabe: liste handsteinen + liste tischsteinen - * - * foreach stein: stein id (durchlaufend nummeriert) Var onTable = - * tisch ? {true}, {true, false} Var value = {N} Var - * color = {C} Var nachbarL,R = {-1, 0...steinanzahl} Var - * groupOrRun - * - * nachbarR != -1 => nachbarL[nachbarR[id]] == id nachbarL != -1 => - * nachbarR[nachbarL[id]] == id - * - * nachbarR != -1 => gOR[nachbarR[id]] = gOR nachbarL != -1 => - * gOR[nachbarL[id]] = gOR - * - * nachbar{R,L} != -1 => group <=> value[{R,L}] == value nachbar{R,L} != -1 - * && group => color[{R,L}] {<,>} color // hier auch <=> ? - * - * nachbar{R,L} != -1 => run <=> color[{R,L}] == color nachbar{R,L} != -1 => - * run <=> value[{R,L}] == value {+,-} 1 - * - * Var pos von {links, rechts} + constraints - * - * links + rechts >= 3 - * - * foreach handstein: Var badness = onTable ? ### (z. B. 1) : 0 - * - * totalBadness = sum(all badness) - * - * foreach joker: Var value = {-1, 1..13} Var color = - * {F, C0..C3} onTable == false <=> value == -1 same with color - * - * joker sind sortiert - */ - public static void main(String[] args) { - } - -} diff --git a/src/jrummikub/ai/fdsolver/Var.java b/src/jrummikub/ai/fdsolver/Var.java deleted file mode 100644 index e885cef..0000000 --- a/src/jrummikub/ai/fdsolver/Var.java +++ /dev/null @@ -1,113 +0,0 @@ -package jrummikub.ai.fdsolver; - -import java.util.Collection; -import java.util.HashSet; -import java.util.Iterator; - -public class Var implements Comparable> { - private Solver solver; - private HashSet range; - private HashSet constraints; - private T recorded; - - public Var(Solver solver, Collection range) { - this.solver = solver; - this.range = new HashSet(range); - constraints = new HashSet(); - } - - public T getValue() { - if (range.size() != 1) - return null; - return range.iterator().next(); - } - - public HashSet getRange() { - return range; - } - - void choose(T value) { - for (Iterator i = this.iterator(); i.hasNext();) { - if (i.next() != value) { - i.remove(); - } - } - } - - void makeDirty() { - this.solver.dirtyVars.add(this); - } - - public void invalidate(T value) { - range.remove(value); - solver.logInvalidation(this, value); - makeDirty(); - if (range.size() == 0) { - solver.contradiction = true; - } - } - - HashSet getConstraints() { - return constraints; - } - - public Iterator iterator() { - final Iterator iterator = range.iterator(); - return new Iterator() { - T lastValue; - - @Override - public boolean hasNext() { - return iterator.hasNext(); - } - - @Override - public T next() { - lastValue = iterator.next(); - return lastValue; - } - - @Override - public void remove() { - // TODO logging - iterator.remove(); - solver.logInvalidation(Var.this, lastValue); - makeDirty(); - if (range.size() == 0) { - solver.contradiction = true; - } - } - }; - } - - void record() { - recorded = getValue(); - } - - void restore() { - range.clear(); - range.add(recorded); - } - - @Override - public String toString() { - return "Var" + range; - } - - private int neighborCount() { - /* int count = 0; - for (Constraint constraint : constraints) { - count += constraint.getWatchedVars().size(); - } */ - return constraints.size(); - } - - @Override - public int compareTo(Var other) { - int rangeCompare = ((Integer)range.size()).compareTo(other.range.size()); - if (rangeCompare != 0) - return rangeCompare; - return -((Integer)neighborCount()).compareTo(other.neighborCount()); - } - -} diff --git a/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java b/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java deleted file mode 100644 index 019de92..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java +++ /dev/null @@ -1,74 +0,0 @@ -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 java.util.NoSuchElementException; - -import jrummikub.ai.fdsolver.Constraint; -import jrummikub.ai.fdsolver.Propagator; -import jrummikub.ai.fdsolver.Satisfiability; -import jrummikub.ai.fdsolver.Var; - -public class ComparatorConstraint extends Constraint { - Var x, y; - Comparator comparator, reverseComparator; - ComparatorPropagator trueX, trueY, falseX, falseY; - boolean allowEqual; - - ComparatorConstraint(final Comparator comparator, boolean allowEqual, - Var x, Var y) { - this.x = x; - this.y = y; - this.comparator = comparator; - this.allowEqual = allowEqual; - reverseComparator = new Comparator() { - @Override - public int compare(T o1, T o2) { - return comparator.compare(o2, o1); - } - }; - trueX = new ComparatorPropagator(comparator, allowEqual, x, y); - trueY = new ComparatorPropagator(reverseComparator, allowEqual, y, x); - falseX = new ComparatorPropagator(reverseComparator, !allowEqual, x, - y); - falseY = new ComparatorPropagator(comparator, !allowEqual, y, x); - } - - @Override - public Collection> getWatchedVars() { - return Arrays.> asList(x, y); - } - - @Override - public Collection getPropagators(boolean negate) { - if (negate) { - return Arrays. asList(falseX, falseY); - } else { - return Arrays. asList(trueX, trueY); - } - } - - @Override - public Satisfiability getSatisfiability() { - try { - 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; - } catch (NoSuchElementException e) { - return UNSAT; - } - } - -} diff --git a/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java b/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java deleted file mode 100644 index b3a3089..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java +++ /dev/null @@ -1,42 +0,0 @@ -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 implements Propagator { - private Var x, y; - private Comparator comparator; - private boolean allowEqual; - public ComparatorPropagator(Comparator comparator, boolean allowEqual, Var x, Var y) { - this.comparator = comparator; - this.allowEqual = allowEqual; - this.x = x; - this.y = y; - } - - @Override - public Collection> getWatchedVars() { - return Arrays.>asList(y); - } - - @Override - public void propagate() { - T maxY = Collections.max(y.getRange(), comparator); - - for(Iterator 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 deleted file mode 100644 index 59c880a..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/Filter.java +++ /dev/null @@ -1,5 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -public interface Filter { - public boolean accept(T value); -} diff --git a/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java b/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java deleted file mode 100644 index d01a109..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java +++ /dev/null @@ -1,65 +0,0 @@ -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 extends Constraint { - private Var var; - private Propagator trueProp, falseProp; - private Filter filter; - - public FilterConstraint(final Filter filter, Var var) { - this.var = var; - this.filter = filter; - trueProp = new FilterPropagator(filter, var); - falseProp = new FilterPropagator(new Filter() { - @Override - public boolean accept(T value) { - return !filter.accept(value); - } - }, var); - } - - @Override - public Collection> getWatchedVars() { - return Arrays.> asList(var); - } - - @Override - public Collection 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 deleted file mode 100644 index 80518c9..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java +++ /dev/null @@ -1,31 +0,0 @@ -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 implements Propagator { - private Filter filter; - private Var var; - - public FilterPropagator(Filter filter, Var var) { - this.filter = filter; - this.var = var; - } - - @Override - public Collection> getWatchedVars() { - return Arrays.>asList(var); - } - - @Override - public void propagate() { - for(Iterator 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 deleted file mode 100644 index 9bdccd2..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java +++ /dev/null @@ -1,18 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -import java.util.Comparator; - -import jrummikub.ai.fdsolver.Var; - -public class GreaterThan> extends - ComparatorConstraint { - - public GreaterThan(boolean allowEqual, Var x, Var y) { - super(new Comparator() { - @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 deleted file mode 100644 index 6b00ee3..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java +++ /dev/null @@ -1,15 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -import jrummikub.ai.fdsolver.Var; - -public class GreaterThanConst> extends - FilterConstraint { - public GreaterThanConst(final boolean allowEqual, Var x, final T y) { - super(new Filter() { - @Override - public boolean accept(T value) { - return y.compareTo(value) < (allowEqual ? 1 : 0); - } - }, x); - } -} diff --git a/src/jrummikub/ai/fdsolver/constraint/IfConstraint.java b/src/jrummikub/ai/fdsolver/constraint/IfConstraint.java deleted file mode 100644 index fc1b484..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/IfConstraint.java +++ /dev/null @@ -1,108 +0,0 @@ -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 extends 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.isSatisfiable()) { - 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 deleted file mode 100644 index 6698282..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java +++ /dev/null @@ -1,140 +0,0 @@ -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 org.w3c.dom.ranges.Range; - -import jrummikub.ai.fdsolver.Constraint; -import jrummikub.ai.fdsolver.Propagator; -import jrummikub.ai.fdsolver.Satisfiability; -import jrummikub.ai.fdsolver.Var; - -public class IndexConstraint extends 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 invUnion = new HashSet(target.getRange()); - for (int i : index.getRange()) { - invUnion.removeAll(list.get(i).getRange()); - if (invUnion.isEmpty()) { - return; - } - } - for (T val : invUnion) { - target.invalidate(val); - } - }; - } - - 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(); - Var item = list.get(id); - if (Collections.disjoint(item.getRange(), target.getRange())) { - 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 boolean isSatisfiable() { - for (int i : index.getRange()) { - if(!Collections.disjoint(list.get(i).getRange(), target.getRange())) { - return true; - } - } - return false; - } - - @Override - public Satisfiability getSatisfiability() { - boolean sat = isSatisfiable(); - if (!sat) { - return Satisfiability.UNSAT; - } - if (target.getRange().size() > 1) - return Satisfiability.SAT; - for (int i : index.getRange()) { - Var var = list.get(i); - if (var.getRange().size() > 1) - return Satisfiability.SAT; - if(var.getValue() != target.getValue()) { - return Satisfiability.SAT; - } - } - return Satisfiability.TAUT; - } -} diff --git a/src/jrummikub/ai/fdsolver/constraint/LessThan.java b/src/jrummikub/ai/fdsolver/constraint/LessThan.java deleted file mode 100644 index b79252c..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/LessThan.java +++ /dev/null @@ -1,17 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -import java.util.Comparator; - -import jrummikub.ai.fdsolver.Var; - -public class LessThan> extends ComparatorConstraint { - - public LessThan(boolean allowEqual, Var x, Var y) { - super(new Comparator() { - @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 deleted file mode 100644 index 18d8827..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java +++ /dev/null @@ -1,18 +0,0 @@ -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> extends FilterConstraint { - public LessThanConst(final boolean allowEqual, Var x, final T y) { - super(new Filter() { - @Override - public boolean accept(T value) { - return value.compareTo(y) < (allowEqual ? 1 : 0); - } - }, x); - } -} diff --git a/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java b/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java deleted file mode 100644 index 22f480f..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java +++ /dev/null @@ -1,91 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -import java.util.ArrayList; -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 java.util.Set; - -import jrummikub.ai.fdsolver.Constraint; -import jrummikub.ai.fdsolver.Propagator; -import jrummikub.ai.fdsolver.Satisfiability; -import jrummikub.ai.fdsolver.Var; - -public class ListSumConstraint extends Constraint { - Var sum; - List> list; - List> vars = new ArrayList>(); - - public ListSumConstraint(Var sum, List> list) { - this.sum = sum; - this.list = list; - vars.add(sum); - vars.addAll(list); - } - - @Override - public Collection> getWatchedVars() { - return vars; - } - - @Override - public Collection getPropagators(boolean negate) { - return Collections.emptyList(); - } - - @Override - public Satisfiability getSatisfiability() { - List values = new ArrayList(); - int valueSum = 0; - boolean isTaut = sum.getRange().size()==1; - for (Var var : list) { - Iterator it = var.getRange().iterator(); - int value = it.next(); - if (it.hasNext()) - isTaut = false; - values.add(value); - valueSum += value; - } - if (isTaut) { - if (valueSum == sum.getValue()) { - return Satisfiability.TAUT; - } else { - return Satisfiability.UNSAT; - } - } - - Set reachableValues = new HashSet(); - Set newValues = new HashSet(); - reachableValues.add(valueSum); - - if (sum.getRange().contains(valueSum)) { - return Satisfiability.SAT; - } - - for (int i = 0; i < values.size(); i++) { - Var var = list.get(i); - int offset = values.get(i); - for (int x : var.getRange()) { - if (x == offset) - continue; - newValues.clear(); - for (int y : reachableValues) { - int newValue = x + y - offset; - if (!reachableValues.contains(newValue)) { - newValues.add(x + y - offset); - } - } - if (!Collections.disjoint(sum.getRange(), newValues)) { - return Satisfiability.SAT; - } - reachableValues.addAll(newValues); - } - } - - return Satisfiability.UNSAT; - } - -} diff --git a/src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java b/src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java deleted file mode 100644 index eb72df8..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java +++ /dev/null @@ -1,90 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -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 extends 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() { - boolean disjoint = true; - if (x.getRange().size() < y.getRange().size()) { - for (int xv : x.getRange()) { - if (y.getRange().contains(xv + offset)) { - disjoint = false; - break; - } - } - } else { - for (int yv : y.getRange()) { - if (x.getRange().contains(yv - offset)) { - disjoint = false; - break; - } - } - } - - if (disjoint) { - 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 deleted file mode 100644 index 7fc0025..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/SameConstraint.java +++ /dev/null @@ -1,69 +0,0 @@ -package jrummikub.ai.fdsolver.constraint; - -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -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 extends 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() { - if (Collections.disjoint(x.getRange(), y.getRange())) { - 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 deleted file mode 100644 index c96a751..0000000 --- a/src/jrummikub/ai/fdsolver/constraint/SumConstraint.java +++ /dev/null @@ -1,51 +0,0 @@ -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 extends 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