This paper presents an object oriented design for a general purpose binary constraint solver. The implementation of QDOOCS was done in C++. QDOOCS consists of abstract data types for representing binary constraints and constraint networks. We implemented an easy to extend class library that features safe constraint and constraint network access and manipulation as well as code reuse. QDOOCS has methods for preprocessing constraint networks to achieve node, arc or path consistency. It has complete search methods such as chronological backtracking, backjumping, backmarking, forward checking, graph based backjumping and hybrid methods. The design has proven to be easily extendable if one wishes to add another search method or generate another binary constraint satisfaction problem. The performance of QDOOCS is reasonable for problems up to 30 variables, but has shown to be inferior to a pure C version [vanBeek92]. This is mainly due to features like safe array access, code reuse (which induces function call overhead) and the slower execution of C++ code.
Constraint based reasoning, Search, Object Oriented Design