What is Least-Constraining-Value?

In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are:

• Minimum-remaining-values (how many values are still valid for this variable)
• Degree heuristic (how many other variables are affected by this variable)
• Least-constraining-value (what value will leave the most other values for other variables)

The first two are pretty obvious and simple to implement. First choose the variable that has the least values left in its domain, and if there are ties, choose the one that affects the most other variables. This way if a parent step in the solver picked a bad assignment, you are likely to find out sooner and thereby save time if you choose the variable with the least values left that affects the most other things.

Those are simple, clearly defined, and easy to implement.

Least-constraining-value is not clearly defined, anywhere I looked. Artificial Intelligence: A Modern Approach (Russel & Norvig) just says:

It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.

Searching for "least-constraining-value" only turned up a lot of university slide shows based on this textbook, with no further information on how this would be done algorithmically.

The only example given for this heuristic is a case where one choice of value eliminates all choices for a neighboring variable, and the other does not. The problem with this example is that it this is a trivial case, which would be eliminated immediately when the potential assignment is checked for consistency with the problem's constraints. So in all the examples I could find, the least-constraining-value heuristic didn't actually benefit the solver performance in any way, except for a small negative effect from adding a redundant check.

The only other thing I can think of would be to test the possible assignments of the neighboring variables for each assignment, and count the number of possible assignments of the neighbors that exist for each possible assignment of this variable, then order the values for this variable based on the number of neighbor assignments available if that value is chosen. However, I don't see how this would offer an improvement over a random order, since this requires both testing numerous variable combinations and sorting based on the results from counting.

Can anyone give a more useful description of least-constraining-value, and explain how that version of least-constraining-value would actually yield an improvement?

• AI:AMA (pp. 228) mentions that the least constraining value heuristic was proposed by Haralick and Elliot (1980). The paper (found here) uses a much different language than is used in AI:AMA and I am having trouble determining which section refers to the LCV heuristic.
– ryan
May 15 '19 at 3:09

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

It first picks variable "O" and then tests "O" with all of it's legal values "i" to see the number of reductions on "O"'s neighbors "N". It adds all of them. and picks an "i" that causes less reductions:

sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
For i from 0 to 9:
plug "o=i" into the constraint formulas
For each neighbor "N" of "o" in the constraint graph:
sums[i] += the number of values remaining for "N"

It picks "i" so that:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}