Jilin University ,Changchun, Jilin Province, China.

---

Abstract—Heuristic is an important subject in the field of constraint satisfaction problem(CSP). In the study, we found a kind of variables named singleton-domain variables have a great influence on the solution process. Based on this, we propose a heuristic method named dom/wsdeg and the corresponding calculating method and combine the method with a constraint network compression technology proposed in this paper. The results have shown that the new heuristics are more efficient than the classical heuristics.

Index Terms—Constraint satisfaction problem, compression method, singleton-domain variable, variable ordering heuristic.

[PDF]

Cite: Yi Jun Liu, "Guiding Search by Singleton-Domain Variables for Constraint Satisfaction Problem," Journal of Software vol. 11, no. 9, pp. 903-911, 2016.