[1-17] Explanation of value ordering heuristics

> Can someone tell me what is the definition of VALUE ORDERING
> and what is its purpose, and are there any rules to follow
> when doing value ordering or is it domain dependent?

In Constraint Satisfaction Problems, once you have decided which
_variable_ to instantiate next, say V, if V has more than one possible
value, you might ask which _value_ to choose first.

The simplest is to go systematically through the domain of V from
smallest to largest. But if V has domain [1,2,...10] and (by some
magic) you know that some/all the solutions to your CSP have V=10, then
it would be nice if you could try V=10 first, before wasting a lot of
work on 1,2,...

One well-known heuristic is to choose that value for V which is
consistent with the _greatest_ number of the constraints on V. If V is
only involved in constraints with X, and the possible values for (V,X)
are (1,2), (1,3), (2,3), then you should choose V=1 before trying V=2.

Unfortunately, it is quite expensive to keep on checking which is the
most popular value in this sense. (And there is no point doing it if
you want all solutions, as you will have to try V=1 and V=2 anyway.) It
is so expensive that it is usually not worth doing.

Of course, if you have problem-specific knowledge it might suggest a
different heuristic, which might be good in your particular circumstances.

In contrast, the first-fail heuristic for choosing which _variable_ to
instantiate next by choosing the one with smallest domain size, is (a)
very cheap (b) often gives good benefits.