CSP.java

// CSP.java
// From Classic Computer Science Problems in Java Chapter 3
// Copyright 2020 David Kopec
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package chapter3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CSP<V, D> {
	private List<V> variables;
	private Map<V, List<D>> domains;
	private Map<V, List<Constraint<V, D>>> constraints = new HashMap<>();

	public CSP(List<V> variables, Map<V, List<D>> domains) {
		this.variables = variables;
		this.domains = domains;
		for (V variable : variables) {
			constraints.put(variable, new ArrayList<>());
			if (!domains.containsKey(variable)) {
				throw new IllegalArgumentException("Every variable should have a domain assigned to it.");
			}
		}
	}

	public void addConstraint(Constraint<V, D> constraint) {
		for (V variable : constraint.variables) {
			if (!variables.contains(variable)) {
				throw new IllegalArgumentException("Variable in constraint not in CSP");
			}
			constraints.get(variable).add(constraint);
		}
	}

	// Check if the value assignment is consistent by checking all constraints
	// for the given variable against it
	public boolean consistent(V variable, Map<V, D> assignment) {
		for (Constraint<V, D> constraint : constraints.get(variable)) {
			if (!constraint.satisfied(assignment)) {
				return false;
			}
		}
		return true;
	}

	public Map<V, D> backtrackingSearch(Map<V, D> assignment) {
		// assignment is complete if every variable is assigned (our base case)
		if (assignment.size() == variables.size()) {
			return assignment;
		}
		// get the first variable in the CSP but not in the assignment
		V unassigned = variables.stream().filter(v -> !assignment.containsKey(v)).findFirst().get();
		// get the every possible domain value of the first unassigned variable
		for (D value : domains.get(unassigned)) {
			// shallow copy of assignment that we can change
			Map<V, D> localAssignment = new HashMap<>(assignment);
			localAssignment.put(unassigned, value);
			// if we're still consistent, we recurse (continue)
			if (consistent(unassigned, localAssignment)) {
				Map<V, D> result = backtrackingSearch(localAssignment);
				// if we didn't find the result, we will end up backtracking
				if (result != null) {
					return result;
				}
			}
		}
		return null;
	}

	// helper for backtrackingSearch when nothing known yet
	public Map<V, D> backtrackingSearch() {
		return backtrackingSearch(new HashMap<>());
	}
}