There are several very different repair algorithms that arise from different choices of how to change the value of a variable from its tentative value. The algorithm most similar to constructive search simply instantiates the variable to the chosen new value. In this case the tentative values do no more than support a specific heuristic within a constructive search algorithm. Notice that the heuristic can do more than simply choosing the tentative value as the first guess for each variable during labelling. It can also take into account for each value for a variable the number of other tentative values with which it conflicts according to the constraints. Thus when a variable is labelled to a new value, the value is chosen so as to minimise disruption to the original solution.

The ECLiPSe *repair* library defines primitives for setting a
tentative value for a variable (*tent_set*) and for looking it up
(*tent_get*).
It also supports a special annotation which
changes the behaviour of a constraint from propagation to simply
checking against the
tentative values of their uninstantiated variables.
The annotation is written *Constraint r*, where *Constraint*
can be any built-in or user-defined constraint.
Whenever the check fails, the constraint is recorded as a *
conflict constraint*, and full propagation on the constraint is
switched on.
The set of conflict constraints can be accessed via the predicate *
conflict_constraints*.
This can be used in the search procedure to decide which variable to
label next.

A built-in search predicate called *repair* is provided which
selects a variable whose tentative value violates a repair constraint,
labels it and succeeds when all the remaining variables have
consistent tentative values.

We illustrate this repair algorithm (with an example from the IC-Parc ECLiPSe library manual [SNE97]) in figure 5.2.1.

The solutions found are [1,3,1] and [1,3,2], which means that onlysolve(X,Y,Z) :- [X,Y,Z]::1..3, % the problem variables Y ## X r, % state the constraints Y ## Z r, Y #= 3 r, [X,Y,Z] tent_set [1,2,3], % set existing solution repair, % invoke repair labeling [X,Y,Z] tent_get [NewX,NewY,NewZ]. % get repaired solutionThe ``Constructive'' Repair Algorithm

The constraint is not affected by the update. In
particular, *X*
keeps the value of the existing solution, and is
not even being labeled by *repair/0*.

Constructive repair is also known as *informed backtracking* and
has been used successfully on a variety of benchmarks
[MJPL92].

Wed Sep 3 18:07:19 BST 1997