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.java61
1 files changed, 39 insertions, 22 deletions
diff --git a/src/jrummikub/ai/fdsolver/Solver.java b/src/jrummikub/ai/fdsolver/Solver.java
index 2277ba4..0bdb344 100644
--- a/src/jrummikub/ai/fdsolver/Solver.java
+++ b/src/jrummikub/ai/fdsolver/Solver.java
@@ -7,6 +7,7 @@ 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.*;
@@ -24,6 +25,8 @@ public class Solver {
Set<Constraint> constraints = new HashSet<Constraint>();
+ Set<Constraint> dirtyConstraints = new HashSet<Constraint>();
+
ArrayList<StackFrame> stack = new ArrayList<StackFrame>();
boolean contradiction = false;
@@ -83,27 +86,19 @@ public class Solver {
}
}
- public void propagateOnce() {
- Var<?> dirtyVar = Collections.min(dirtyVars);
- dirtyVars.remove(dirtyVar);
- outerLoop: for (Iterator<Constraint> i = dirtyVar.getConstraints()
- .iterator(); i.hasNext();) {
- Constraint constraint = i.next();
- Satisfiability sat = constraint.getSatisfiability();
- if (sat == UNSAT) {
- contradiction = true;
- break;
- }
- if (sat == TAUT) {
- i.remove();
- finishedConstraint(constraint, dirtyVar);
- continue;
- }
- for (Propagator propagator : constraint.cachedPropagators) {
- if (propagator.getWatchedVars().contains(dirtyVar)) {
- propagator.propagate();
- if (contradiction) {
- break outerLoop;
+ 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;
+ }
}
}
}
@@ -111,9 +106,31 @@ public class Solver {
}
public void propagateAll() {
+ int i = 0;
while (!(dirtyVars.isEmpty() || contradiction)) {
- propagateOnce();
+ 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) {