Constraints: Representation and Solving

The idea underlying in Constraint Programming is that constraints can be used to represent a problem, to solve it, and to represent a solution--which, in fact, is no more than a simplification of the initial constraints, arrived at by following deduction rules hardwired in the solver.^1.1

We will give an example of how a problem can be represented by using constraints: let us think of a puzzle such as those commonly found in magazines:

The murderer is older than Joe

The man in yellow does not have green eyes

This puzzle can be viewed as constraints expressed in a language which has some primitive constraints (such as ``is older than''), which relate elements pertaining to the domain of the constraint system (such as the actors and their characteristics: ``the man in yellow'', ``Joe'', ``green eyes''). Some of the actors are definitely identified (``Joe''), and some others are represented by an identifier, or a characteristic which does not allow its identification them (yet): ``the murderer''.

A solution is an assignment of domain values to those actors not completely identified which agrees with all the initial constraints:

Murderer: López, green eyes, Magnum gun

Sometimes a single solution cannot be reached. This can be due to the way in which the solver works (incomplete solver), or due to a lack of initial constraints which define completely the problem (underconstrained problem--probably not correctly modeled) or just because there are many different solutions for that particular problem. In that case the initial constraint system cannot be completely reduced, and the final answer is a constraint itself, such as:

The murderer is older than the man in yellow

Note that it is often possible to perform an enumeration (search) through all the individuals in our initial problem to check which ones meet this final constraint. This path could have been followed right from the beginning (try all the combinations of possible actors and domain values, and check which ones meet all the constraints), but a (partial) solving of the constraints can sometimes solve the problem, and, in any case, the number of equations and domain values to try is greatly reduced.