D(X3) = {2,3,4,5}

D(X3) = {3,4,5}

An inconsistency is detected.

Deactivating a constraint is not a reversible operation: the constraint will never be called again for the remainder of the search tree, even after backtracking.

The forward-checking filtering algorithm for AllDifferent removes the same values as the binary decomposition.

The forward-checking filtering algorithm removes all the infeasible values: it achieves domain consistency.

Whatever the (deterministic) heuristic used for the variable and value selection for the n-Queens problem, the search tree explored with forward-checking filtering for AllDifferent is the same as with the binary decomposition (same number of nodes).

A deactivated constraint will not be propagated, but since it is in the stacks of the constraints on the variables, the constraint will nevertheless be scanned.

The forward-checking filtering algorithm without the sparse-set trick (thus scanning all the variables every time in order to possibly remove a value) is faster than the binary decomposition.

D(X3) = {3,4,5}

An inconsistency is detected.

D(X3) = {2,3,4,5}

The node indices 2 and 4 are in the same strongly connected component.

The node indices 2 and 4 are in two different strongly connected components.

The node label of value 2 in the residual graph is 2.

The number of strongly connected components in the residual graph is 2.

The number of strongly connected components in the residual graph is 3.

The node label of value 2 in the residual graph is 6.

The node label of value 2 in the residual graph is 5.

An edge belongs to some maximum matching (in the variable-value graph) if and only if for every maximum matching, it belongs to an alternating path.

Given a maximum matching (in the variable-value graph), the domain-consistent filtering algorithm for \(AllDifferent(X_1,\dots,X_n)\) can be implemented to run in \(O(|D(X_1)|+\dots+|D(X_n)|)\) time.

The maximum matching needs to be stored in a stateful data-structure since it may not be valid anymore on backtrack.

An edge belongs to some maximum matching (in the variable-value graph) if and only if for every maximum matching, it belongs to an even alternating cycle.