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

An inconsistency is detected.

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

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.

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 removes all the infeasible values: it achieves domain consistency.

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.

An inconsistency is detected.

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

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

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

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

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

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 node indices 2 and 4 are in the same strongly connected component.

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

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.

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

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.