diff options
Diffstat (limited to 'src/jrummikub/ai')
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; - } -} |