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

An inconsistency is detected.

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

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

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 considered.

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.

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).

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

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.

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

An inconsistency is detected.

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

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

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

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

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 indices 2 and 4 are in two different strongly connected components.

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

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-length alternating cycle.

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.