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/TurnLogic.java | 345 +++++++++++++++++++++ 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 +++ 9 files changed, 864 insertions(+), 12 deletions(-) create mode 100644 src/jrummikub/ai/TurnLogic.java 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') diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java new file mode 100644 index 0000000..dcb95fc --- /dev/null +++ b/src/jrummikub/ai/TurnLogic.java @@ -0,0 +1,345 @@ +package jrummikub.ai; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import jrummikub.ai.fdsolver.Constraint; +import jrummikub.ai.fdsolver.Solver; +import jrummikub.ai.fdsolver.Var; +import jrummikub.ai.fdsolver.constraint.IfConstraint; +import jrummikub.ai.fdsolver.constraint.IndexConstraint; +import jrummikub.ai.fdsolver.constraint.LessThan; +import jrummikub.model.GameSettings; +import jrummikub.model.Stone; +import jrummikub.model.StoneColor; +import static jrummikub.ai.fdsolver.Constraints.*; + +/** + * Provides Humanlike Advanced Logic (HAL) that models the options given to a + * player in a turn to the Solver MCP. + */ +public class TurnLogic { + private Solver solver = new Solver(); + private GameSettings settings; + private int stoneCount; + private int maxSetSize; + + private Var trueVar; + + private List> onTable = new ArrayList>(); + + private List> stoneValue = new ArrayList>(); + private List> leftStoneValue = new ArrayList>(); + private List> rightStoneValue = new ArrayList>(); + + private List> stoneColor = new ArrayList>(); + private List> leftStoneColor = new ArrayList>(); + private List> rightStoneColor = new ArrayList>(); + + private List> lowCount = new ArrayList>(); + private List> leftLowCount = new ArrayList>(); + private List> rightLowCount = new ArrayList>(); + + private List> highCount = new ArrayList>(); + private List> leftHighCount = new ArrayList>(); + private List> rightHighCount = new ArrayList>(); + + private List> setSize = new ArrayList>(); + + private List> isRun = new ArrayList>(); + + private List> leftNeighbor = new ArrayList>(); + private List> rightNeighbor = new ArrayList>(); + + private List> stoneID = new ArrayList>(); + + private List> hasLeftNeighbor = new ArrayList>(); + private List> hasRightNeighbor = new ArrayList>(); + + private List isJoker = new ArrayList(); + + public TurnLogic(GameSettings settings, Collection tableStones, + Collection handStones) { + this.settings = settings; + stoneCount = tableStones.size() + handStones.size(); + maxSetSize = Math.max(settings.getHighestValue(), settings + .getStoneColors().size()); + + trueVar = solver.makeVar(true); + + int i = 0; + for (Stone stone : tableStones) { + addStone(i, true, stone); + i++; + } + for (Stone stone : handStones) { + addStone(i, false, stone); + i++; + } + + for (i = 0; i < stoneCount; i++) { + addConstraints(i); + } + } + + private void addStone(int i, boolean table, Stone stone) { + if (table) { + onTable.add(trueVar); + } else { + onTable.add(solver.makeBoolVar()); + } + isJoker.add(stone.isJoker()); + if (stone.isJoker()) { + stoneValue.add(solver.makeRangeVar(1, settings.getHighestValue())); + stoneColor.add(solver.makeVar(settings.getStoneColors())); + } else { + stoneValue.add(solver.makeVar(stone.getValue())); + stoneColor.add(solver.makeVar(stone.getColor())); + } + + leftStoneValue.add(solver.makeRangeVar(1, settings.getHighestValue())); + rightStoneValue.add(solver.makeRangeVar(1, settings.getHighestValue())); + leftStoneColor.add(solver.makeVar(settings.getStoneColors())); + rightStoneColor.add(solver.makeVar(settings.getStoneColors())); + + lowCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + leftLowCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + rightLowCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + + highCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + leftHighCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + rightHighCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + + setSize.add(solver.makeRangeVar(2, maxSetSize - 1)); + + isRun.add(solver.makeBoolVar()); + + leftNeighbor.add(solver.makeRangeVar(0, stoneCount - 1)); + rightNeighbor.add(solver.makeRangeVar(0, stoneCount - 1)); + + stoneID.add(solver.makeVar(i)); + + hasLeftNeighbor.add(solver.makeBoolVar()); + hasRightNeighbor.add(solver.makeBoolVar()); + } + + private void add(Constraint c) { + solver.addConstraint(c); + } + + private void addConstraints(int i) { + // Linking of neighbors + add(when(hasLeftNeighbor.get(i), + index(stoneID.get(i), leftNeighbor.get(i), rightNeighbor))); + add(unless(hasLeftNeighbor.get(i), constant(leftNeighbor.get(i), 0))); + add(when(hasLeftNeighbor.get(i), + index(trueVar, leftNeighbor.get(i), hasRightNeighbor))); + add(when(hasRightNeighbor.get(i), + index(stoneID.get(i), rightNeighbor.get(i), leftNeighbor))); + add(unless(hasRightNeighbor.get(i), constant(rightNeighbor.get(i), 0))); + add(when(hasRightNeighbor.get(i), + index(trueVar, rightNeighbor.get(i), hasLeftNeighbor))); + // hand stones have no neighbors + add(unless(onTable.get(i), constant(hasLeftNeighbor.get(i), false))); + add(unless(onTable.get(i), constant(hasRightNeighbor.get(i), false))); + + // low/high counts and size + add(unless(hasLeftNeighbor.get(i), constant(lowCount.get(i), 0))); + add(unless(hasRightNeighbor.get(i), constant(highCount.get(i), 0))); + + add(when(hasLeftNeighbor.get(i), + index(leftLowCount.get(i), leftNeighbor.get(i), lowCount))); + add(unless(hasLeftNeighbor.get(i), constant(leftLowCount.get(i), 0))); + + add(when(hasRightNeighbor.get(i), + index(rightLowCount.get(i), rightNeighbor.get(i), lowCount))); + add(unless(hasRightNeighbor.get(i), constant(rightLowCount.get(i), 0))); + + add(when(hasLeftNeighbor.get(i), + index(leftHighCount.get(i), leftNeighbor.get(i), highCount))); + add(unless(hasLeftNeighbor.get(i), constant(leftHighCount.get(i), 0))); + + add(when(hasRightNeighbor.get(i), + index(rightHighCount.get(i), rightNeighbor.get(i), highCount))); + add(unless(hasRightNeighbor.get(i), constant(rightHighCount.get(i), 0))); + + add(when(hasLeftNeighbor.get(i), + index(setSize.get(i), leftNeighbor.get(i), setSize))); + + add(when(hasRightNeighbor.get(i), + index(setSize.get(i), rightNeighbor.get(i), setSize))); + + add(when(hasLeftNeighbor.get(i), + offset(1, leftLowCount.get(i), lowCount.get(i)))); + add(when(hasRightNeighbor.get(i), + offset(1, lowCount.get(i), rightLowCount.get(i)))); + + add(when(hasRightNeighbor.get(i), + offset(1, rightHighCount.get(i), highCount.get(i)))); + add(when(hasLeftNeighbor.get(i), + offset(1, highCount.get(i), leftHighCount.get(i)))); + + add(when(onTable.get(i), + sum(lowCount.get(i), highCount.get(i), setSize.get(i)))); + + add(unless(onTable.get(i), constant(setSize.get(i), 2))); + + // set same rules + add(when(hasLeftNeighbor.get(i), + index(isRun.get(i), leftNeighbor.get(i), isRun))); + add(when(hasRightNeighbor.get(i), + index(isRun.get(i), rightNeighbor.get(i), isRun))); + + add(unless(onTable.get(i), constant(isRun.get(i), false))); + + // rule neighbors + add(when(hasLeftNeighbor.get(i), + index(leftStoneColor.get(i), leftNeighbor.get(i), stoneColor))); + add(unless(hasLeftNeighbor.get(i), + constant(leftStoneColor.get(i), StoneColor.RED))); + add(when(hasRightNeighbor.get(i), + index(rightStoneColor.get(i), rightNeighbor.get(i), stoneColor))); + add(unless(hasRightNeighbor.get(i), + constant(rightStoneColor.get(i), StoneColor.RED))); + + add(when(hasLeftNeighbor.get(i), + index(leftStoneValue.get(i), leftNeighbor.get(i), stoneValue))); + add(unless(hasLeftNeighbor.get(i), constant(leftStoneValue.get(i), 1))); + add(when(hasRightNeighbor.get(i), + index(rightStoneValue.get(i), rightNeighbor.get(i), stoneValue))); + add(unless(hasRightNeighbor.get(i), constant(rightStoneValue.get(i), 1))); + // general rules + + add(when( + hasLeftNeighbor.get(i), + when(isRun.get(i), + lessThanEq(leftStoneValue.get(i), stoneValue.get(i))))); + add(when( + hasRightNeighbor.get(i), + when(isRun.get(i), + lessThanEq(stoneValue.get(i), rightStoneValue.get(i))))); + + add(when( + hasLeftNeighbor.get(i), + when(isRun.get(i), + lessThanEq(leftStoneColor.get(i), stoneColor.get(i))))); + add(when( + hasRightNeighbor.get(i), + when(isRun.get(i), + lessThanEq(stoneColor.get(i), rightStoneColor.get(i))))); + + // run rules + + add(when( + hasLeftNeighbor.get(i), + when(isRun.get(i), + offset(1, leftStoneValue.get(i), stoneValue.get(i))))); + add(when( + hasRightNeighbor.get(i), + when(isRun.get(i), + offset(1, stoneValue.get(i), rightStoneValue.get(i))))); + + add(when( + hasLeftNeighbor.get(i), + when(isRun.get(i), + same(leftStoneColor.get(i), stoneColor.get(i))))); + add(when( + hasRightNeighbor.get(i), + when(isRun.get(i), + same(stoneColor.get(i), rightStoneColor.get(i))))); + + // group rules + add(when( + hasLeftNeighbor.get(i), + unless(isRun.get(i), + same(leftStoneValue.get(i), stoneValue.get(i))))); + add(when( + hasRightNeighbor.get(i), + unless(isRun.get(i), + same(stoneValue.get(i), rightStoneValue.get(i))))); + + add(when( + hasLeftNeighbor.get(i), + unless(isRun.get(i), + lessThan(leftStoneColor.get(i), stoneColor.get(i))))); + add(when( + hasRightNeighbor.get(i), + unless(isRun.get(i), + lessThan(stoneColor.get(i), rightStoneColor.get(i))))); + + // joker defaulting + if (isJoker.get(i)) { + add(unless(onTable.get(i), constant(stoneValue.get(i), 1))); + add(unless(onTable.get(i), + constant(stoneColor.get(i), StoneColor.RED))); + } + } + + public boolean solve() { + Set tableIDs = new HashSet(); + Set leftIDs = new HashSet(); + boolean res = solver.solve(); + if (!res) + return false; + System.out.println("== Hand =="); + for (int i = 0; i < stoneCount; i++) { + if (onTable.get(i).getValue()) { + tableIDs.add(i); + if (!hasLeftNeighbor.get(i).getValue()) { + leftIDs.add(i); + } + } else { + outputStone(i); + } + } + System.out.println(""); + System.out.println("== Table =="); + boolean newLine = false; + boolean first = true; + int nextID = -1; // leftIDs.iterator().next(); + while (!tableIDs.isEmpty()) { + if (tableIDs.contains(nextID)) { + tableIDs.remove(nextID); + leftIDs.remove(nextID); + if (newLine) { + if (!first) { + System.out.println(""); + } + first = false; + newLine = false; + } + outputStone(nextID); + if (!hasRightNeighbor.get(nextID).getValue()) { + newLine = true; + nextID = -1; + } else { + nextID = rightNeighbor.get(nextID).getValue(); + } + } else { + if (leftIDs.isEmpty()) { + nextID = tableIDs.iterator().next(); + } else { + nextID = leftIDs.iterator().next(); + } + newLine = true; + } + } + System.out.println(""); + System.out.println(""); + return res; + } + + private void outputStone(int i) { + System.out.print("[" + + stoneColor.get(i).getValue().toString().substring(0, 1) + + stoneValue.get(i).getValue() + "]"); + // + "," + leftNeighbor.get(i).getValue() + + // hasLeftNeighbor.get(i).getValue() + lowCount.get(i).getValue() + "," + // + rightNeighbor.get(i).getValue() + + // hasRightNeighbor.get(i).getValue() + highCount.get(i).getValue() + + // "]"); + } +} 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