Problem.java

  1. /* Copyright 2015 Laurent COCAULT
  2.  * Licensed to Laurent COCAULT under one or more contributor license agreements.
  3.  * See the NOTICE file distributed with this work for additional information
  4.  * regarding copyright ownership. Laurent COCAULT licenses this file to You
  5.  * under the Apache License, Version 2.0 (the "License"); you may not use this
  6.  * file except in compliance with the License.  You may obtain a copy of the
  7.  * License at
  8.  *
  9.  *   http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.csp.constraint.solver;

  18. import java.util.ArrayList;
  19. import java.util.Iterator;
  20. import java.util.List;

  21. import org.csp.constraint.model.BinaryConstraint;
  22. import org.csp.constraint.model.Constraint;
  23. import org.csp.constraint.model.NAryConstraint;
  24. import org.csp.constraint.model.TernaryConstraint;
  25. import org.csp.constraint.model.UnaryConstraint;
  26. import org.csp.constraint.model.UnsizedConstraint;
  27. import org.csp.constraint.model.Variable;

  28. /**
  29.  * Represents a constraint solving problem.
  30.  */
  31. public class Problem<T> {

  32.     /**
  33.      * True when the problem is being solved.
  34.      */
  35.     private boolean searching_;

  36.     /**
  37.      * Number of fails since the beginning of the search session.
  38.      */
  39.     private int failsCounter_;

  40.     /**
  41.      * Number of choice points since the beginning of the search session.
  42.      */
  43.     private int choicePointsCounter_;

  44.     /**
  45.      * During the search, variable states are saved and restored in a stack.
  46.      * This attribute counts the number of states currently stored in this
  47.      * stack.
  48.      */
  49.     private int stackDepth_;

  50.     /**
  51.      * Table of variables declared in the problem. A variable is considered
  52.      * declared once it has been successfully added to problem and until it is
  53.      * removed.
  54.      */
  55.     private List<Variable<T>> variables_;

  56.     /**
  57.      * Table of unary constraints declared in the problem. An unary constraint
  58.      * is considered declared once it has been successfully added to problem and
  59.      * until it is removed.
  60.      */
  61.     private List<UnaryConstraint<T>> unaryConstraints_;

  62.     /**
  63.      * Table of N-ary constraints declared in the problem. An N-ary constraint
  64.      * is considered declared once it has been successfully added to problem and
  65.      * until it is removed.
  66.      */
  67.     private List<NAryConstraint<T>> nAryConstraints_;

  68.     /**
  69.      * Constructor.
  70.      */
  71.     public Problem() {
  72.         // Counters and flags
  73.         searching_ = false;
  74.         failsCounter_ = 0;
  75.         choicePointsCounter_ = 0;
  76.         stackDepth_ = 1;
  77.         // Collection of variables and constraints
  78.         variables_ = new ArrayList<Variable<T>>();
  79.         unaryConstraints_ = new ArrayList<UnaryConstraint<T>>();
  80.         nAryConstraints_ = new ArrayList<NAryConstraint<T>>();
  81.     }

  82.     // -----------------------------------------------------------------------//
  83.     // Search services //
  84.     // -----------------------------------------------------------------------//

  85.     /**
  86.      * Add a binary constraint to the problem. A binary constraint can not be
  87.      * added while the problem is being solved or if one of the referenced
  88.      * variables has not been previously added to the problem. A constraint can
  89.      * not be added twice.
  90.      * @param constraint
  91.      *            Constraint to add to the problem
  92.      * @return True if the constraint has been added
  93.      */
  94.     private boolean add(final BinaryConstraint<T> constraint) {

  95.         // Can the constraint be added ?
  96.         final boolean canAdd = !searching_ &&
  97.                 isVariableDeclared(constraint.getFirstVariable()) &&
  98.                 isVariableDeclared(constraint.getSecondVariable()) &&
  99.                 !isNAryConstraintDeclared(constraint);

  100.         if (canAdd) {
  101.             // The problem is not being solved, the two referenced variables are
  102.             // declared : the constraint is added.
  103.             nAryConstraints_.add(constraint);
  104.         }

  105.         return canAdd;
  106.     }

  107.     /**
  108.      * Add a constraint to the problem. A constraint can not be added while the
  109.      * problem is being solved or if one of the referenced variables has not
  110.      * been previously added to the problem. A constraint can not be added
  111.      * twice.
  112.      * @param constraint
  113.      *            Constraint to add to the problem
  114.      * @return True if the constraint has been added
  115.      */
  116.     public boolean add(final Constraint<T> constraint) {

  117.         // Can the constraint be added
  118.         boolean canAdd = false;
  119.         if (constraint.isUnary()) {
  120.             // Unary constraint
  121.             canAdd = add((UnaryConstraint<T>) constraint);
  122.         } else if (constraint.isBinary()) {
  123.             // Binary constraint
  124.             canAdd = add((BinaryConstraint<T>) constraint);
  125.         } else if (constraint.isTernary()) {
  126.             // Ternary constraint
  127.             canAdd = add((TernaryConstraint<T>) constraint);
  128.         } else if (constraint.isUnsized()) {
  129.             // Unsized N-ary constraint
  130.             canAdd = add((UnsizedConstraint<T>) constraint);
  131.         }
  132.         if (canAdd) {
  133.             constraint.enablePropagate(true);
  134.         }

  135.         return canAdd;
  136.     }

  137.     /**
  138.      * Add a ternary constraint to the problem. A ternary constraint can not be
  139.      * added while the problem is being solved or if one of the referenced
  140.      * variables has not been previously added to the problem. A constraint can
  141.      * not be added twice.
  142.      * @param constraint
  143.      *            Constraint to add to the problem
  144.      * @return True if the constraint has been added
  145.      */
  146.     private boolean add(final TernaryConstraint<T> constraint) {

  147.         // Can the constraint be added ?
  148.         final boolean canAdd = !searching_ &&
  149.                 isVariableDeclared(constraint.getFirstVariable()) &&
  150.                 isVariableDeclared(constraint.getSecondVariable()) &&
  151.                 isVariableDeclared(constraint.getThirdVariable()) &&
  152.                 !isNAryConstraintDeclared(constraint);

  153.         if (canAdd) {
  154.             // The problem is not being solved, the three referenced variables
  155.             // are declared : the constraint is added.
  156.             nAryConstraints_.add(constraint);
  157.         }

  158.         return canAdd;
  159.     }

  160.     /**
  161.      * Add an unary constraint to the problem. An unary constraint can not be
  162.      * added while the problem is being solved or if the referenced variable has
  163.      * not been previously added to the problem. A constraint can not be added
  164.      * twice.
  165.      * @param constraint
  166.      *            Constraint to add to the problem
  167.      * @return True if the constraint has been added
  168.      */
  169.     private boolean add(final UnaryConstraint<T> constraint) {

  170.         // Can the constraint be added ?
  171.         final boolean canAdd = !searching_ &&
  172.                 isVariableDeclared(constraint.getVariable()) &&
  173.                 !isUnaryConstraintDeclared(constraint);

  174.         if (canAdd) {
  175.             // The problem is not being solved, the referenced variable is
  176.             // declared : the constraint is added.
  177.             unaryConstraints_.add(constraint);
  178.         }

  179.         return canAdd;
  180.     }

  181.     /**
  182.      * Add an unsized constraint to the problem. An unsized constraint can not
  183.      * be added while the problem is being solved or if one of the referenced
  184.      * variables has not been previously added to the problem. A constraint can
  185.      * not be added twice.
  186.      * @param constraint
  187.      *            Constraint to add to the problem
  188.      * @return True if the constraint has been added
  189.      */
  190.     private boolean add(final UnsizedConstraint<T> constraint) {

  191.         // Can the constraint be added ?
  192.         boolean canAdd = !searching_ && !isNAryConstraintDeclared(constraint);
  193.         final Iterator<Variable<T>> var = constraint.getVariablesIterator();
  194.         while (var.hasNext() && canAdd) {
  195.             canAdd = isVariableDeclared(var.next());
  196.         }

  197.         if (canAdd) {
  198.             // The problem is not being solved, the referenced variables are
  199.             // declared : the constraint is added.
  200.             nAryConstraints_.add(constraint);
  201.         }

  202.         return canAdd;
  203.     }

  204.     /**
  205.      * Add a variable to the problem. A variable can not be added while the
  206.      * problem is being solved. A variable can not be added twice.
  207.      * @param variable
  208.      *            Variable to add to the problem
  209.      * @return True if the variable has been added
  210.      */
  211.     public boolean add(final Variable<T> variable) {

  212.         // Can the variable be added ?
  213.         final boolean canAdd = !searching_ && !isVariableDeclared(variable);
  214.         if (canAdd) {
  215.             // The problem is not being solved and the variable has not already
  216.             // been added : the variable is added
  217.             variables_.add(variable);
  218.         }
  219.         return canAdd;
  220.     }

  221.     /**
  222.      * Apply arc consistency 3 algorithm to the problem. The list of constraints
  223.      * to evaluate is initialized with all the constraints of the problem. This
  224.      * consistency can be applied only when the problem is being solved. If this
  225.      * method is called before the start of the search it returns false.
  226.      * @return True if the problem is being solved and arc consistent
  227.      */
  228.     private boolean applyAC3() {
  229.         // Get a copy of the N-ary constraints table
  230.         return applyAC3(nAryConstraints_);
  231.     }

  232.     /**
  233.      * Apply arc consistency 3 algorithm to the problem. The list of constraints
  234.      * to evaluate is initialized with the parameter. This consistency can be
  235.      * applied only when the problem is being solved. If this method is called
  236.      * before the start of the search it returns false.
  237.      * @param constraints
  238.      *            List of constraints to revise
  239.      * @return True if the problem is being solved and arc consistent
  240.      */
  241.     private boolean applyAC3(final List<NAryConstraint<T>> constraints) {

  242.         // Local variables
  243.         NAryConstraint<T> cst;
  244.         boolean consistent = searching_;
  245.         final List<NAryConstraint<T>> toRevise = new ArrayList<NAryConstraint<T>>(
  246.                 constraints);

  247.         // The arc consistency can be applied only when the problem is being
  248.         // solved
  249.         if (searching_) {
  250.             while (consistent && !toRevise.isEmpty()) {

  251.                 // Get a constraint to revise
  252.                 cst = toRevise.remove(0);
  253.                 consistent = cst.revise();

  254.                 // Get the list of constraint to be revised once more
  255.                 final List<Variable<T>> vars = new ArrayList<Variable<T>>(
  256.                         cst.getRecentChangedVariables());
  257.                 while (!vars.isEmpty()) {

  258.                     // Get one changed variable
  259.                     final Variable<T> var = vars.remove(0);

  260.                     // Get the associated constraints to merge them with the
  261.                     // current constraints to revise
  262.                     final List<NAryConstraint<T>> varCsts = var
  263.                             .getNAryConstraints();
  264.                     for (NAryConstraint<T> cstToAdd : varCsts) {
  265.                         if (!toRevise.contains(cstToAdd)) {
  266.                             toRevise.add(cstToAdd);
  267.                         }
  268.                     }
  269.                 }
  270.             }
  271.         }

  272.         return consistent;
  273.     }

  274.     /**
  275.      * Apply arc consistency 3 algorithm to the problem. The list of constraints
  276.      * to evaluate is initialized with constraints associated with the variable
  277.      * given as parameter. This consistency can be applied only when the problem
  278.      * is being solved. If this method is called before the start of the search
  279.      * it returns false.
  280.      * @param variable
  281.      *            Variable for which the consistency must be checked
  282.      * @return True if the problem is being solved and arc consistent
  283.      */
  284.     public boolean applyAC3(final Variable<T> variable) {
  285.         // Get a copy of the N-ary constraints table
  286.         return applyAC3(variable.getNAryConstraints());
  287.     }

  288.     /**
  289.      * Apply node consistency algorithm to the problem. This consistence can be
  290.      * applied only when the problem is being solved. If this method is called
  291.      * before the start of the search it returns false.
  292.      * @return True if the problem is being solved and node consistent
  293.      */
  294.     private boolean applyNC() {
  295.         final boolean consistent = searching_;

  296.         // The node consistency can be applied only when the problem is being
  297.         // solved
  298.         if (searching_) {

  299.             // Revise unary constraints
  300.             final Iterator<UnaryConstraint<T>> cst = unaryConstraints_
  301.                     .iterator();
  302.             while (cst.hasNext()) {
  303.                 cst.next().revise();
  304.             }
  305.         }
  306.         return consistent;
  307.     }

  308.     /**
  309.      * Restore the previous state of each variable.
  310.      */
  311.     void backtrack() {

  312.         // Restore the domains
  313.         final Iterator<Variable<T>> var = variables_.iterator();
  314.         while (var.hasNext()) {
  315.             var.next().restoreDomain();
  316.         }

  317.         // The domains stack has decreased
  318.         stackDepth_--;
  319.     }

  320.     /**
  321.      * Restore the stack of the domain stack corresponding to the given depth.
  322.      * If the current stack depth is lesser than the given stack depth, no
  323.      * backtrack is performed. Warning : All the domain deeper in the stack are
  324.      * lost.
  325.      * @param stackDepth
  326.      *            Depth of the stack to reach
  327.      */
  328.     private void backtrackToStackDepth(final int stackDepth) {
  329.         while (stackDepth_ > stackDepth) {
  330.             backtrack();
  331.         }
  332.     }

  333.     /**
  334.      * Clear the problem. All the added elements are removed. This method can
  335.      * not be called while the problem is being solved.
  336.      * @return True if the problem has been cleared
  337.      */
  338.     public boolean clear() {
  339.         final boolean canClear = !searching_;
  340.         if (canClear) {
  341.             // The problem lists are cleared
  342.             variables_.clear();
  343.             unaryConstraints_.clear();
  344.             nAryConstraints_.clear();
  345.         }
  346.         return canClear;
  347.     }

  348.     // -----------------------------------------------------------------------//
  349.     // Problem definition services //
  350.     // -----------------------------------------------------------------------//

  351.     /**
  352.      * Get the number of choice points in the current search session.
  353.      * @return The number of choice points
  354.      */
  355.     public int getChoicePointsCounter() {
  356.         return choicePointsCounter_;
  357.     }

  358.     /**
  359.      * Get the number of fails in the current search session.
  360.      * @return The number of fails
  361.      */
  362.     public int getFailsCounter() {
  363.         return failsCounter_;
  364.     }

  365.     /**
  366.      * Get the first unbound variable of the problem.
  367.      * @return The first unbound variable found in the list of variables (the
  368.      *         order of the list is the order in which they have been added),
  369.      *         null if no variable has been found
  370.      */
  371.     public Variable<T> getFirstUnboundVariable() {

  372.         // Variable found ?
  373.         Variable<T> found = null;

  374.         // Run through all the variables
  375.         final Iterator<Variable<T>> var = variables_.iterator();
  376.         while (var.hasNext() && found == null) {

  377.             // Get the next variable and check if it is bound
  378.             found = var.next();
  379.             if (found.isBound()) {
  380.                 found = null;
  381.             }
  382.         }

  383.         return found;
  384.     }

  385.     /**
  386.      * Get the unbound variable with the greatest number of n-ary constraints.
  387.      * Only the N-ary constraints are taken into account because the unary
  388.      * constraints are not evaluated after the beginning of the search
  389.      * @return The unbound variable with the greatest number of constraints,
  390.      *         null if no unbound variable is found
  391.      */
  392.     public Variable<T> getMostConstraintUnboundVariable() {

  393.         // Variable found
  394.         Variable<T> found = null;

  395.         // Run through all the variables
  396.         final Iterator<Variable<T>> var = variables_.iterator();
  397.         while (var.hasNext()) {

  398.             // Get the next variable, then check if it is unbound and with a
  399.             // higher number of constraint
  400.             final Variable<T> next = var.next();
  401.             if (found == null ||
  402.                     !next.isBound() &&
  403.                     next.getNAryConstraintsNumber() > found
  404.                             .getNAryConstraintsNumber()) {
  405.                 found = next;
  406.             }
  407.         }

  408.         return found;
  409.     }

  410.     /**
  411.      * Get the unbound variable with the smallest not empty domain.
  412.      * @return The unbound variable with the smallest domain, null if no
  413.      *         variable is unbound
  414.      */
  415.     public Variable<T> getMostReducedUnboundVariable() {

  416.         // Variable found
  417.         Variable<T> found = null;

  418.         // Run through all the variables
  419.         final Iterator<Variable<T>> var = variables_.iterator();
  420.         while (var.hasNext()) {

  421.             // Get the next variable, then check if it is unbound and with a
  422.             // most reduced domain
  423.             final Variable<T> next = var.next();
  424.             if (!next.isBound() &&
  425.                     (found == null || next.getDomainSize() < found
  426.                             .getDomainSize())) {
  427.                 found = next;
  428.             }
  429.         }

  430.         return found;
  431.     }

  432.     /**
  433.      * Get the number of declared constraints.
  434.      * @return The number of constraints
  435.      */
  436.     public int getNumberOfConstraints() {
  437.         return unaryConstraints_.size() + nAryConstraints_.size();
  438.     }

  439.     /**
  440.      * Get the number of declared variables.
  441.      * @return The number of variables
  442.      */
  443.     public int getNumberOfVariables() {
  444.         return variables_.size();
  445.     }

  446.     // -----------------------------------------------------------------------//
  447.     // Variable selectors //
  448.     // -----------------------------------------------------------------------//

  449.     /**
  450.      * Get the current stack depth of the problem.
  451.      * @return The accumulated number of calls to backtrack substracted to the
  452.      *         accumulated number of calls to store.
  453.      */
  454.     public int getStackDepth() {
  455.         return stackDepth_;
  456.     }

  457.     /**
  458.      * Increase the number of choice points.
  459.      */
  460.     public void increaseChoicePointsCounter() {
  461.         choicePointsCounter_++;
  462.     }

  463.     /**
  464.      * Increase the number of fails.
  465.      */
  466.     protected void increaseFailsCounter() {
  467.         failsCounter_++;
  468.     }

  469.     /**
  470.      * Search the constraint given as parameter in the table of declared N-ary
  471.      * constraints and return true if it found.
  472.      * @param constraint
  473.      *            Constraint to find in the N-ary constraints table of the
  474.      *            problem
  475.      * @return True if the constraint is found, false otherwise
  476.      */
  477.     private boolean isNAryConstraintDeclared(final NAryConstraint<T> constraint) {
  478.         return nAryConstraints_.contains(constraint);
  479.     }

  480.     /**
  481.      * Search the constraint given as parameter in the table of declared unary
  482.      * constraints and return true if it found.
  483.      * @param constraint
  484.      *            Constraint to find in the unary constraints table of the
  485.      *            problem
  486.      * @return True if the constraint is found, false otherwise
  487.      */
  488.     private boolean isUnaryConstraintDeclared(
  489.             final UnaryConstraint<T> constraint) {
  490.         return unaryConstraints_.contains(constraint);
  491.     }

  492.     /**
  493.      * Search the variable given as parameter in the table of declared variables
  494.      * and return true if it found.
  495.      * @param variable
  496.      *            Variable to find in the variables table of the problem
  497.      * @return True if the variable is found, false otherwise
  498.      */
  499.     private boolean isVariableDeclared(final Variable<T> variable) {
  500.         return variables_.contains(variable);
  501.     }

  502.     /**
  503.      * Search if the variable given as parameter is referenced by one more
  504.      * constraints of the problem.
  505.      * @param variable
  506.      *            Variable whose references are checked
  507.      * @return True if the variable is referenced, false otherwise
  508.      */
  509.     private boolean isVariableReferenced(final Variable<T> variable) {

  510.         // Variables locales
  511.         boolean isReferenced = false;
  512.         final Iterator<UnaryConstraint<T>> unary = unaryConstraints_.iterator();
  513.         final Iterator<NAryConstraint<T>> nary = nAryConstraints_.iterator();

  514.         // Check if the variable is referenced by an unary constraint
  515.         while (!isReferenced && unary.hasNext()) {
  516.             isReferenced = unary.next().isVariableReferenced(variable);
  517.         }

  518.         // Check if the variable is referenced by a N-ary constraint
  519.         while (!isReferenced && nary.hasNext()) {
  520.             isReferenced = nary.next().isVariableReferenced(variable);
  521.         }

  522.         return isReferenced;
  523.     }

  524.     /**
  525.      * Remove a constraint of the problem. A constraint can not be removed while
  526.      * the problem is being solved.
  527.      * @param constraint
  528.      *            Constraint to remove
  529.      * @return True if the constraint has been removed
  530.      */
  531.     public boolean remove(final Constraint<T> constraint) {
  532.         boolean canRemove = !searching_;
  533.         if (canRemove) {
  534.             if (constraint.isUnary()) {
  535.                 // Remove the unary constraint
  536.                 canRemove = unaryConstraints_.remove(constraint);
  537.             } else {
  538.                 // Remove the N-ary constraint
  539.                 canRemove = nAryConstraints_.remove(constraint);
  540.             }
  541.         }

  542.         if (canRemove) {
  543.             constraint.enablePropagate(false);
  544.         }

  545.         return canRemove;
  546.     }

  547.     /**
  548.      * Remove a variable of the problem. A variable can not be removed while the
  549.      * problem is being solved or if the variable is referenced by one or more
  550.      * constraints.
  551.      * @param variable
  552.      *            Variable to remove
  553.      * @return True if the variable has been removed
  554.      */
  555.     public boolean remove(final Variable<T> variable) {

  556.         // Can the variable be removed
  557.         final boolean canRemove = !searching_ &&
  558.                 !isVariableReferenced(variable);
  559.         if (canRemove) {
  560.             // Remove the variable
  561.             variables_.remove(variable);
  562.         }
  563.         return canRemove;
  564.     }

  565.     /**
  566.      * Start the search for a solution.
  567.      * @return True when the problem is consistent. The search can be performed
  568.      *         only when the problem is consistent. When the return is false,
  569.      *         search is forbidden.
  570.      */
  571.     public boolean startSearch() {

  572.         // Initializes attributes
  573.         failsCounter_ = 0;
  574.         choicePointsCounter_ = 0;
  575.         searching_ = true;

  576.         // Apply node and arc consistency
  577.         store();
  578.         if (!(applyNC() && applyAC3())) {
  579.             increaseFailsCounter();
  580.             stopSearch();
  581.         }

  582.         return searching_;
  583.     }

  584.     /**
  585.      * Stop the search for a solution.
  586.      */
  587.     public void stopSearch() {
  588.         // Initializes attributes
  589.         searching_ = false;
  590.         // Restore domains stack
  591.         backtrackToStackDepth(1);
  592.     }

  593.     /**
  594.      * Store the current state of each variable.
  595.      */
  596.     public void store() {

  597.         // Store the variables domain
  598.         final Iterator<Variable<T>> var = variables_.iterator();
  599.         while (var.hasNext()) {
  600.             var.next().saveDomain();
  601.         }

  602.         // The domains stack has increased
  603.         stackDepth_++;
  604.     }

  605.     /**
  606.      * {@inheritDoc}
  607.      */
  608.     @Override
  609.     public String toString() {

  610.         // String builder
  611.         final StringBuilder builder = new StringBuilder();

  612.         // Iterators
  613.         final Iterator<Variable<T>> var = variables_.iterator();
  614.         final Iterator<UnaryConstraint<T>> unary = unaryConstraints_.iterator();
  615.         final Iterator<NAryConstraint<T>> nary = nAryConstraints_.iterator();

  616.         // List of variables
  617.         builder.append("List of variables\n");
  618.         while (var.hasNext()) {
  619.             builder.append("   ");
  620.             builder.append(var.next().toString());
  621.             builder.append("\n");
  622.         }

  623.         // List of unary constraints
  624.         builder.append("\nList of unary constraints\n");
  625.         while (unary.hasNext()) {
  626.             builder.append("   ");
  627.             builder.append(unary.next().toString());
  628.             builder.append("\n");
  629.         }

  630.         // List of nary constraints
  631.         builder.append("\nList of N-ary constraints\n");
  632.         while (nary.hasNext()) {
  633.             builder.append("   ");
  634.             builder.append(nary.next().toString());
  635.             builder.append("\n");
  636.         }

  637.         return builder.toString();
  638.     }

  639. }