#title Constraint Programming

<contents depth="2">

* About this document

This file was automatically generated from the interactive Strasheela tutorial. Some aspects of the text only make sense in the original interactive tutorial application (e.g., buttons indicated to press, and positions specified on the screen), and not in this version of the text.

* -- Constraint Programming

The following examples introduce the basics of constraint programming in Oz.
  



* Constrained Variables

The two variables X and Y are declared to integers with a specific domain of allowed values (finite domain, FD). X is explicitly declared to an integer in {0, ..., 10}. Y is declared to any integer supported by Oz (so you see the maximum domain supported by Oz).

Please note that a finite domain consists always of integers in Oz (for efficiency reasons), and that FD integers can not be negative. There are also other domains supported (e.g. sets of finite integers, and real numbers). 




<src lang="oz">
local 
  X = {FD.int 0#10}
  Y = {FD.decl}
in
  {Browse [X Y]}
end
</src>

* Constraint Propagation

This example declares two finite domain integers as the example before. In addition, it states that X is greater than Y. The domain of both variables are automatically reduced, so that all domain values fulfill the greater-than constraint. 

However, no specific solution is shown. The next example shows how to search for solutions of a constraint satisfaction problem (CSP) in Oz.  



<src lang="oz">
local 
  X = {FD.int 0#10}
  Y = {FD.decl}
in
  X >: Y
  {Browse [X Y]}
end
</src>

* A Simple Script

This example shows the first full constraint satisfaction problem (CSP) definition. A constraint solver (here SearchAll) expects a CSP in form of a script. A script is a procedure (here an anonymous procedure) whose only argument is the solution of the solved CSP. The variable is often called the root variable of the script. Transformed into common mathematical notation, the CSP states the following conjunction

  X + Y = Z  AND  X < Y

The script defines the three variables X, Y, and Z with a shortcut. Within many Oz constructs (e.g. procedure definitions), there exists a shorthand for declaring local variables where we only need to write the 'in' like 

  proc {Name <args>} X=bla in <my code> end

The script simply collects the three variables X, Y, and Z in a record stored in the root variable Solution. The solver SearchAll returns a list with all solutions of the CSP defined by the script. Note the use of the special constraint operators <code><:</code> and <code>=:</code> instead of <code><</code> and <code>=</code>. 

The last line of the script shows a very characteristic Oz feature: an Oz script explicitly defines a search strategy (or, more specifically the distribution strategy). The procedure FD.distribute expects a specification of a distribution strategy and a record or list of the constrained variables. 

The distribution strategy specifies in which order variables are visited during the search process. The specification 'ff' stands for first-fail and means that always a variable with smallest domain is visited next. The selection of a suitable distribution strategy is vital for the performance of the search process. Nevertheless, for keeping things simple this tutorial does not discuss constraint distribution in detail. Please refer to the Oz documentation for more information (e.g. the "Finite Domain Constraint Programming Tutorial" at http://www.mozart-oz.org/documentation/fdt/index.html). 



<src lang="oz">
{Browse 
 {SearchAll
  proc {$ Solution}
     X = {FD.int 1#10}
     Y = {FD.int 1#10}
     Z = {FD.int 1#10}
  in
     Solution = unit(x:X y:Y z:Z)
     X + Y =: Z
     X <: Y
     %% search strategy
     {FD.distribute ff Solution}
  end}}
</src>

* Parameterised Script

This example defines a script which expects an argument -- a parameterised script. IncreasingInts expects an integer L and returns the actual script (an anonymous procedure). This script creates a list of L finite domain integers (using FD.list). It then constrains all integers in this list to be pairwise distinct (using the constraint FD.distinct). In addition, it constrains the sum of all integers to be equal the square of L (using FD.sum). 

This example uses another constraint solver, the Oz Explorer. The Explorer visualises the search space. Green nodes in the tree denote solutions, red nodes represent a fail, blue nodes show a stage in the search where there are still open decisions. Triangles represent a subtree (use the middle mouse button to show the nodes of the subtree).

Just double-click on a node to see the values of the variables at this stage during the search process (you can not look at failed nodes, though). You can use this facility to get some intuitive understanding of the search process. For example, look first at the variable values in the root node, than in a child node of the root and in a grand-child node and so forth, to monitor how the search process shrinks the variable domains. For understanding this process please read the "Finite Domain Constraint Programming Tutorial".

You may play around with the menu entries of the Oz Explorer. For example, select the top node with the mouse, then go to the 'Search' menu and select 'Next Solution'.

You may also edit the CSP definition. For example, change the value for L in the IncreasingInts call to another integer.




<src lang="oz">
local
   fun {IncreasingInts L}
      proc {$ Sol}
	 %% create a list of L FD integers with domain {0, ..., L*2}
	 Sol = {FD.list L 0#L*2}
         {FD.distinct Sol}
         {FD.sum Sol '=:' L*L}
	 %% search strategy
	 {FD.distribute ff Sol}
      end
   end
in
   {ExploreOne {IncreasingInts 7}}
end
</src>