<!--
  - Authors:
  -   Christian Schulte <schulte@ps.uni-sb.de>
  -   Gert Smolka <smolka@dfki.de>
  -   Jörg Würtz
  -
  - Contributors:
  -   Daniel Simon <dansim@ps.uni-sb.de>
  -   Andy Walter <anwalt@ps.uni-sb.de>
  -   
  - Copyright:
  -   Christian Schulte, 1998
  -   Gert Smolka, 1998
  -   Jörg Würtz, 1997
  -
  - Last change:
  -   $Date: 1999-08-12 11:45:40 +0200 (Thu, 12 Aug 1999) $ by $Author: duchier $
  -   $Revision: 11784 $
  -
  - This file is part of Mozart, an implementation
  - of Oz 3
  -    http://www.mozart-oz.org
  -
  - See the file "LICENSE" or
  -    http://www.mozart-oz.org/LICENSE.html
  - for information on usage and redistribution
  - of this file, and for a DISCLAIMER OF ALL
  - WARRANTIES.
  -
  -->

<chapter id=chapter.scripts><title/Parameterized Scripts/

<P>
Combinatorial problems typically occur in a
general form that can be instantiated with
different data sets.  This leads to parameterized
scripts separating the general script from
particular data sets.


<section id="section.scripts.queens">
  <title/Example: Queens/


<subsection class=unnumbered>
  <title/Problem Specification/

<p>

Place <Math/N/ queens on an <math/N\times N/ chess board
such that no two queens attack each other.  The
parameter of the problem is <Math/N/.  A solution for
the 8-queens problem looks as follows:

<figure class="Figure">
<table>
  <tr/<th/<p.silent/&nbsp;// <th/1/<th/2/<th/3/<th/4/<th/5/<th/6/<th/7/<th/8//
  <tr><th/1/ <td><picture.extern id="pic.q1" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td></tr>
  <tr><th/2/
  <td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><picture.extern
  id="pic.q2" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td></tr>
  <tr><th/3/
  <td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><picture.extern
  id="pic.q3" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td></tr>
  <tr><th/4/
  <td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><picture.extern
  id="pic.q4" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td></tr>
  <tr><th/5/
  <td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><picture.extern
  id="pic.q5" to="queen.gif" type=gif></td></tr>
  <tr><th/6/ <td><p.silent/&nbsp;/</td><td><picture.extern id="pic.q6" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td></tr>
  <tr><th/7/
  <td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><picture.extern
  id="pic.q7" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td></tr>
  <tr><th/8/
  <td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><picture.extern
  id="pic.q8" to="queen.gif" type=gif></td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td><td><p.silent/&nbsp;/</td></tr>
</table>
</figure>

<subsection class=unnumbered>
  <title/Model/

<p>
We will use a clever model avoiding possible
symmetries and minimizing the number of
propagators.

<p>
We assume that the queens are numbered from 1
to <math/N/, and that the <math/k/-th queen is always placed
in the <math/k/-th column.  For every queen <math/i/ we have
one variable <math/R_i/ saying in which row the queen
is placed.  The model guarantees by construction
that two queens are never placed in the same
column.  To ensure that two queens are never in
the same row, we impose the constraint that the
variables <math/R_1,\ldots,R_N/ are pairwise distinct.

<p>
To enforce that two queens are never in the same
diagonal, we need to impose the constraints
<math display/
R_i+(j-i)\neq R_j
\qquad
\hbox{and}
\qquad
R_i-(j-i)\neq R_j
/
for all <math/i/, <math/j/ such that <math/1\le i<j\le N/.
Equivalently, we can impose the constraints
<math display/
R_i-i\neq R_j-j
\qquad
\hbox{and}
\qquad
R_i+i\neq R_j+j
/
for all <math/i/, <math/j/ such that <math/1\le i<j\le N/.  This is
equivalent to saying that the sequences
<math display/
R_1-1\;,\ldots,\;R_N-N
\qquad
\hbox{and}
\qquad
R_1+1\;,\ldots,\;R_N+N
/
are both nonrepetitive.  Since Oz has a special
propagator for the constraint stating the
nonrepetitiveness of such sequences, this
formulation requires only two propagators, one for
each sequence.

<subsection class=unnumbered>
  <title/Distribution Strategy/

<p>
We distribute on the variables <math/R_1,\ldots,R_N/ using a
first-fail strategy that tries the value in the
middle of the domain of the selected variable
first.  This strategy works well even for
large ?{N}.

<p>
<figure id="ProgQueens">
<caption>A script for the ?{N}-queens Problem.</caption>
<chunk class=anonymous><title/Queens/
fun {Queens N}
   proc {$ Row}
      L1N ={MakeTuple c N} 
      LM1N={MakeTuple c N}
   in
      {FD.tuple queens N 1#N Row}
      {For 1 N 1 proc {$ I}
                    L1N.I=I LM1N.I=~I
                 end}
      {FD.distinct Row}
      {FD.distinctOffset Row LM1N}
      {FD.distinctOffset Row L1N}
      {FD.distribute generic(value:mid) Row}
   end
end
</chunk>
</figure>

<subsection class=unnumbered>
  <title/Script/

<p>
<Ptr to="ProgQueens"> shows a parameterized
script for the ?{N}-Queens Problem.  The actual
script is created by the procedure <<Queens>>,
which takes <<N>> as parameter.  The script
constrains its root variable <<Row>> to a tuple
having a component for every queen.  This
implicitly creates the variables <math/R_1,\ldots,R_N/ of the
model.

<p>
The statements
<<<
{FD.distinct Row}
{FD.distinctOffset Row LM1N}
{FD.distinctOffset Row L1N}
>>>
create propagators for the constraints stating
that the sequences
<table>
<tr> <td><<Row.1>></td> <td/<p.silent/&ellipsis;// <td><<Row.N>></td></tr>
<tr> <td><<Row.1-1>></td> <td/<p.silent/&ellipsis;// <td><<Row.N-N>></td></tr>
<tr> <td><<Row.1+1>></td> <td/<p.silent/&ellipsis;// <td><<Row.N+N>></td></tr>
</table>
be non repetitive. 


</section>

<section id="section.scripts.change">
  <title/Example: Changing Money/

<subsection class=unnumbered>
  <title/Problem Specification/


<p>
Given bills and coins of different denominations
and an amount <math/A/, select a minimal number of
bill and coins to pay <math/A/.  One instance of the
problem assumes that we want to pay the amount of
<math/1.42/, and that we have 6 one dollar bills, 8
quarters (25 cents) , 10 dimes (10 cents), 1
nickel (5 cents), and 5 pennies (1 cent).

<subsection class=unnumbered>
  <title/Model/

<p>
To avoid conversions, we assume that the amount
to be paid and all denominations are specified in
the same currency unit (e.g., cents).  The data
is specified by variables <math/a_1,\ldots,a_k/
specifying the available denominations <math/d_i/ and
the number <math/a_i/ of available respective coins or
bills.

<p>
The model has a variable <math/C_i/ for ever available
denomination saying how many of the corresponding
bills or coins we will use to pay the amount.
For all ?{i}, we must have
<math/
0\le C_i\le a_i
/
Moreover, we must satisfy the constraint
<math display/
d_1\cdot C_1 + d_2\cdot C_2 + \cdots + d_k\cdot
C_k
\;=\;
\mbox{\it amount}
/

<subsection class=unnumbered>
  <title/Distribution Strategy/

<p>
We distribute on the variables <math/C_1,C_2,\ldots/,
where we give precedence to larger denominations
and, with second priority, to larger values.

<figure id="ProgChange">
<caption/A script for changing money together with a data specification./
<chunk class=anonymous><title/ChangeMoney/
fun {ChangeMoney BillsAndCoins Amount}
   Available    = {Record.map BillsAndCoins fun {$ A#_} A end}
   Denomination = {Record.map BillsAndCoins fun {$ _#D} D end}
   NbDenoms     = {Width Denomination}
in
   proc {$ Change}
      {FD.tuple change NbDenoms 0#Amount Change}
      {For 1 NbDenoms 1 proc {$ I} Change.I =<: Available.I end}
      {FD.sumC Denomination Change '=:' Amount}
      {FD.distribute generic(order:naive value:max) Change}
   end
end

BillsAndCoins = bac(6#100  8#25  10#10  1#5  5#1)
</chunk>
</figure>

<subsection class=unnumbered>
  <title/Script/

<p>
The procedure <<ChangeMoney>> in
<Ptr to="ProgChange"> takes two parameters
specifying the available bills and coins and the
amount to be paid.  It returns a script that
enumerates the possible ways to pay the specified
amount with the specified bills and coins.  It is
assumed that the bills and coins are specified in
denomination decreasing order.
<p>
The statement
<chunk class=anonymous><title/{SearchOne ChangeMoney}/
{Browse {SearchOne {ChangeMoney BillsAndCoins 142}}}
</chunk>
computes the list
<<<
[change(1 1 1 1 2)]
>>>
saying that we can pay $1.42 with 1 one dollar
bill, 1 quarter, 1 dime, 1 nickel, and 2 pennies.
This payment uses the minimal number of bills and
coins.  The number of different possibilities to
pay $1.42 with the specified stock of bills and
coins is 6 and can be computed with the statement
<chunk class=anonymous><title/{SearchAll ChangeMoney}/
{Browse {Length {SearchAll {ChangeMoney BillsAndCoins 142}}}}
</chunk>
</section>

<![ %EXTRA; [
<section><title/NONE/
<p>
<chunk><title/EXAMPLES/
%%%
%%% Chapter: Parameterized Scripts
%%%

%%
%% Example: Queens
%%

declare
<chunk.ref/Queens/

{ExploreOne {Queens 8}}

{ExploreAll {Queens 6}}



%%
%% Example: Changing Money
%%

declare
<chunk.ref/ChangeMoney/

{ExploreOne {ChangeMoney BillsAndCoins 142}}


<chunk.ref/{SearchOne ChangeMoney}/

<chunk.ref/{SearchAll ChangeMoney}/



</chunk>
]]>


</chapter>


