The decision repair algorithm (Jussien and Lhomme,
Artificial Intelligence139 (2002) 21–45),
which has been designed to solve constraint satisfaction problems (CSP), can
be seen, either (i) as an extension of the classical depth first tree
search algorithm with the introduction of a free choice of the variable to
which to backtrack in case of inconsistency, or (ii) as a local
search algorithm in the space of the partial consistent variable
assignments. or (iii) as a hybridisation between local search
and constraint propagation. Experiments reported in
Pralet and Verfailllie (2004) show that some heuristics for the choice of the
variable to which to backtrack behave well on consistent instances and
that other heuristics behave well on inconsistent ones. They show also
that, despite its a priori incompleteness, decision repair,
equipped with some specific heuristics, can solve within a limited time
almost all the consistent and inconsistent randomly generated
instances over the whole constrainedness spectrum. In this paper, we
discuss the heuristics that could be used by decision
repair to solve consistent instances, on the one hand, and
inconsistent ones, on the other hand. Moreover, we establish that
some specific heuristics make decision repair complete.