Constraint-based problem solving is a technique for solving hard combinatorial problems that can be stated as variables ranging over a finite domain of non-negative integers, or sets thereof. Problems in this class range from puzzles to real world applications as diverse as scheduling, ware house allocation, configuration and placement.
The two basic techniques of constraint programming are constraint propagation and constraint distribution. Constraint propagation is an efficient inference mechanism obtained with concurrent propagators accumulating information in a constraint store. Constraint distribution splits a problem into complementary cases once constraint propagation cannot advance further. By iterating propagation and distribution, propagation will eventually determine the solutions of a problem.
Constraint distribution can easily lead to an exponential growth of the number of subproblems to be considered. Fortunately, this potential combinatorial explosion can often be contained by combining strong propagation mechanisms with problem specific heuristics for selecting distribution steps.
The Alice constraint programming features are inherited directly from Mozart. We refer to its Finite Domain Programming and Finite Set Programming tutorials for a thorough introduction.
The following classic puzzle gives a first idea of the combinatorial problems constraint programming can solve.
The Send More Money problem consists in finding distinct digits for the letters S, E, N, D, M, O, R, Y such that S and M are different from zero (no leading zeros) and the equation
SEND + MORE = MONEY
is satisfied. The unique solution of the problem is 9567 + 1085 = 10652.
Alice provides most of the constraint functionality available in Mozart, but in a typeful way. For linear finite domain constraints there is a convenient library abstraction that allows for easy constraint construction and leaves the decision of choosing the best constraint to the system.
The constraint programming functionality of Alice is provided through a library interface, containing the following components:
Finite domains constraints describe the set of values a non-negative integer variable may take.
As an example of finite domain constraint solving, consider the SEND + MORE = MONEY problem. It may be solved in Alice by the following program:
fun money () = let val V as #[S,E,N,D,M,O,R,Y] = vec(8, [0`#9]) in distinct V; post (S `<> `0); post (M `<> `0); post ( `1000`*S `+ `100`*E `+ `10`*N `+ D `+ `1000`*M `+ `100`*O `+ `10`*R `+ E `= `10000`*M `+ `1000`*O `+ `100`*N `+ `10`*E `+ Y ); distribute (FD.FIRSTFAIL, V); {S,E,N,D,M,O,R,Y} end
Constraint problems have to be formulated as a script, a nullary function posting the necessary constraints to the constraint store. The script makes use of the Linear component to formulate the constraints conveniently. See the description of the FD and Linear structures for a detailed description of the meaning of the above constraints.
Once written, the script can be passed to different search engines. For example, we can search for all possible solutions, using the Search structure:
inspect (Search.searchAll money)
Or we can search for the first solution, using the interactive Explorer:
Explorer.exploreOne money
To learn more about constraint programming with Mozart, we refer to the Mozart tutorial.
Finite set constraints describe the possible elements that can be contained in the set denoted by a set variable.
Alice supports the full range of finite set constraints, as available in Mozart tutorial.
Like Mozart, Alice supports the unique concept of first-class computation spaces that can be used to program inference engines for problem solving. See the Space component for details.