Constraint Programming - Domains

Domains

The constraints used in constraint programming are typically over some specific domains. Some popular domains for constraint programming are:

• boolean domains, where only true/false constraints apply (SAT problem)
• integer domains, rational domains
• linear domains, where only linear functions are described and analyzed (although approaches to non-linear problems do exist)
• finite domains, where constraints are defined over finite sets
• mixed domains, involving two or more of the above

Finite domains is one of the most successful domains of constraint programming. In some areas (like operations research) constraint programming is often identified with constraint programming over finite domains.

All of the above examples are commonly solved by satisfiability modulo theories (SMT) solvers.

Finite domain solvers are useful for solving constraint satisfaction problems, and are often based on arc consistency or one of its approximations.

The syntax for expressing constraints over finite domains depends on the host language. The following is a Prolog program that solves the classical alphametic puzzle SEND+MORE=MONEY in constraint logic programming:

% This code works in both YAP and SWI-Prolog using the environment-supplied % CLPFD constraint solver library. It may require minor modifications to work % in other Prolog environments or using other constraint solvers. :- use_module(library(clpfd)). sendmore(Digits) :- Digits =, % Create variables Digits ins 0..9, % Associate domains to variables S #\= 0, % Constraint: S must be different from 0 M #\= 0, all_different(Digits), % all the elements must take different values 1000*S + 100*E + 10*N + D % Other constraints + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y, label(Digits). % Start the search

The interpreter creates a variable for each letter in the puzzle. The operator ins is used to specify the domains of these variables, so that they range over the set of values {0,1,2,3, ..., 9}. The constraints S#\=0 and M#\=0 means that these two variables cannot take the value zero. When the interpreter evaluates these constraints, it reduces the domains of these two variables by removing the value 0 from them. Then, the constraint all_different(Digits) is considered; it does not reduce any domain, so it is simply stored. The last constraint specifies that the digits assigned to the letters must be such that "SEND+MORE=MONEY" holds when each letter is replaced by its corresponding digit. From this constraint, the solver infers that M=1. All stored constraints involving variable M are awakened: in this case, constraint propagation on the all_different constraint removes value 1 from the domain of all the remaining variables. Constraint propagation may solve the problem by reducing all domains to a single value, it may prove that the problem has no solution by reducing a domain to the empty set, but may also terminate without proving satisfiability or unsatisfiability. The label literals are used to actually perform search for a solution.