Recently spectacular improvements in the performance of SAT solvers have been achieved through nogood recording (clause learning). In the CSP literature, on the other hand, nogood recording remains a fairly minor technique for improving backtracking algorithms. In this paper we demonstrate how recent nogood recording techniques from SAT can be generalized to CSPs. The result is a significant enhancement over current nogood recording techniques used in CSPs. We also report on some preliminary empirical results which indicate that generalized nogood recording can have a significant performance benefit.
展开▼
