    001package org.cpsolver.ifs.extension;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.HashMap;
    007import java.util.Iterator;
    008import java.util.LinkedList;
    009import java.util.List;
    010import java.util.Map;
    011import java.util.Queue;
    012import java.util.Set;
    013
    014import org.cpsolver.ifs.assignment.Assignment;
    015import org.cpsolver.ifs.assignment.context.AssignmentContext;
    016import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
    017import org.cpsolver.ifs.model.Constraint;
    018import org.cpsolver.ifs.model.Value;
    019import org.cpsolver.ifs.model.Variable;
    020import org.cpsolver.ifs.solver.Solver;
    021import org.cpsolver.ifs.util.DataProperties;
    022import org.cpsolver.ifs.util.Progress;
    023
    024
    025/**
    026 * MAC propagation. <br>
    027 * <br>
    028 * During the arc consistency maintenance, when a value is deleted from a
    029 * variable's domain, the reason (forming an explanation) can be computed and
    030 * attached to the deleted value. Once a variable (say Vx with the assigned
    031 * value vx) is unassigned during the search, all deleted values which contain a
    032 * pair Vx = vx in their explanations need to be recomputed. Such value can be
    033 * either still inconsistent with the current (partial) solution (a different
    034 * explanation is attached to it in this case) or it can be returned back to its
    035 * variable's domain. Arc consistency is maintained after each iteration step,
    036 * i.e., the selected assignment is propagated into the not yet assigned
    037 * variables. When a value vx is assigned to a variable Vx, an explanation Vx !=
    038 * vx' &#8592; Vx = vx is attached to all values vx' of the variable Vx,
    039 * different from vx. <br>
    040 * <br>
    041 * In the case of forward checking (only constraints going from assigned
    042 * variables to unassigned variables are revised), computing explanations is
    043 * rather easy. A value vx is deleted from the domain of the variable Vx only if
    044 * there is a constraint which prohibits the assignment Vx=vx because of the
    045 * existing assignments (e.g., Vy = vy, Vz = vz). An explanation for the
    046 * deletion of this value vx is then Vx != vx &#8592; (Vy = vy &amp; ... Vz = vz),
    047 * where Vy = vy &amp; ... Vz = vz are assignments contained in the prohibiting
    048 * constraint. In case of arc consistency, a value vx is deleted from the domain
    049 * of the variable Vx if there is a constraint which does not permit the
    050 * assignment Vx = vx with other possible assignments of the other variables in
    051 * the constraint. This means that there is no support value (or combination of
    052 * values) for the value vx of the variable Vx in the constraint. An explanation
    053 * is then a union of explanations of all possible support values for the
    054 * assignment Vx = vx of this constraint which were deleted. The reason is that
    055 * if one of these support values is returned to its variable's domain, this
    056 * value vx may be returned as well (i.e., the reason for its deletion has
    057 * vanished, a new reason needs to be computed). <br>
    058 * <br>
    059 * As for the implementation, we only need to enforce arc consistency of the
    060 * initial solution and to extend unassign and assign methods. Procedure
    061 * {@link MacPropagation#afterAssigned(Assignment, long, Value)} enforces arc consistency of
    062 * the solution with the selected assignment variable = value and the procedure
    063 * {@link MacPropagation#afterUnassigned(Assignment, long, Value)} "undoes" the assignment
    064 * variable = value. It means that explanations of all values which were deleted
    065 * and which contain assignment variable = value in their explanations need to
    066 * be recomputed. This can be done via returning all these values into their
    067 * variables' domains followed by arc consistency maintenance over their
    068 * variables. <br>
    069 * <br>
    070 * Parameters:
    071 * <table border='1' summary='Related Solver Parameters'>
    072 * <tr>
    073 * <th>Parameter</th>
    074 * <th>Type</th>
    075 * <th>Comment</th>
    076 * </tr>
    077 * <tr>
    078 * <td>MacPropagation.JustForwardCheck</td>
    079 * <td>{@link Boolean}</td>
    080 * <td>If true, only forward checking instead of full arc consistency is
    081 * maintained during the search.</td>
    082 * </tr>
    083 * </table>
    084 *
    085 * @version IFS 1.3 (Iterative Forward Search)<br>
    086 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    087 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    088 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    089 * <br>
    090 *          This library is free software; you can redistribute it and/or modify
    091 *          it under the terms of the GNU Lesser General Public License as
    092 *          published by the Free Software Foundation; either version 3 of the
    093 *          License, or (at your option) any later version. <br>
    094 * <br>
    095 *          This library is distributed in the hope that it will be useful, but
    096 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    097 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    098 *          Lesser General Public License for more details. <br>
    099 * <br>
    100 *          You should have received a copy of the GNU Lesser General Public
    101 *          License along with this library; if not see
    102 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    103 * @param <V> Variable
    104 * @param <T> Value
    105 */
    106public class MacPropagation<V extends Variable<V, T>, T extends Value<V, T>> extends ExtensionWithContext<V, T, MacPropagation<V, T>.NoGood> {
    107    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacPropagation.class);
    108    private boolean iJustForwardCheck = false;
    109    private Progress iProgress;
    110
    111    /** List of constraints on which arc-consistency is to be maintained */
    112    protected List<Constraint<V, T>> iConstraints = null;
    113    /** Current iteration */
    114    protected long iIteration = 0;
    115
    116    /** Constructor
    117     * @param solver current solver
    118     * @param properties solver configuration
    119     **/
    120    public MacPropagation(Solver<V, T> solver, DataProperties properties) {
    121        super(solver, properties);
    122        iJustForwardCheck = properties.getPropertyBoolean("MacPropagation.JustForwardCheck", false);
    123    }
    124
    125    /** Adds a constraint on which arc-consistency is to be maintained
    126     * @param constraint a hard constraint
    127     **/
    128    public void addConstraint(Constraint<V, T> constraint) {
    129        if (iConstraints == null)
    130            iConstraints = new ArrayList<Constraint<V, T>>();
    131        iConstraints.add(constraint);
    132    }
    133
    134    /**
    135     * Returns true, if arc-consistency is to be maintained on the given
    136     * constraint
    137     * @param constraint a constraint
    138     * @return true if in the set
    139     */
    140    public boolean contains(Constraint<V, T> constraint) {
    141        if (iConstraints == null)
    142            return true;
    143        return iConstraints.contains(constraint);
    144    }
    145
    146    /**
    147     * Before a value is unassigned: until the value is inconsistent with the
    148     * current solution, an assignment from its explanation is picked and
    149     * unassigned.
    150     */
    151    @Override
    152    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
    153        iIteration = iteration;
    154        if (value == null)
    155            return;
    156        if (!isGood(assignment, value)) {
    157            while (!isGood(assignment, value) && !noGood(assignment, value).isEmpty()) {
    158                T noGoodValue = noGood(assignment, value).iterator().next();
    159                assignment.unassign(iteration, noGoodValue.variable());
    160            }
    161        }
    162        if (!isGood(assignment, value)) {
    163            sLogger.warn("Going to assign a bad value " + value + " with empty no-good.");
    164        }
    165    }
    166
    167    /**
    168     * After a value is assigned: explanations of other values of the value's
    169     * variable are reset (to contain only the assigned value), propagation over
    170     * the assigned variable takes place.
    171     */
    172    @Override
    173    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
    174        iIteration = iteration;
    175        if (!isGood(assignment, value)) {
    176            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(assignment, value) + ")");
    177            setGood(assignment, value);
    178        }
    179
    180        HashSet<T> noGood = new HashSet<T>(1);
    181        noGood.add(value);
    182        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
    183            T anotherValue = i.next();
    184            if (anotherValue.equals(value))
    185                continue;
    186            setNoGood(assignment, anotherValue, noGood);
    187        }
    188        getContext(assignment).propagate(assignment, value.variable());
    189    }
    190
    191    /**
    192     * After a value is unassigned: explanations of all values of unassigned
    193     * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo
    194     * over the unassigned variable takes place.
    195     */
    196    @Override
    197    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
    198        iIteration = iteration;
    199        if (!isGood(assignment, value))
    200            sLogger.error(value.variable().getName() + " = " + value.getName()
    201                    + " -- not good value unassigned (noGood:" + noGood(assignment, value) + ")");
    202        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
    203            T anotherValue = i.next();
    204            if (!isGood(assignment, anotherValue)) {
    205                Set<T> noGood = anotherValue.conflicts(assignment);
    206                if (noGood == null)
    207                    setGood(assignment, anotherValue);
    208                else
    209                    setNoGood(assignment, anotherValue, noGood);
    210            }
    211        }
    212        getContext(assignment).undoPropagate(assignment, value.variable());
    213    }
    214
    215    /** good values of a variable (values not removed from variables domain)
    216     * @param assignment current assignment
    217     * @param variable given variable
    218     * @return set of good values
    219     **/
    220    public Set<T> goodValues(Assignment<V, T> assignment, V variable) {
    221        return getContext(assignment).goodValues(variable);
    222    }
    223
    224    /** notification that a nogood value becomes good or vice versa */
    225    private void goodnessChanged(Assignment<V, T> assignment, T value) {
    226        if (isGood(assignment, value)) {
    227            goodValues(assignment, value.variable()).add(value);
    228        } else {
    229            goodValues(assignment, value.variable()).remove(value);
    230        }
    231    }
    232
    233    /** removes support of a variable */
    234    private void removeSupport(Assignment<V, T> assignment, V variable, T value) {
    235        getContext(assignment).supportValues(variable).remove(value);
    236    }
    237
    238    /** adds support of a variable */
    239    private void addSupport(Assignment<V, T> assignment, V variable, T value) {
    240        getContext(assignment).supportValues(variable).add(value);
    241    }
    242
    243    /** variables explanation
    244     * @param assignment current assignment
    245     * @param value given value
    246     * @return no-good for the value
    247     **/
    248    public Set<T> noGood(Assignment<V, T> assignment, T value) {
    249        return getContext(assignment).getNoGood(value);
    250    }
    251
    252    /** is variable good
    253     * @param assignment current assignment
    254     * @param value given value
    255     * @return true if there is no no-good set for the value
    256     **/
    257    public boolean isGood(Assignment<V, T> assignment, T value) {
    258        return getContext(assignment).getNoGood(value) == null;
    259    }
    260
    261    /** sets value to be good
    262     * @param assignment current assignment
    263     * @param value given value
    264     **/
    265    protected void setGood(Assignment<V, T> assignment, T value) {
    266        Set<T> noGood = getContext(assignment).getNoGood(value);
    267        if (noGood != null)
    268            for (T v : noGood)
    269                removeSupport(assignment, v.variable(), value);
    270        getContext(assignment).setNoGood(value, null);
    271        goodnessChanged(assignment, value);
    272    }
    273
    274    /** sets value's explanation
    275     * @param assignment current assignment
    276     * @param value given value
    277     * @param reason no-good set for the value
    278     **/
    279    public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
    280        Set<T> noGood = noGood(assignment, value);
    281        if (noGood != null)
    282            for (T v : noGood)
    283                removeSupport(assignment, v.variable(), value);
    284        getContext(assignment).setNoGood(value, reason);
    285        for (T aValue : reason)
    286            addSupport(assignment, aValue.variable(), value);
    287        goodnessChanged(assignment, value);
    288    }
    289
    290    private Set<T> reason(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable, T aValue) {
    291        Set<T> ret = new HashSet<T>();
    292
    293        for (Iterator<T> i = aVariable.values(assignment).iterator(); i.hasNext();) {
    294            T value = i.next();
    295            if (constraint.isConsistent(aValue, value)) {
    296                if (noGood(assignment, value) == null)
    297                    sLogger.error("Something went wrong: value " + value + " cannot participate in a reason.");
    298                else
    299                    ret.addAll(noGood(assignment, value));
    300            }
    301        }
    302        return ret;
    303    }
    304
    305    @Override
    306    public NoGood createAssignmentContext(Assignment<V, T> assignment) {
    307        return new NoGood(assignment);
    308    }
    309
    310    /** Propagation over the given variable.
    311     * @param assignment current assignment
    312     * @param variable given variable
    313     **/
    314    protected void propagate(Assignment<V, T> assignment, V variable) {
    315        getContext(assignment).propagate(assignment, variable);
    316    }
    317
    318    /**
    319     * Propagation undo over the given variable. All values having given
    320     * variable in their explanations needs to be recomputed. This is done in
    321     * two phases: 1) values that contain this variable in explanation are
    322     * returned back to domains (marked as good) 2) propagation over variables
    323     * which contains a value that was marked as good takes place
    324     * @param assignment current assignment
    325     * @param variable given variable
    326     */
    327    public void undoPropagate(Assignment<V, T> assignment, V variable) {
    328        getContext(assignment).undoPropagate(assignment, variable);
    329    }
    330
    331    /**
    332     * Assignment context
    333     */
    334    public class NoGood implements AssignmentContext {
    335        private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>();
    336        private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>();
    337
    338        /**
    339         * Initialization. Enforce arc-consistency over the current (initial)
    340         * solution. AC3 algorithm is used.
    341         */
    342        public NoGood(Assignment<V, T> assignment) {
    343            iProgress = Progress.getInstance(getModel());
    344            iProgress.save();
    345            iProgress.setPhase("Initializing propagation:", 3 * getModel().variables().size());
    346            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    347                V aVariable = i.next();
    348                supportValues(aVariable).clear();
    349                goodValues(aVariable).clear();
    350            }
    351            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    352                V aVariable = i.next();
    353                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
    354                    T aValue = j.next();
    355                    Set<T> noGood = aValue.conflicts(assignment);
    356                    setNoGood(aValue, noGood);
    357                    if (noGood == null) {
    358                        goodValues(aVariable).add(aValue);
    359                    } else {
    360                    }
    361                }
    362                iProgress.incProgress();
    363            }
    364            Queue<V> queue = new LinkedList<V>();
    365            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    366                V aVariable = i.next();
    367                for (Constraint<V, T> constraint : aVariable.hardConstraints()) {
    368                    propagate(assignment, constraint, aVariable, queue);
    369                }
    370                iProgress.incProgress();
    371            }
    372            if (!iJustForwardCheck)
    373                propagate(assignment, queue);
    374            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    375                V aVariable = i.next();
    376                List<T> values2delete = new ArrayList<T>();
    377                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
    378                    T aValue = j.next();
    379                    if (getNoGood(aValue) != null && getNoGood(aValue).isEmpty()) {
    380                        values2delete.add(aValue);
    381                    }
    382                }
    383                for (T val : values2delete)
    384                    aVariable.removeValue(0, val);
    385                if (aVariable.values(assignment).isEmpty()) {
    386                    sLogger.error(aVariable.getName() + " has empty domain!");
    387                }
    388                iProgress.incProgress();
    389            }
    390            iProgress.restore();
    391        }
    392
    393        public Set<T>[] getNoGood(V variable) {
    394            return iNoGood.get(variable);
    395        }
    396
    397        public void setNoGood(V variable, Set<T>[] noGood) {
    398            if (noGood == null)
    399                iNoGood.remove(variable);
    400            else
    401                iNoGood.put(variable, noGood);
    402        }
    403
    404        public Set<T> getNoGood(T value) {
    405            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
    406            if (ng == null) return null;
    407            return ng.get(value);
    408        }
    409
    410        public void setNoGood(T value, Set<T> noGood) {
    411            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
    412            if (ng == null) {
    413                ng = new HashMap<T, Set<T>>();
    414                iNoGoodVal.put(value.variable(), ng);
    415            }
    416            if (noGood == null)
    417                ng.remove(value);
    418            else
    419                ng.put(value, noGood);
    420        }
    421
    422        /** support values of a variable */
    423        @SuppressWarnings("unchecked")
    424        private Set<T> supportValues(V variable) {
    425            Set<T>[] ret = getNoGood(variable);
    426            if (ret == null) {
    427                ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
    428                setNoGood(variable, ret);
    429            }
    430            return ret[0];
    431        }
    432
    433        /** good values of a variable (values not removed from variables domain)
    434         * @param variable given variable
    435         * @return set of good values
    436         **/
    437        @SuppressWarnings("unchecked")
    438        private Set<T> goodValues(V variable) {
    439            Set<T>[] ret = getNoGood(variable);
    440            if (ret == null) {
    441                ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
    442                setNoGood(variable, ret);
    443            }
    444            return ret[1];
    445        }
    446
    447        /** propagation over a constraint */
    448        private void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable, Queue<V> queue) {
    449            if (goodValues(aVariable).isEmpty())
    450                return;
    451            List<T> conflicts = conflictValues(assignment, constraint, aVariable);
    452
    453            if (conflicts != null && !conflicts.isEmpty()) {
    454                for (T conflictValue : conflicts) {
    455                    if (!queue.contains(conflictValue.variable()))
    456                        queue.add(conflictValue.variable());
    457                    Set<T> reason = reason(assignment, constraint, aVariable, conflictValue);
    458                    // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
    459                    setNoGood(conflictValue, reason);
    460                    if (reason.isEmpty())
    461                        (conflictValue.variable()).removeValue(iIteration, conflictValue);
    462                }
    463            }
    464        }
    465
    466        protected boolean propagate(Assignment<V, T> assignment, V aVariable, V anotherVariable, List<T> adepts) {
    467            if (goodValues(aVariable).isEmpty())
    468                return false;
    469            boolean ret = false;
    470            List<T> conflicts = null;
    471            for (Constraint<V, T> constraint : anotherVariable.constraintVariables().get(aVariable)) {
    472                for (T aValue : goodValues(aVariable)) {
    473                    if (conflicts == null)
    474                        conflicts = conflictValues(constraint, aValue, adepts);
    475                    else
    476                        conflicts = conflictValues(constraint, aValue, conflicts);
    477                    if (conflicts == null || conflicts.isEmpty())
    478                        break;
    479                }
    480                if (conflicts != null && !conflicts.isEmpty())
    481                    for (T conflictValue : conflicts) {
    482                        Set<T> reason = reason(assignment, constraint, aVariable, conflictValue);
    483                        // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
    484                        setNoGood(conflictValue, reason);
    485                        adepts.remove(conflictValue);
    486                        if (reason.isEmpty())
    487                            (conflictValue.variable()).removeValue(iIteration, conflictValue);
    488                        ret = true;
    489                    }
    490            }
    491            return ret;
    492        }
    493
    494        protected boolean propagate(Assignment<V, T> assignment, V aVariable, V anotherVariable) {
    495            if (goodValues(anotherVariable).isEmpty())
    496                return false;
    497            return propagate(assignment, aVariable, anotherVariable, new ArrayList<T>(goodValues(anotherVariable)));
    498        }
    499
    500        /** Propagation over the given variable.
    501         * @param assignment current assignment
    502         * @param variable given variable
    503         **/
    504        protected void propagate(Assignment<V, T> assignment, V variable) {
    505            Queue<V> queue = new LinkedList<V>();
    506            if (assignment.getValue(variable) != null) {
    507                for (Constraint<V, T> constraint : variable.hardConstraints()) {
    508                    if (contains(constraint))
    509                        propagate(assignment, constraint, assignment.getValue(variable), queue);
    510                }
    511            } else {
    512                for (Constraint<V, T> constraint : variable.hardConstraints()) {
    513                    if (contains(constraint))
    514                        propagate(assignment, constraint, variable, queue);
    515                }
    516            }
    517            if (!iJustForwardCheck && !queue.isEmpty())
    518                propagate(assignment, queue);
    519        }
    520
    521        /** Propagation over the queue of variables.
    522         * @param assignment current assignment
    523         * @param queue variable queue
    524         **/
    525        protected void propagate(Assignment<V, T> assignment, Queue<V> queue) {
    526            while (!queue.isEmpty()) {
    527                V aVariable = queue.poll();
    528                for (Constraint<V, T> constraint : aVariable.hardConstraints()) {
    529                    if (contains(constraint))
    530                        propagate(assignment, constraint, aVariable, queue);
    531                }
    532            }
    533        }
    534
    535        /** propagation over a constraint */
    536        private void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T anAssignedValue, Queue<V> queue) {
    537            Set<T> reason = new HashSet<T>(1);
    538            reason.add(anAssignedValue);
    539            Collection<T> conflicts = conflictValues(assignment, constraint, anAssignedValue);
    540            if (conflicts != null && !conflicts.isEmpty())
    541                for (T conflictValue : conflicts) {
    542                    // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
    543                    setNoGood(conflictValue, reason);
    544                    if (!queue.contains(conflictValue.variable()))
    545                        queue.add(conflictValue.variable());
    546                }
    547        }
    548
    549        /**
    550         * Propagation undo over the given variable. All values having given
    551         * variable in thair explanations needs to be recomputed. This is done in
    552         * two phases: 1) values that contain this variable in explanation are
    553         * returned back to domains (marked as good) 2) propagation over variables
    554         * which contains a value that was marked as good takes place
    555         * @param assignment current assignment
    556         * @param variable given variable
    557         */
    558        public void undoPropagate(Assignment<V, T> assignment, V variable) {
    559            Map<V, List<T>> undoVars = new HashMap<V, List<T>>();
    560            NoGood context = getContext(assignment);
    561            while (!context.supportValues(variable).isEmpty()) {
    562                T value = context.supportValues(variable).iterator().next();
    563                Set<T> noGood = value.conflicts(assignment);
    564                if (noGood == null) {
    565                    setGood(assignment, value);
    566                    List<T> values = undoVars.get(value.variable());
    567                    if (values == null) {
    568                        values = new ArrayList<T>();
    569                        undoVars.put(value.variable(), values);
    570                    }
    571                    values.add(value);
    572                } else {
    573                    setNoGood(value, noGood);
    574                    if (noGood.isEmpty())
    575                        (value.variable()).removeValue(iIteration, value);
    576                }
    577            }
    578
    579            Queue<V> queue = new LinkedList<V>();
    580            for (V aVariable : undoVars.keySet()) {
    581                List<T> values = undoVars.get(aVariable);
    582                boolean add = false;
    583                for (V x : aVariable.constraintVariables().keySet()) {
    584                    if (propagate(assignment, x, aVariable, values))
    585                        add = true;
    586                }
    587                if (add)
    588                    queue.add(aVariable);
    589            }
    590            for (V x : variable.constraintVariables().keySet()) {
    591                if (propagate(assignment, x, variable) && !queue.contains(variable))
    592                    queue.add(variable);
    593            }
    594            if (!iJustForwardCheck)
    595                propagate(assignment, queue);
    596        }
    597
    598        private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, T aValue) {
    599            List<T> ret = new ArrayList<T>();
    600
    601            for (V variable : constraint.variables()) {
    602                if (variable.equals(aValue.variable()))
    603                    continue;
    604                if (assignment.getValue(variable) != null)
    605                    continue;
    606
    607                for (T value : goodValues(variable))
    608                    if (!constraint.isConsistent(aValue, value))
    609                        ret.add(value);
    610            }
    611            return ret;
    612        }
    613
    614        private List<T> conflictValues(Constraint<V, T> constraint, T aValue, List<T> values) {
    615            List<T> ret = new ArrayList<T>(values.size());
    616            for (T value : values)
    617                if (!constraint.isConsistent(aValue, value))
    618                    ret.add(value);
    619            return ret;
    620        }
    621
    622        private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable) {
    623            List<T> conflicts = null;
    624            for (T aValue : goodValues(aVariable)) {
    625                if (conflicts == null)
    626                    conflicts = conflictValues(assignment, constraint, aValue);
    627                else
    628                    conflicts = conflictValues(constraint, aValue, conflicts);
    629                if (conflicts == null || conflicts.isEmpty())
    630                    return null;
    631            }
    632            return conflicts;
    633        }
    634    }
    635
    636}