Finding the lexicographically smallest solution. We first show how to find the lexicographically smallest solution of a constraint. We denote this algorithm Cmin(L, X).

A dual method is used to find the lexicographically greatest solution. We use a greedy algorithm that scans through X and extends the partial solution by selecting the smallest value from the domain of X[i] at ith step (line 6). To ensure that the selection at the next step will never lead to a failure, the algorithm enforces DC after each value selection (line 7). Algorithm 1 gives the pseudo-code for the Cmin(L, X) algorithm.

The time complexity of Algorithm 1 is O(nc + nd), where d is the total number of values in the domains of variables X and c is the (polynomial) cost of enforcing DC on C.

| Algorithm 1 Cmin(L, X) 1: procedure Cmin(L : out, X : in) 2: if (DC(C(X)) == fail) then 3: return false; 4: Y = Copy(X); 5: for i = 1 to n do 6: Y [i] = L[i] = min(D(Y [i])); 7: DC(C(Y )); 8: return true;   |
|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

Proposition 2. Let C(X) be a global constraint. Algorithm 1 returns the lexicographically smallest solution of the global constraint C if such a solution exists.

Proof. First we prove that if there is a solution to C(X) then Algorithm 1 returns a solution. Second, we prove that the solution returned is the lexicographically smallest solution.

1. If C(X) does not have a solution then Algorithm 1 fails at line 3. Otherwise C(X)
has a solution. Since DC(C(X)) leaves only consistent values, any value of X[1] can be extended to a solution of C(X) and Algorithm 1 selects L[1] to be the minimum value of X[1]. Suppose Algorithm 1 performed i−1 steps and the partial solution is [L[1], . . . , L[i − 1]]. All values left in the domains of at X[i]**, . . . , X**[n]
are consistent with the partial solution [L[1], . . . , L[i−1]]. Consequently, any value that is in the domain of X[i] is consistent with [L[1], . . . , L[i − 1]] and can be extended to a solution of C(X). The algorithm assigns L[i] to the minimum value of X[i]. Moving forward to the end of the sequence, the algorithm finds a solution to C(X).

2. By contradiction. Let L′ be the lexicographically smallest solution of C(X) and L be the solution returned by Algorithm 1. Let i be the first position where L′
and L differ so that L
′[i] < L[i], L
′[k] = L[k], k = 1**, . . . , i** − 1. Consider ith step of Algorithm 1. As DC(C(X)) is correct, all values of X[i] consistent with [L[1], . . . , L[i**−1]]** are in the domain of X[i]. The algorithm selects L[i] to be equal to min(D(X[i])). Therefore, [L[1]**, . . . , L**[i]] is the lexicographically smallest prefix of length i for a solution of C(X). Hence, there is no solution of C(X) with prefix [L
′[1], . . . , L′[i]] ≤lex [L[1]**, . . . , L**[i]]. This leads to a contradiction.