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();
- }
- }