Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 4.8.2.3 Any Conflict

An even simpler alternative, instead of choosing the best step, is to select any variable participating in a conflict and change its value. At each step, one of the variables involved in a violated constraint is selected at random. The algorithm assigns to that variable one of the values that minimizes the number of violated constraints.

To implement this alternative, we require a data structure to represent the set *C* of
variables involved in a conflict. This data structure
should be designed for quick selection of a random member of *C*.
When a variable *X* has its value
changed, each constraint in which *X* is involved is checked. For each
such constraint that has become violated, all of the variables
involved in the constraint are added to *C*. For each such constraint that is no longer
violated, those variables involved in
that constraint, but not involved in
another violated constraint, are removed from *C*. One way to check
whether a variable is involved in another conflict is to
maintain a count of the number of conflicts for each variable, which
is incremented when a constraint becomes violated and decremented
when a constraint is no longer violated.

Each of the preceding algorithms can be combined with random steps, random restarts, and a tabu mechanism.