Problem.java
/* Copyright 2015 Laurent COCAULT
* Licensed to Laurent COCAULT under one or more contributor license agreements.
* See the NOTICE file distributed with this work for additional information
* regarding copyright ownership. Laurent COCAULT licenses this file to You
* 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 org.csp.constraint.solver;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import org.csp.constraint.model.BinaryConstraint;
import org.csp.constraint.model.Constraint;
import org.csp.constraint.model.NAryConstraint;
import org.csp.constraint.model.TernaryConstraint;
import org.csp.constraint.model.UnaryConstraint;
import org.csp.constraint.model.UnsizedConstraint;
import org.csp.constraint.model.Variable;
/**
* Represents a constraint solving problem.
*/
public class Problem<T> {
/**
* True when the problem is being solved.
*/
private boolean searching_;
/**
* Number of fails since the beginning of the search session.
*/
private int failsCounter_;
/**
* Number of choice points since the beginning of the search session.
*/
private int choicePointsCounter_;
/**
* During the search, variable states are saved and restored in a stack.
* This attribute counts the number of states currently stored in this
* stack.
*/
private int stackDepth_;
/**
* Table of variables declared in the problem. A variable is considered
* declared once it has been successfully added to problem and until it is
* removed.
*/
private List<Variable<T>> variables_;
/**
* Table of unary constraints declared in the problem. An unary constraint
* is considered declared once it has been successfully added to problem and
* until it is removed.
*/
private List<UnaryConstraint<T>> unaryConstraints_;
/**
* Table of N-ary constraints declared in the problem. An N-ary constraint
* is considered declared once it has been successfully added to problem and
* until it is removed.
*/
private List<NAryConstraint<T>> nAryConstraints_;
/**
* Constructor.
*/
public Problem() {
// Counters and flags
searching_ = false;
failsCounter_ = 0;
choicePointsCounter_ = 0;
stackDepth_ = 1;
// Collection of variables and constraints
variables_ = new ArrayList<Variable<T>>();
unaryConstraints_ = new ArrayList<UnaryConstraint<T>>();
nAryConstraints_ = new ArrayList<NAryConstraint<T>>();
}
// -----------------------------------------------------------------------//
// Search services //
// -----------------------------------------------------------------------//
/**
* Add a binary constraint to the problem. A binary constraint can not be
* added while the problem is being solved or if one of the referenced
* variables has not been previously added to the problem. A constraint can
* not be added twice.
* @param constraint
* Constraint to add to the problem
* @return True if the constraint has been added
*/
private boolean add(final BinaryConstraint<T> constraint) {
// Can the constraint be added ?
final boolean canAdd = !searching_ &&
isVariableDeclared(constraint.getFirstVariable()) &&
isVariableDeclared(constraint.getSecondVariable()) &&
!isNAryConstraintDeclared(constraint);
if (canAdd) {
// The problem is not being solved, the two referenced variables are
// declared : the constraint is added.
nAryConstraints_.add(constraint);
}
return canAdd;
}
/**
* Add a constraint to the problem. A constraint can not be added while the
* problem is being solved or if one of the referenced variables has not
* been previously added to the problem. A constraint can not be added
* twice.
* @param constraint
* Constraint to add to the problem
* @return True if the constraint has been added
*/
public boolean add(final Constraint<T> constraint) {
// Can the constraint be added
boolean canAdd = false;
if (constraint.isUnary()) {
// Unary constraint
canAdd = add((UnaryConstraint<T>) constraint);
} else if (constraint.isBinary()) {
// Binary constraint
canAdd = add((BinaryConstraint<T>) constraint);
} else if (constraint.isTernary()) {
// Ternary constraint
canAdd = add((TernaryConstraint<T>) constraint);
} else if (constraint.isUnsized()) {
// Unsized N-ary constraint
canAdd = add((UnsizedConstraint<T>) constraint);
}
if (canAdd) {
constraint.enablePropagate(true);
}
return canAdd;
}
/**
* Add a ternary constraint to the problem. A ternary constraint can not be
* added while the problem is being solved or if one of the referenced
* variables has not been previously added to the problem. A constraint can
* not be added twice.
* @param constraint
* Constraint to add to the problem
* @return True if the constraint has been added
*/
private boolean add(final TernaryConstraint<T> constraint) {
// Can the constraint be added ?
final boolean canAdd = !searching_ &&
isVariableDeclared(constraint.getFirstVariable()) &&
isVariableDeclared(constraint.getSecondVariable()) &&
isVariableDeclared(constraint.getThirdVariable()) &&
!isNAryConstraintDeclared(constraint);
if (canAdd) {
// The problem is not being solved, the three referenced variables
// are declared : the constraint is added.
nAryConstraints_.add(constraint);
}
return canAdd;
}
/**
* Add an unary constraint to the problem. An unary constraint can not be
* added while the problem is being solved or if the referenced variable has
* not been previously added to the problem. A constraint can not be added
* twice.
* @param constraint
* Constraint to add to the problem
* @return True if the constraint has been added
*/
private boolean add(final UnaryConstraint<T> constraint) {
// Can the constraint be added ?
final boolean canAdd = !searching_ &&
isVariableDeclared(constraint.getVariable()) &&
!isUnaryConstraintDeclared(constraint);
if (canAdd) {
// The problem is not being solved, the referenced variable is
// declared : the constraint is added.
unaryConstraints_.add(constraint);
}
return canAdd;
}
/**
* Add an unsized constraint to the problem. An unsized constraint can not
* be added while the problem is being solved or if one of the referenced
* variables has not been previously added to the problem. A constraint can
* not be added twice.
* @param constraint
* Constraint to add to the problem
* @return True if the constraint has been added
*/
private boolean add(final UnsizedConstraint<T> constraint) {
// Can the constraint be added ?
boolean canAdd = !searching_ && !isNAryConstraintDeclared(constraint);
final Iterator<Variable<T>> var = constraint.getVariablesIterator();
while (var.hasNext() && canAdd) {
canAdd = isVariableDeclared(var.next());
}
if (canAdd) {
// The problem is not being solved, the referenced variables are
// declared : the constraint is added.
nAryConstraints_.add(constraint);
}
return canAdd;
}
/**
* Add a variable to the problem. A variable can not be added while the
* problem is being solved. A variable can not be added twice.
* @param variable
* Variable to add to the problem
* @return True if the variable has been added
*/
public boolean add(final Variable<T> variable) {
// Can the variable be added ?
final boolean canAdd = !searching_ && !isVariableDeclared(variable);
if (canAdd) {
// The problem is not being solved and the variable has not already
// been added : the variable is added
variables_.add(variable);
}
return canAdd;
}
/**
* Apply arc consistency 3 algorithm to the problem. The list of constraints
* to evaluate is initialized with all the constraints of the problem. This
* consistency can be applied only when the problem is being solved. If this
* method is called before the start of the search it returns false.
* @return True if the problem is being solved and arc consistent
*/
private boolean applyAC3() {
// Get a copy of the N-ary constraints table
return applyAC3(nAryConstraints_);
}
/**
* Apply arc consistency 3 algorithm to the problem. The list of constraints
* to evaluate is initialized with the parameter. This consistency can be
* applied only when the problem is being solved. If this method is called
* before the start of the search it returns false.
* @param constraints
* List of constraints to revise
* @return True if the problem is being solved and arc consistent
*/
private boolean applyAC3(final List<NAryConstraint<T>> constraints) {
// Local variables
NAryConstraint<T> cst;
boolean consistent = searching_;
final List<NAryConstraint<T>> toRevise = new ArrayList<NAryConstraint<T>>(
constraints);
// The arc consistency can be applied only when the problem is being
// solved
if (searching_) {
while (consistent && !toRevise.isEmpty()) {
// Get a constraint to revise
cst = toRevise.remove(0);
consistent = cst.revise();
// Get the list of constraint to be revised once more
final List<Variable<T>> vars = new ArrayList<Variable<T>>(
cst.getRecentChangedVariables());
while (!vars.isEmpty()) {
// Get one changed variable
final Variable<T> var = vars.remove(0);
// Get the associated constraints to merge them with the
// current constraints to revise
final List<NAryConstraint<T>> varCsts = var
.getNAryConstraints();
for (NAryConstraint<T> cstToAdd : varCsts) {
if (!toRevise.contains(cstToAdd)) {
toRevise.add(cstToAdd);
}
}
}
}
}
return consistent;
}
/**
* Apply arc consistency 3 algorithm to the problem. The list of constraints
* to evaluate is initialized with constraints associated with the variable
* given as parameter. This consistency can be applied only when the problem
* is being solved. If this method is called before the start of the search
* it returns false.
* @param variable
* Variable for which the consistency must be checked
* @return True if the problem is being solved and arc consistent
*/
public boolean applyAC3(final Variable<T> variable) {
// Get a copy of the N-ary constraints table
return applyAC3(variable.getNAryConstraints());
}
/**
* Apply node consistency algorithm to the problem. This consistence can be
* applied only when the problem is being solved. If this method is called
* before the start of the search it returns false.
* @return True if the problem is being solved and node consistent
*/
private boolean applyNC() {
final boolean consistent = searching_;
// The node consistency can be applied only when the problem is being
// solved
if (searching_) {
// Revise unary constraints
final Iterator<UnaryConstraint<T>> cst = unaryConstraints_
.iterator();
while (cst.hasNext()) {
cst.next().revise();
}
}
return consistent;
}
/**
* Restore the previous state of each variable.
*/
void backtrack() {
// Restore the domains
final Iterator<Variable<T>> var = variables_.iterator();
while (var.hasNext()) {
var.next().restoreDomain();
}
// The domains stack has decreased
stackDepth_--;
}
/**
* Restore the stack of the domain stack corresponding to the given depth.
* If the current stack depth is lesser than the given stack depth, no
* backtrack is performed. Warning : All the domain deeper in the stack are
* lost.
* @param stackDepth
* Depth of the stack to reach
*/
private void backtrackToStackDepth(final int stackDepth) {
while (stackDepth_ > stackDepth) {
backtrack();
}
}
/**
* Clear the problem. All the added elements are removed. This method can
* not be called while the problem is being solved.
* @return True if the problem has been cleared
*/
public boolean clear() {
final boolean canClear = !searching_;
if (canClear) {
// The problem lists are cleared
variables_.clear();
unaryConstraints_.clear();
nAryConstraints_.clear();
}
return canClear;
}
// -----------------------------------------------------------------------//
// Problem definition services //
// -----------------------------------------------------------------------//
/**
* Get the number of choice points in the current search session.
* @return The number of choice points
*/
public int getChoicePointsCounter() {
return choicePointsCounter_;
}
/**
* Get the number of fails in the current search session.
* @return The number of fails
*/
public int getFailsCounter() {
return failsCounter_;
}
/**
* Get the first unbound variable of the problem.
* @return The first unbound variable found in the list of variables (the
* order of the list is the order in which they have been added),
* null if no variable has been found
*/
public Variable<T> getFirstUnboundVariable() {
// Variable found ?
Variable<T> found = null;
// Run through all the variables
final Iterator<Variable<T>> var = variables_.iterator();
while (var.hasNext() && found == null) {
// Get the next variable and check if it is bound
found = var.next();
if (found.isBound()) {
found = null;
}
}
return found;
}
/**
* Get the unbound variable with the greatest number of n-ary constraints.
* Only the N-ary constraints are taken into account because the unary
* constraints are not evaluated after the beginning of the search
* @return The unbound variable with the greatest number of constraints,
* null if no unbound variable is found
*/
public Variable<T> getMostConstraintUnboundVariable() {
// Variable found
Variable<T> found = null;
// Run through all the variables
final Iterator<Variable<T>> var = variables_.iterator();
while (var.hasNext()) {
// Get the next variable, then check if it is unbound and with a
// higher number of constraint
final Variable<T> next = var.next();
if (found == null ||
!next.isBound() &&
next.getNAryConstraintsNumber() > found
.getNAryConstraintsNumber()) {
found = next;
}
}
return found;
}
/**
* Get the unbound variable with the smallest not empty domain.
* @return The unbound variable with the smallest domain, null if no
* variable is unbound
*/
public Variable<T> getMostReducedUnboundVariable() {
// Variable found
Variable<T> found = null;
// Run through all the variables
final Iterator<Variable<T>> var = variables_.iterator();
while (var.hasNext()) {
// Get the next variable, then check if it is unbound and with a
// most reduced domain
final Variable<T> next = var.next();
if (!next.isBound() &&
(found == null || next.getDomainSize() < found
.getDomainSize())) {
found = next;
}
}
return found;
}
/**
* Get the number of declared constraints.
* @return The number of constraints
*/
public int getNumberOfConstraints() {
return unaryConstraints_.size() + nAryConstraints_.size();
}
/**
* Get the number of declared variables.
* @return The number of variables
*/
public int getNumberOfVariables() {
return variables_.size();
}
// -----------------------------------------------------------------------//
// Variable selectors //
// -----------------------------------------------------------------------//
/**
* Get the current stack depth of the problem.
* @return The accumulated number of calls to backtrack substracted to the
* accumulated number of calls to store.
*/
public int getStackDepth() {
return stackDepth_;
}
/**
* Increase the number of choice points.
*/
public void increaseChoicePointsCounter() {
choicePointsCounter_++;
}
/**
* Increase the number of fails.
*/
protected void increaseFailsCounter() {
failsCounter_++;
}
/**
* Search the constraint given as parameter in the table of declared N-ary
* constraints and return true if it found.
* @param constraint
* Constraint to find in the N-ary constraints table of the
* problem
* @return True if the constraint is found, false otherwise
*/
private boolean isNAryConstraintDeclared(final NAryConstraint<T> constraint) {
return nAryConstraints_.contains(constraint);
}
/**
* Search the constraint given as parameter in the table of declared unary
* constraints and return true if it found.
* @param constraint
* Constraint to find in the unary constraints table of the
* problem
* @return True if the constraint is found, false otherwise
*/
private boolean isUnaryConstraintDeclared(
final UnaryConstraint<T> constraint) {
return unaryConstraints_.contains(constraint);
}
/**
* Search the variable given as parameter in the table of declared variables
* and return true if it found.
* @param variable
* Variable to find in the variables table of the problem
* @return True if the variable is found, false otherwise
*/
private boolean isVariableDeclared(final Variable<T> variable) {
return variables_.contains(variable);
}
/**
* Search if the variable given as parameter is referenced by one more
* constraints of the problem.
* @param variable
* Variable whose references are checked
* @return True if the variable is referenced, false otherwise
*/
private boolean isVariableReferenced(final Variable<T> variable) {
// Variables locales
boolean isReferenced = false;
final Iterator<UnaryConstraint<T>> unary = unaryConstraints_.iterator();
final Iterator<NAryConstraint<T>> nary = nAryConstraints_.iterator();
// Check if the variable is referenced by an unary constraint
while (!isReferenced && unary.hasNext()) {
isReferenced = unary.next().isVariableReferenced(variable);
}
// Check if the variable is referenced by a N-ary constraint
while (!isReferenced && nary.hasNext()) {
isReferenced = nary.next().isVariableReferenced(variable);
}
return isReferenced;
}
/**
* Remove a constraint of the problem. A constraint can not be removed while
* the problem is being solved.
* @param constraint
* Constraint to remove
* @return True if the constraint has been removed
*/
public boolean remove(final Constraint<T> constraint) {
boolean canRemove = !searching_;
if (canRemove) {
if (constraint.isUnary()) {
// Remove the unary constraint
canRemove = unaryConstraints_.remove(constraint);
} else {
// Remove the N-ary constraint
canRemove = nAryConstraints_.remove(constraint);
}
}
if (canRemove) {
constraint.enablePropagate(false);
}
return canRemove;
}
/**
* Remove a variable of the problem. A variable can not be removed while the
* problem is being solved or if the variable is referenced by one or more
* constraints.
* @param variable
* Variable to remove
* @return True if the variable has been removed
*/
public boolean remove(final Variable<T> variable) {
// Can the variable be removed
final boolean canRemove = !searching_ &&
!isVariableReferenced(variable);
if (canRemove) {
// Remove the variable
variables_.remove(variable);
}
return canRemove;
}
/**
* Start the search for a solution.
* @return True when the problem is consistent. The search can be performed
* only when the problem is consistent. When the return is false,
* search is forbidden.
*/
public boolean startSearch() {
// Initializes attributes
failsCounter_ = 0;
choicePointsCounter_ = 0;
searching_ = true;
// Apply node and arc consistency
store();
if (!(applyNC() && applyAC3())) {
increaseFailsCounter();
stopSearch();
}
return searching_;
}
/**
* Stop the search for a solution.
*/
public void stopSearch() {
// Initializes attributes
searching_ = false;
// Restore domains stack
backtrackToStackDepth(1);
}
/**
* Store the current state of each variable.
*/
public void store() {
// Store the variables domain
final Iterator<Variable<T>> var = variables_.iterator();
while (var.hasNext()) {
var.next().saveDomain();
}
// The domains stack has increased
stackDepth_++;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
// String builder
final StringBuilder builder = new StringBuilder();
// Iterators
final Iterator<Variable<T>> var = variables_.iterator();
final Iterator<UnaryConstraint<T>> unary = unaryConstraints_.iterator();
final Iterator<NAryConstraint<T>> nary = nAryConstraints_.iterator();
// List of variables
builder.append("List of variables\n");
while (var.hasNext()) {
builder.append(" ");
builder.append(var.next().toString());
builder.append("\n");
}
// List of unary constraints
builder.append("\nList of unary constraints\n");
while (unary.hasNext()) {
builder.append(" ");
builder.append(unary.next().toString());
builder.append("\n");
}
// List of nary constraints
builder.append("\nList of N-ary constraints\n");
while (nary.hasNext()) {
builder.append(" ");
builder.append(nary.next().toString());
builder.append("\n");
}
return builder.toString();
}
}