summaryrefslogtreecommitdiffstats
path: root/src/jrummikub/ai
diff options
context:
space:
mode:
Diffstat (limited to 'src/jrummikub/ai')
-rw-r--r--src/jrummikub/ai/TurnLogic.java892
-rw-r--r--src/jrummikub/ai/fdsolver/Constraint.java17
-rw-r--r--src/jrummikub/ai/fdsolver/Constraints.java61
-rw-r--r--src/jrummikub/ai/fdsolver/Propagator.java9
-rw-r--r--src/jrummikub/ai/fdsolver/Satisfiability.java5
-rw-r--r--src/jrummikub/ai/fdsolver/Solver.java268
-rw-r--r--src/jrummikub/ai/fdsolver/SolverMain.java42
-rw-r--r--src/jrummikub/ai/fdsolver/Var.java113
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java74
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java42
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/Filter.java5
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java65
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java31
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/GreaterThan.java18
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java15
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/IfConstraint.java108
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java140
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/LessThan.java17
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/LessThanConst.java18
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java91
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/OffsetConstraint.java90
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/SameConstraint.java69
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/SumConstraint.java51
23 files changed, 567 insertions, 1674 deletions
diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java
index e736361..8318773 100644
--- a/src/jrummikub/ai/TurnLogic.java
+++ b/src/jrummikub/ai/TurnLogic.java
@@ -1,391 +1,633 @@
package jrummikub.ai;
-import static jrummikub.ai.fdsolver.Constraints.constant;
-import static jrummikub.ai.fdsolver.Constraints.index;
-import static jrummikub.ai.fdsolver.Constraints.lessThan;
-import static jrummikub.ai.fdsolver.Constraints.lessThanEq;
-import static jrummikub.ai.fdsolver.Constraints.offset;
-import static jrummikub.ai.fdsolver.Constraints.same;
-import static jrummikub.ai.fdsolver.Constraints.sum;
-import static jrummikub.ai.fdsolver.Constraints.unless;
-import static jrummikub.ai.fdsolver.Constraints.when;
-
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
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.model.GameSettings;
import jrummikub.model.Stone;
import jrummikub.model.StoneColor;
+import jrummikub.util.Pair;
-/**
- * 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 int maxHandPoints;
+ GameSettings settings;
+ int stoneCount;
+ StoneColor maxColor;
+ StoneColor minColor;
+ ArrayList<StoneColor> stoneColors;
+
+ ArrayList<State> stack = new ArrayList<State>();
+ State top;
+
+ int neededPoints = 0;
+ double neededScore = Double.NEGATIVE_INFINITY;
+
+ @SuppressWarnings("serial")
+ private static class Contradiction extends Throwable {
- private Var<Boolean> trueVar;
- private Var<Integer> totalPoints;
+ }
- private List<Var<Boolean>> onTable = new ArrayList<Var<Boolean>>();
+ private class State {
+ ArrayList<StoneState> stones = new ArrayList<StoneState>();
+ HashSet<Integer> changedStones = new HashSet<Integer>();
+ ArrayList<Integer> jokerIDs = new ArrayList<Integer>();
- private List<Var<Integer>> pointsValue = new ArrayList<Var<Integer>>();
+ public State() {
+ }
- private List<Var<Integer>> stoneValue = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> leftStoneValue = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> rightStoneValue = new ArrayList<Var<Integer>>();
+ public State(State state) {
+ for (StoneState stone : state.stones) {
+ stones.add(new StoneState(stone));
+ }
+ jokerIDs = state.jokerIDs;
+ }
- private List<Var<StoneColor>> stoneColor = new ArrayList<Var<StoneColor>>();
- private List<Var<StoneColor>> leftStoneColor = new ArrayList<Var<StoneColor>>();
- private List<Var<StoneColor>> rightStoneColor = new ArrayList<Var<StoneColor>>();
+ public void add(StoneState stone) {
+ stones.add(stone);
+ changedStones.add(stones.size() - 1);
+ if (stone.joker) {
+ jokerIDs.add(stone.id);
+ }
+ }
- private List<Var<Integer>> lowCount = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> leftLowCount = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> rightLowCount = new ArrayList<Var<Integer>>();
+ public void updateStones() throws Contradiction {
+ checkJokers();
+ for (int i : changedStones) {
+ stones.get(i).checkState();
+ }
+ checkScoreAndPoints();
+ while (!changedStones.isEmpty()) {
+ updateStonesStep();
+ checkScoreAndPoints();
+ }
+ }
- private List<Var<Integer>> highCount = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> leftHighCount = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> rightHighCount = new ArrayList<Var<Integer>>();
+ public void updateStonesStep() throws Contradiction {
+ HashSet<Integer> newChangedStones = new HashSet<Integer>();
+ for (int i = 0; i < stoneCount; i++) {
+ StoneState stone = stones.get(i);
+ if (stone.isInterested(changedStones)) {
+ if (stone.update(changedStones)) {
+ newChangedStones.add(i);
+ }
+ }
+ }
+ changedStones = newChangedStones;
+ }
- private List<Var<Integer>> setSize = new ArrayList<Var<Integer>>();
+ public boolean isSolved() {
+ for (StoneState stone : stones) {
+ if (!stone.isSolved())
+ return false;
+ }
+ return true;
+ }
- private List<Var<Boolean>> isRun = new ArrayList<Var<Boolean>>();
+ public void checkJokers() throws Contradiction {
+ for (int i = 0; i < jokerIDs.size(); i++) {
+ StoneState left = stones.get(jokerIDs.get(i));
+
+ HashSet<Integer> leftLeftGroup = new HashSet<Integer>(
+ left.leftGroup);
+ HashSet<Integer> leftLeftRun = new HashSet<Integer>(
+ left.leftRun);
+ leftLeftGroup.remove(null);
+ leftLeftRun.remove(null);
+ int runID, groupID;
+ if (leftLeftGroup.isEmpty()) {
+ groupID = -1;
+ } else {
+ groupID = Collections.min(leftLeftGroup);
+ }
+ if (leftLeftRun.isEmpty()) {
+ runID = -1;
+ } else {
+ runID = Collections.min(leftLeftRun);
+ }
+ for (int j = i + 1; j < jokerIDs.size(); j++) {
+ StoneState right = stones.get(jokerIDs.get(j));
- private List<Var<Integer>> leftNeighbor = new ArrayList<Var<Integer>>();
- private List<Var<Integer>> rightNeighbor = new ArrayList<Var<Integer>>();
+ if (right.leftGroup.remove(groupID)) {
+ changedStones.add(jokerIDs.get(j));
+ }
+ if (right.leftRun.remove(runID)) {
+ changedStones.add(jokerIDs.get(j));
+ }
+ }
+ }
+ }
- private List<Var<Integer>> stoneID = new ArrayList<Var<Integer>>();
+ public void checkScoreAndPoints() throws Contradiction {
+ if (getPoints() < neededPoints) {
+ throw new Contradiction();
+ }
+ if (getScore() <= neededScore) {
+ throw new Contradiction();
+ }
+ }
- private List<Var<Boolean>> hasLeftNeighbor = new ArrayList<Var<Boolean>>();
- private List<Var<Boolean>> hasRightNeighbor = new ArrayList<Var<Boolean>>();
+ public int getPoints() {
+ int sum = 0;
+ for (StoneState stone : stones) {
+ if (stone.onTable != Boolean.FALSE) {
+ sum += stone.getPoints();
+ }
+ }
+ return sum;
+ }
+
+ public double getScore() {
+ double sum = 0;
+ for (StoneState stone : stones) {
+ if (stone.onTable != Boolean.FALSE) {
+ sum += stone.getScore();
+ }
+
+ }
+ return sum;
+ }
+ }
- private List<Boolean> isJoker = new ArrayList<Boolean>();
+ private class StoneState {
+ int id;
+ boolean joker;
+ Integer value;
+ StoneColor color;
+ Boolean onTable;
+ boolean fromTable;
+ HashSet<Integer> leftRun;
+ HashSet<Integer> rightRun;
+ HashSet<Integer> leftGroup;
+ HashSet<Integer> rightGroup;
+
+ public StoneState(int id, Stone stone, boolean table) {
+ this.id = id;
+ joker = stone.isJoker();
+ if (!joker) {
+ this.value = stone.getValue();
+ this.color = stone.getColor();
+ }
+ onTable = table ? true : null;
+ fromTable = table;
+ leftRun = makeFullSet();
+ rightRun = makeFullSet();
+ leftGroup = makeFullSet();
+ rightGroup = makeFullSet();
+ }
- public TurnLogic(GameSettings settings, Collection<Stone> tableStones,
- Collection<Stone> handStones) {
- this.settings = settings;
- stoneCount = tableStones.size() + handStones.size();
- maxSetSize = Math.max(settings.getHighestValue(), settings
- .getStoneColors().size());
+ public StoneState(StoneState stone) {
+ this.id = stone.id;
+ this.joker = stone.joker;
+ this.value = stone.value;
+ this.color = stone.color;
+ this.onTable = stone.onTable;
+ this.fromTable = stone.fromTable;
+ this.leftRun = new HashSet<Integer>(stone.leftRun);
+ this.rightRun = new HashSet<Integer>(stone.rightRun);
+ this.leftGroup = new HashSet<Integer>(stone.leftGroup);
+ this.rightGroup = new HashSet<Integer>(stone.rightGroup);
+ }
+
+ private HashSet<Integer> makeFullSet() {
+ HashSet<Integer> set = new HashSet<Integer>();
+ for (int i = 0; i < stoneCount; i++) {
+ if (i != id) {
+ set.add(i);
+ }
+ }
+ set.add(null);
+ return set;
+ }
- trueVar = solver.makeVar(true);
+ public boolean isInterested(HashSet<Integer> changes) {
+ return !(Collections.disjoint(changes, leftRun)
+ && Collections.disjoint(changes, rightRun)
+ && Collections.disjoint(changes, leftGroup) && Collections
+ .disjoint(changes, rightGroup));
+ }
- maxHandPoints = 0;
- int i = 0;
- for (Stone stone : tableStones) {
- addStone(i, true, stone);
- i++;
+ private boolean isNullSet(HashSet<Integer> i) {
+ return i.size() == 1 && i.contains(null);
}
- for (Stone stone : handStones) {
- addStone(i, false, stone);
- i++;
+
+ private boolean isSingleNonNullSet(HashSet<Integer> i) {
+ return i.size() == 1 && !i.contains(null);
}
- for (i = 0; i < stoneCount; i++) {
- addConstraints(i);
+ public <T extends Comparable<T>> boolean lessThan(T a, T b) {
+ return a == null || b == null || a.compareTo(b) < 0;
}
- totalPoints = solver.makeRangeVar(settings.getInitialMeldThreshold(),
- maxHandPoints);
+ public <T> boolean same(T a, T b) {
+ return a == null || b == null || a.equals(b);
+ }
- List<Var<Integer>> points = new ArrayList<Var<Integer>>();
+ public boolean step(Integer a, Integer b) {
+ return a == null || b == null || (int) a == b - 1;
+ }
- for (Var<Integer> var : pointsValue) {
- if (var != null) {
- points.add(var);
- }
+ public boolean cycleStep(Integer a, Integer b) {
+ return a == null || b == null || (int) a == b - 1
+ || a == settings.getHighestValue() && b == 1;
}
- add(sum(totalPoints, points));
- }
+ public boolean groupNeighbor(StoneState other) {
+ if (isNullSet(leftGroup) && isNullSet(other.rightGroup)) {
+ return false;
+ }
+ if (other.color == minColor || color == maxColor) {
+ return false;
+ }
+ return lessThan(color, other.color) && same(value, other.value);
+ }
- 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()));
- if (table) {
- pointsValue.add(null);
- } else {
- pointsValue.add(solver.makeRangeVar(0,
- settings.getHighestValue()));
- maxHandPoints += settings.getHighestValue();
- }
- stoneColor.add(solver.makeVar(settings.getStoneColors()));
- } else {
- stoneValue.add(solver.makeVar(stone.getValue()));
- if (table) {
- pointsValue.add(null);
+ public boolean runNeighbor(StoneState other) {
+ if (isNullSet(leftRun) && isNullSet(other.rightRun)) {
+ return false;
+ }
+ if (!same(color, other.color)) {
+ return false;
+ }
+ if (settings.isNoLimits()) {
+ return cycleStep(value, other.value);
} else {
- pointsValue.add(solver.makeVar(0, stone.getValue()));
- maxHandPoints += stone.getValue();
+ if (((Integer) 1).equals(other.value)
+ || ((Integer) settings.getHighestValue()).equals(value)) {
+ return false;
+ }
+ return step(value, other.value);
}
- 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()));
+ public boolean update(HashSet<Integer> changes) throws Contradiction {
+ boolean changed = false;
+ changed |= updateRuns(changes);
+ changed |= updateGroups(changes);
+ changed |= checkState();
+ return changed;
+ }
- lowCount.add(solver.makeRangeVar(0, maxSetSize - 1));
- leftLowCount.add(solver.makeRangeVar(0, maxSetSize - 1));
- rightLowCount.add(solver.makeRangeVar(0, maxSetSize - 1));
+ public boolean updateRuns(HashSet<Integer> changes)
+ throws Contradiction {
+ boolean changed = false;
+ HashSet<Integer> relevantChanges = new HashSet<Integer>(leftRun);
+ relevantChanges.retainAll(changes);
+ for (int i : relevantChanges) {
+ StoneState other = top.stones.get(i);
+ if (!other.runNeighbor(this) || !other.rightRun.contains(id)) {
+ leftRun.remove(i);
+ changed = true;
+ } else if (other.rightRun.size() == 1
+ && other.onTable == Boolean.TRUE) {
+ changed |= leftRun.retainAll(Arrays.asList(i));
+ changed |= onTable != Boolean.TRUE;
+ onTable = true;
+ break;
+ }
+ }
+ relevantChanges = new HashSet<Integer>(rightRun);
+ relevantChanges.retainAll(changes);
+ for (int i : relevantChanges) {
+ StoneState other = top.stones.get(i);
+ if (!this.runNeighbor(other) || !other.leftRun.contains(id)) {
+ rightRun.remove(i);
+ changed = true;
+ } else if (other.leftRun.size() == 1
+ && other.onTable == Boolean.TRUE) {
+ changed |= rightRun.retainAll(Arrays.asList(i));
+ changed |= onTable != Boolean.TRUE;
+ onTable = true;
+ break;
+ }
+ }
+ return changed;
+ }
- highCount.add(solver.makeRangeVar(0, maxSetSize - 1));
- leftHighCount.add(solver.makeRangeVar(0, maxSetSize - 1));
- rightHighCount.add(solver.makeRangeVar(0, maxSetSize - 1));
+ public boolean updateGroups(HashSet<Integer> changes)
+ throws Contradiction {
+ boolean changed = false;
+ HashSet<Integer> relevantChanges = new HashSet<Integer>(leftGroup);
+ relevantChanges.retainAll(changes);
+ for (int i : relevantChanges) {
+ StoneState other = top.stones.get(i);
+ if (!other.groupNeighbor(this)
+ || !other.rightGroup.contains(id)) {
+ leftGroup.remove(i);
+ changed = true;
+ } else if (other.rightGroup.size() == 1
+ && other.onTable == Boolean.TRUE) {
+ changed |= leftGroup.retainAll(Arrays.asList(i));
+ changed |= onTable != Boolean.TRUE;
+ onTable = true;
+ break;
+ }
+ }
+ relevantChanges = new HashSet<Integer>(rightGroup);
+ relevantChanges.retainAll(changes);
+ for (int i : relevantChanges) {
+ StoneState other = top.stones.get(i);
+ if (!this.groupNeighbor(other) || !other.leftGroup.contains(id)) {
+ rightGroup.remove(i);
+ changed = true;
+ } else if (other.leftGroup.size() == 1
+ && other.onTable == Boolean.TRUE) {
+ changed |= rightGroup.retainAll(Arrays.asList(i));
+ changed |= onTable != Boolean.TRUE;
+ onTable = true;
+ break;
+ }
+ }
+ return changed;
+ }
- setSize.add(solver.makeRangeVar(2, maxSetSize - 1));
+ public boolean checkState() throws Contradiction {
+ boolean changed = false;
+ if (onTable == Boolean.FALSE) {
+ if (leftRun.size() + rightRun.size() + leftGroup.size()
+ + rightGroup.size() != 0) {
+ leftRun.clear();
+ rightRun.clear();
+ leftGroup.clear();
+ rightGroup.clear();
+ return true;
+ }
+ return false;
+ }
- isRun.add(solver.makeBoolVar());
+ if (!(leftGroup.contains(null) || rightGroup.contains(null))) {
+ changed |= leftRun.retainAll(Arrays.asList((Integer) null))
+ | rightRun.retainAll(Arrays.asList((Integer) null));
+ }
+ if (!(leftRun.contains(null) || rightRun.contains(null))) {
+ changed |= leftGroup.retainAll(Arrays.asList((Integer) null))
+ | rightGroup.retainAll(Arrays.asList((Integer) null));
+ }
- leftNeighbor.add(solver.makeRangeVar(0, stoneCount - 1));
- rightNeighbor.add(solver.makeRangeVar(0, stoneCount - 1));
+ @SuppressWarnings("unchecked")
+ List<HashSet<Integer>> sets = Arrays.<HashSet<Integer>> asList(
+ leftGroup, rightGroup, leftRun, rightRun, leftGroup,
+ rightGroup, leftRun);
+ for (int i = 0; i < 4; i++) {
+ if (isNullSet(sets.get(i)) && isNullSet(sets.get(i + 1))
+ && isNullSet(sets.get(i + 2))) {
+ changed |= sets.get(i + 3).remove(null);
+ }
+ }
- stoneID.add(solver.makeVar(i));
+ if (leftGroup.isEmpty() || rightGroup.isEmpty()
+ || leftRun.isEmpty() || rightRun.isEmpty()) {
+ if (onTable == Boolean.TRUE) {
+ throw new Contradiction();
+ }
+ if (onTable == null) {
+ onTable = false;
+ changed = true;
+ }
+ }
+
+ if (isSingleNonNullSet(leftRun)
+ && isNullSet(top.stones.get(leftRun.iterator().next()).leftRun)) {
+ changed |= rightRun.remove(null);
+ }
+ if (isSingleNonNullSet(rightRun)
+ && isNullSet(top.stones.get(rightRun.iterator().next()).rightRun)) {
+ changed |= leftRun.remove(null);
+ }
+
+ if (isSingleNonNullSet(leftGroup)
+ && isNullSet(top.stones.get(leftGroup.iterator().next()).leftGroup)) {
+ changed |= rightGroup.remove(null);
+ }
+ if (isSingleNonNullSet(rightGroup)
+ && isNullSet(top.stones.get(rightGroup.iterator().next()).rightGroup)) {
+ changed |= leftGroup.remove(null);
+ }
+
+ changed |= checkJoker();
+
+ return changed;
+ }
+
+ private boolean checkJoker() {
+ return false;
+ }
+
+ public boolean isSolved() {
+ if (onTable == Boolean.FALSE) {
+ return true;
+ }
+ if (onTable == null || color == null || value == null) {
+ return false;
+ }
+ if (leftRun.size() > 1 || rightRun.size() > 1
+ || leftGroup.size() > 1 || rightGroup.size() > 1) {
+ return false;
+ }
+ return true;
+ }
+
+ public double getScore() {
+ if (fromTable) {
+ return 0;
+ }
+ return 1;
+ }
+
+ public double getPoints() {
+ if (fromTable) {
+ return 0;
+ }
+ if (value == null)
+ return (double) settings.getHighestValue();
+ else
+ return (double) value;
+ }
+ }
+
+ public TurnLogic(GameSettings settings, Collection<Stone> tableStones,
+ Collection<Stone> handStones) {
+ this.settings = settings;
+
+ stoneCount = tableStones.size() + handStones.size();
+
+ maxColor = Collections.max(settings.getStoneColors());
+ minColor = Collections.min(settings.getStoneColors());
+
+ stoneColors = new ArrayList<StoneColor>(settings.getStoneColors());
+ Collections.sort(stoneColors);
+
+ top = new State();
+ stack.add(top);
+
+ ArrayList<Pair<Stone, Boolean>> sortedStones = new ArrayList<Pair<Stone, Boolean>>();
+
+ for (Stone stone : tableStones) {
+ sortedStones.add(new Pair<Stone, Boolean>(stone, true));
+ }
+ for (Stone stone : handStones) {
+ sortedStones.add(new Pair<Stone, Boolean>(stone, false));
+ }
+ Collections.sort(sortedStones, new Comparator<Pair<Stone, Boolean>>() {
+ @Override
+ public int compare(Pair<Stone, Boolean> o1, Pair<Stone, Boolean> o2) {
+ int cmp;
+ cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2
+ .getFirst().isJoker());
+ if (cmp != 0) {
+ return -cmp;
+ }
+ cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst()
+ .getColor());
+ if (cmp != 0) {
+ return cmp;
+ }
+ cmp = ((Integer) o1.getFirst().getValue()).compareTo(o2
+ .getFirst().getValue());
+ return cmp;
+ }
+ });
+
+ int i = 0;
+ for (Pair<Stone, Boolean> pair : sortedStones) {
+ top.add(new StoneState(i++, pair.getFirst(), pair.getSecond()));
+ }
+ }
+
+ public void needIntialMeldThreshold() {
+ neededPoints = settings.getInitialMeldThreshold();
+ }
- hasLeftNeighbor.add(solver.makeBoolVar());
- hasRightNeighbor.add(solver.makeBoolVar());
+ private void pop() {
+ stack.remove(stack.size() - 1);
+ if (!stack.isEmpty()) {
+ top = stack.get(stack.size() - 1);
+ }
}
- private void add(Constraint c) {
- solver.addConstraint(c);
+ private void replace() {
+ stack.remove(stack.size() - 1);
}
- 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)));
- }
-
- // initial meld points
- if (pointsValue.get(i) != null) {
- add(when(onTable.get(i),
- same(stoneValue.get(i), pointsValue.get(i))));
- add(unless(onTable.get(i), constant(pointsValue.get(i), 0)));
+ private void pushes(State... states) {
+ for (State state : states) {
+ stack.add(state);
}
}
+ private void done() {
+ top = stack.get(stack.size() - 1);
+ }
+
public boolean solve() {
- Set<Integer> tableIDs = new HashSet<Integer>();
- Set<Integer> leftIDs = new HashSet<Integer>();
- boolean res = solver.solve();
- if (!res)
- return false;
- System.out.println("== Hand ==");
+ if (top.isSolved()) {
+ pop();
+ }
+ while (stack.size() != 0) {
+ try {
+ top.updateStones();
+ if (top.isSolved()) {
+ return true;
+ }
+ branch();
+ done();
+ } catch (Contradiction c) {
+ pop();
+ }
+ }
+ return false;
+ }
+
+ public double optimize() {
+ while (solve()) {
+ neededScore = top.getScore();
+ }
+ return neededScore;
+ }
+
+ private void branch() throws Contradiction {
for (int i = 0; i < stoneCount; i++) {
- if (onTable.get(i).getValue()) {
- tableIDs.add(i);
- if (!hasLeftNeighbor.get(i).getValue()) {
- leftIDs.add(i);
+ StoneState stone = top.stones.get(i);
+ if (stone.onTable == null) {
+ replace();
+ State newState = new State(top);
+ newState.stones.get(i).onTable = false;
+ newState.changedStones.add(i);
+ State altState = new State(top);
+ altState.stones.get(i).onTable = true;
+ altState.changedStones.add(i);
+ pushes(altState, newState);
+ return;
+ }
+ if (stone.leftRun.size() > 1) {
+ replace();
+ for (Integer id : stone.leftRun) {
+ State newState = new State(top);
+ newState.stones.get(i).leftRun.clear();
+ newState.stones.get(i).leftRun.add(id);
+ newState.changedStones.add(i);
+ pushes(newState);
}
- } 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;
+ return;
+ }
+ if (stone.rightRun.size() > 1) {
+ replace();
+ for (Integer id : stone.rightRun) {
+ State newState = new State(top);
+ newState.stones.get(i).rightRun.clear();
+ newState.stones.get(i).rightRun.add(id);
+ newState.changedStones.add(i);
+ pushes(newState);
}
- outputStone(nextID);
- if (!hasRightNeighbor.get(nextID).getValue()) {
- newLine = true;
- nextID = -1;
- } else {
- nextID = rightNeighbor.get(nextID).getValue();
+ return;
+ }
+ if (stone.leftGroup.size() > 1) {
+ replace();
+ for (Integer id : stone.leftGroup) {
+ State newState = new State(top);
+ newState.stones.get(i).leftGroup.clear();
+ newState.stones.get(i).leftGroup.add(id);
+ newState.changedStones.add(i);
+ pushes(newState);
}
- } else {
- if (leftIDs.isEmpty()) {
- nextID = tableIDs.iterator().next();
- } else {
- nextID = leftIDs.iterator().next();
+ return;
+ }
+ if (stone.rightGroup.size() > 1) {
+ replace();
+ for (Integer id : stone.rightGroup) {
+ State newState = new State(top);
+ newState.stones.get(i).rightGroup.clear();
+ newState.stones.get(i).rightGroup.add(id);
+ newState.changedStones.add(i);
+ pushes(newState);
+ }
+ return;
+ }
+ if (stone.color == null) {
+ replace();
+ for (StoneColor color : stoneColors) {
+ State newState = new State(top);
+ newState.stones.get(i).color = color;
+ newState.changedStones.add(i);
+ pushes(newState);
}
- newLine = true;
+ return;
+ }
+ if (stone.value == null) {
+ replace();
+ for (int value = 1; value <= settings.getHighestValue(); value++) {
+ State newState = new State(top);
+ newState.stones.get(i).value = value;
+ newState.changedStones.add(i);
+ pushes(newState);
+ }
+ return;
}
}
- 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() +
- * "]");
- */
+ // This should never happen
+ throw new Error("Internal AI error");
}
}
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<Propagator> cachedPropagators;
-
- public abstract Collection<Var<?>> getWatchedVars();
-
- public abstract Collection<Propagator> 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<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 Constraint sum(Var<Integer> sum, List<Var<Integer>> list) {
- return new ListSumConstraint(sum, list);
- }
-
- 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/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<Var<?>> 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<Var<?>> vars = new HashSet<Var<?>>();
-
- Set<Var<?>> dirtyVars = new HashSet<Var<?>>();
-
- Set<Var<?>> unsolvedVars = new HashSet<Var<?>>();
-
- Set<Constraint> constraints = new HashSet<Constraint>();
-
- Set<Constraint> dirtyConstraints = new HashSet<Constraint>();
-
- ArrayList<StackFrame> stack = new ArrayList<StackFrame>();
-
- boolean contradiction = false;
-
- static private class StackFrame {
- Map<Var<?>, HashSet<?>> invalidatedValues = new HashMap<Var<?>, HashSet<?>>();
- Var<?> branchVar;
- Object branchValue;
- HashSet<Constraint> finishedConstraints = new HashSet<Constraint>();
-
- public <T> void invalidate(Var<T> var, T invalid) {
- HashSet<T> values = (HashSet<T>) invalidatedValues.get(var);
- if (values == null) {
- invalidatedValues.put(var,
- new HashSet<T>(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<Var<?>> oldDirtyVars = new ArrayList<Var<?>>(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<Object>) var, value);
- }
-
- <T> void branchWith(Var<T> 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);
- }
-
- <T> void logInvalidation(Var<T> 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<Var<?>, HashSet<?>> entry : item.invalidatedValues
- .entrySet()) {
- Var<Object> var = (Var<Object>) entry.getKey();
- HashSet<Object> values = (HashSet<Object>) 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<Object>) topFrame.branchVar).invalidate(topFrame.branchValue);
- }
-
- // factory methods for vars
-
- public Var<Integer> makeRangeVar(int low, int high) {
- ArrayList<Integer> range = new ArrayList<Integer>();
- for (int i = low; i <= high; i++) {
- range.add(i);
- }
- return makeVar(range);
- }
-
- public Var<Boolean> makeBoolVar() {
- return makeVar(true, false);
- }
-
- public <T> Var<T> makeVar(Collection<T> range) {
- Var<T> var = new Var<T>(this, range);
- addVar(var);
- return var;
- }
-
- 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/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<Boolean> onTable =
- * tisch ? {true}, {true, false} Var<Integer> value = {N} Var<StoneColor>
- * color = {C} Var<Integer> nachbarL,R = {-1, 0...steinanzahl} Var<Boolean>
- * 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<Integer> pos von {links, rechts} + constraints
- *
- * links + rechts >= 3
- *
- * foreach handstein: Var<Integer> badness = onTable ? ### (z. B. 1) : 0
- *
- * totalBadness = sum(all badness)
- *
- * foreach joker: Var<Integer> value = {-1, 1..13} Var<StoneColor> 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<T> implements Comparable<Var<T>> {
- private Solver solver;
- private HashSet<T> range;
- private HashSet<Constraint> constraints;
- private T recorded;
-
- public Var(Solver solver, Collection<T> range) {
- this.solver = solver;
- this.range = new HashSet<T>(range);
- constraints = new HashSet<Constraint>();
- }
-
- public T getValue() {
- if (range.size() != 1)
- return null;
- return range.iterator().next();
- }
-
- public HashSet<T> getRange() {
- return range;
- }
-
- void choose(T value) {
- for (Iterator<T> 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<Constraint> getConstraints() {
- return constraints;
- }
-
- public Iterator<T> iterator() {
- final Iterator<T> iterator = range.iterator();
- return new Iterator<T>() {
- 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<T> 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<T> extends Constraint {
- Var<T> x, y;
- Comparator<T> comparator, reverseComparator;
- ComparatorPropagator<T> trueX, trueY, falseX, falseY;
- boolean allowEqual;
-
- ComparatorConstraint(final Comparator<T> comparator, boolean allowEqual,
- Var<T> x, Var<T> y) {
- this.x = x;
- this.y = y;
- this.comparator = comparator;
- this.allowEqual = allowEqual;
- reverseComparator = new Comparator<T>() {
- @Override
- public int compare(T o1, T o2) {
- return comparator.compare(o2, o1);
- }
- };
- trueX = new ComparatorPropagator<T>(comparator, allowEqual, x, y);
- trueY = new ComparatorPropagator<T>(reverseComparator, allowEqual, y, x);
- falseX = new ComparatorPropagator<T>(reverseComparator, !allowEqual, x,
- y);
- falseY = new ComparatorPropagator<T>(comparator, !allowEqual, y, x);
- }
-
- @Override
- public Collection<Var<?>> getWatchedVars() {
- return Arrays.<Var<?>> asList(x, y);
- }
-
- @Override
- public Collection<Propagator> getPropagators(boolean negate) {
- if (negate) {
- return Arrays.<Propagator> asList(falseX, falseY);
- } else {
- return Arrays.<Propagator> asList(trueX, trueY);
- }
- }
-
- @Override
- public Satisfiability getSatisfiability() {
- 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<T> implements Propagator {
- private Var<T> x, y;
- private Comparator<T> comparator;
- private boolean allowEqual;
- public ComparatorPropagator(Comparator<T> comparator, boolean allowEqual, Var<T> x, Var<T> y) {
- this.comparator = comparator;
- this.allowEqual = allowEqual;
- this.x = x;
- this.y = y;
- }
-
- @Override
- public Collection<Var<?>> getWatchedVars() {
- return Arrays.<Var<?>>asList(y);
- }
-
- @Override
- public void propagate() {
- T maxY = Collections.max(y.getRange(), comparator);
-
- for(Iterator<T> i = x.iterator(); i.hasNext();) {
- T value = i.next();
- int comparision = comparator.compare(value, maxY);
- if (comparision > 0 || comparision == 0 && !allowEqual) {
- i.remove();
- }
- }
- }
-}
diff --git a/src/jrummikub/ai/fdsolver/constraint/Filter.java b/src/jrummikub/ai/fdsolver/constraint/Filter.java
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<T> {
- 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<T> extends Constraint {
- private Var<T> var;
- private Propagator trueProp, falseProp;
- private Filter<T> filter;
-
- public FilterConstraint(final Filter<T> filter, Var<T> var) {
- this.var = var;
- this.filter = filter;
- trueProp = new FilterPropagator<T>(filter, var);
- falseProp = new FilterPropagator<T>(new Filter<T>() {
- @Override
- public boolean accept(T value) {
- return !filter.accept(value);
- }
- }, var);
- }
-
- @Override
- public Collection<Var<?>> getWatchedVars() {
- return Arrays.<Var<?>> asList(var);
- }
-
- @Override
- public Collection<Propagator> getPropagators(boolean negate) {
- return Arrays.asList(negate ? falseProp : trueProp);
- }
-
- @Override
- public Satisfiability getSatisfiability() {
- boolean any = false;
- boolean all = true;
-
- for (T value : var.getRange()) {
- boolean accepted = filter.accept(value);
- if (accepted) {
- any = true;
- } else {
- all = false;
- }
- }
-
- if (all && any) {
- return TAUT;
- } else if (any) {
- return SAT;
- } else {
- return UNSAT;
- }
- }
-
-}
diff --git a/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java b/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java
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<T> implements Propagator {
- private Filter<T> filter;
- private Var<T> var;
-
- public FilterPropagator(Filter<T> filter, Var<T> var) {
- this.filter = filter;
- this.var = var;
- }
-
- @Override
- public Collection<Var<?>> getWatchedVars() {
- return Arrays.<Var<?>>asList(var);
- }
-
- @Override
- public void propagate() {
- for(Iterator<T> i = var.iterator(); i.hasNext();) {
- if(!filter.accept(i.next()))
- i.remove();
- }
- }
-}
diff --git a/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java b/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java
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<T extends Comparable<T>> extends
- ComparatorConstraint<T> {
-
- public GreaterThan(boolean allowEqual, Var<T> x, Var<T> y) {
- super(new Comparator<T>() {
- @Override
- public int compare(T o1, T o2) {
- return o2.compareTo(o1);
- }
- }, allowEqual, x, y);
- }
-}
diff --git a/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java b/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java
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<T extends Comparable<T>> extends
- FilterConstraint<T> {
- public GreaterThanConst(final boolean allowEqual, Var<T> x, final T y) {
- super(new Filter<T>() {
- @Override
- public boolean accept(T value) {
- return y.compareTo(value) < (allowEqual ? 1 : 0);
- }
- }, x);
- }
-}
diff --git a/src/jrummikub/ai/fdsolver/constraint/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<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.isSatisfiable()) {
- 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
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<T> extends 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> invUnion = new HashSet<T>(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<Var<?>> getWatchedVars() {
- return varsNoIndex;
- }
-
- @Override
- public void propagate() {
- for (Iterator<Integer> i = index.iterator(); i.hasNext();) {
- int id = i.next();
- Var<T> item = list.get(id);
- if (Collections.disjoint(item.getRange(), target.getRange())) {
- 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 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<T> 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<T extends Comparable<T>> extends ComparatorConstraint<T> {
-
- public LessThan(boolean allowEqual, Var<T> x, Var<T> y) {
- super(new Comparator<T>() {
- @Override
- public int compare(T o1, T o2) {
- return o1.compareTo(o2);
- }
- }, allowEqual, x, y);
- }
-}
diff --git a/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java b/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java
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<T extends Comparable<T>> extends FilterConstraint<T> {
- public LessThanConst(final boolean allowEqual, Var<T> x, final T y) {
- super(new Filter<T>() {
- @Override
- public boolean accept(T value) {
- return value.compareTo(y) < (allowEqual ? 1 : 0);
- }
- }, x);
- }
-}
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<Integer> sum;
- List<Var<Integer>> list;
- List<Var<?>> vars = new ArrayList<Var<?>>();
-
- public ListSumConstraint(Var<Integer> sum, List<Var<Integer>> list) {
- this.sum = sum;
- this.list = list;
- vars.add(sum);
- vars.addAll(list);
- }
-
- @Override
- public Collection<Var<?>> getWatchedVars() {
- return vars;
- }
-
- @Override
- public Collection<Propagator> getPropagators(boolean negate) {
- return Collections.emptyList();
- }
-
- @Override
- public Satisfiability getSatisfiability() {
- List<Integer> values = new ArrayList<Integer>();
- int valueSum = 0;
- boolean isTaut = sum.getRange().size()==1;
- for (Var<Integer> var : list) {
- Iterator<Integer> 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<Integer> reachableValues = new HashSet<Integer>();
- Set<Integer> newValues = new HashSet<Integer>();
- reachableValues.add(valueSum);
-
- if (sum.getRange().contains(valueSum)) {
- return Satisfiability.SAT;
- }
-
- for (int i = 0; i < values.size(); i++) {
- Var<Integer> 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<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() {
- 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<T> extends 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() {
- 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<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;
- }
-}