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 variable selection, value ordering, as well as domain pruning to subclasses such as FlexibleBacktrackingSolver. Different heuristics from CspHeuristics and InferenceStrategys from package aima.core.search.csp.solver.inference can be plugged in using the corresponding set methods (setAll() should select the best combination for most problems).
The CSP package provides some more solver implementations: BackjumpingBacktrackingSolver, TreeCspSolver, and MinConflictsSolver (often fast, but incomplete).
To use the package for solving a practical CSP, first the necessary constraint types must be implemented (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).