Constraint satisfaction has received increasing attention over the years. Intense research has focused on solving all kinds of constraint satisfaction problems (CSPs). In this paper, first we propose a random CSP model, named k-CSP, that guarantees the existence of phase transitions under certain circumstances. The exact location of the phase transition is quantified and experimental results are provided to illustrate the performance of the proposed model. Second, we revise the model k-CSP to a random linear CSP by incorporating certain linear ...
