From e06ba8ea1346e5045a34508648ac93150aacb01a Mon Sep 17 00:00:00 2001
From: Jannis Harder <harder@informatik.uni-luebeck.de>
Date: Fri, 17 Jun 2011 17:41:52 +0200
Subject: Reimplemented AI (old one was too slow)

git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@443 72836036-5685-4462-b002-a69064685172
---
 src/jrummikub/ai/fdsolver/Solver.java | 268 ----------------------------------
 1 file changed, 268 deletions(-)
 delete mode 100644 src/jrummikub/ai/fdsolver/Solver.java

(limited to 'src/jrummikub/ai/fdsolver/Solver.java')

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();
-		}
-	}
-
-}
-- 
cgit v1.2.3