The phenomenon of phase transition in constraint satisfaction problems (CSPs) plays a crucial role in the field of artificial intelligence and computational complexity theory. In this paper, we propose a new random CSP called
d-p-RB model, which is a generalization of
RB model on domain size
d and constraint tightness
p. In this model, the variable domain size
d Ε [ nα, nny], and all constraints are uniformly divided into several groups with different constraint tightness
p. It is proved by the second moment method that the
d-p-RB model undergoes phase transition from a region where almost all instances are satisfiable to a region where almost all instances are unsatisfiable as the control parameter increases. Moreover, the threshold value at which the phase transition occurs is located exactly.