summaryrefslogtreecommitdiffstats
path: root/src/jrummikub/ai/fdsolver/Solver.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/jrummikub/ai/fdsolver/Solver.java')
-rw-r--r--src/jrummikub/ai/fdsolver/Solver.java268
1 files changed, 0 insertions, 268 deletions
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();
- }
- }
-
-}