AIMA3e CSP Package
A Constraint Satisfaction Problem (CSP) consists of Variables, corresponding Domains, and Constraints imposing restrictions to legal combinations of values. A solution is an Assignment, which satisfies all constraints.
The following UML class diagram gives an overview of the AIMA3e CSP implementation:
Most classes and interfaces are generic. They use type parameters for the types to represent variables
VAR and values VAL. VAR must be bound to a subclass of Variable to make sure that all variables have a name.
CspSolver defines an interface for different kinds of CSP solvers and also provides some basic infrastructure for progress tracking. AbstractBacktrackingSolver provides an implementation of the backtracking algorithm as template method. It delegates implementations of heuristics for variable selection, value ordering as well as domain pruning to subclasses such as FlexibleBacktrackingSolver. MinConflictsSolver is a second solver implementation which is based on local search (often fast, but incomplete).
To use the package for solving a practical CSP, first the necessary constraint typs must be implementet (see e.g. NotEqualConstraint). Then, a CSP must be defined by instantiating or subclassing the CSP class (see e.g. MapCSP). Finally, a solver must be configured and applied to the CSP (see e.g. MapColoringCspDemo).