Content deleted Content added
No edit summary |
No edit summary |
||
Line 29:
*[http://www.sics.se/isl/sicstuswww/site/index.html SICStus] ([[Prolog]] based)
*[http://www.koalog.com/ Koalog Constraint Solver] ([[Java programming language|Java]] based)
==Finite Domain==
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.
Finite ___domain solvers are useful for solving [[Constraint satisfaction problem|Constraint satisfaction problems]], and are often based on Arc-Consistency (see [[AC-3 algorithm]]), or one of its approximations.
The syntax of CP(FD) languages depends on the host language. The following is a program that solves the puzzle SEND+MORE=MONEY in CLP (i.e., Constraint Programming based on a logic language):
sendmore(Digits) :-
Digits = [S,E,N,D,M,O,R,Y], % Create variables
Digits '''::''' [0..9], % Associate domains to variables
S '''#\=''' 0, % Constraint: S must be different from 0
M '''#\=''' 0,
'''alldifferent'''(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,
'''labeling'''(Digits). % Start the search
The constraint solver creates the variables, and the domains, so all the variables range over the set of values {0,1,2,3, ..., 9}. S#\=0 (which means <math>S \neq 0</math>) is imposed, and value 0 is removed from the ___domain of variable S. Same for variable M. Then, the constraint alldifferent(Digits) is imposed: it cannot propagate any deletion, so it simply suspends. Then the last constraint is imposed. From the last constraint, the solver infers that M=1. All the constraints involving variable M are awaken: in particular alldifferent can remove value 1 from the ___domain of all the remaining variables
==References==
| |||