  We study the performances of stochastic heuristic search algorithms on
Uniquely Extendible Constraint Satisfaction Problems with random inputs. We
show that, for any heuristic preserving the Poissonian nature of the underlying
instance, the (heuristic-dependent) largest ratio $\alpha_a$ of constraints per
variables for which a search algorithm is likely to find solutions is smaller
than the critical ratio $\alpha_d$ above which solutions are clustered and
highly correlated. In addition we show that the clustering ratio can be reached
when the number k of variables per constraints goes to infinity by the
so-called Generalized Unit Clause heuristic.
