  In this paper we propose a random CSP model, called Model GB, which is a
natural generalization of standard Model B. It is proved that Model GB in which
each constraint is easy to satisfy exhibits non-trivial behaviour (not
trivially satisfiable or unsatisfiable) as the number of variables approaches
infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1))
of the average number of nodes in a search tree used by the backtracking
algorithm on Model GB is also presented. It is shown that the average number of
nodes required for finding all solutions or proving that no solution exists
grows exponentially with the number of variables. So this model might be an
interesting distribution for studying the nature of hard instances and
evaluating the performance of CSP algorithms. In addition, we further
investigate the behaviour of the average number of nodes as r (the ratio of
constraints to variables) varies. The results indicate that as r increases,
random CSP instances get easier and easier to solve, and the base for the
average number of nodes that is exponential in r tends to 1 as r approaches
infinity. Therefore, although the average number of nodes used by the
backtracking algorithm on random CSP is exponential, many CSP instances will be
very easy to solve when r is sufficiently large.
