1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 1996 - 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Micha Meier, ECRC 20% 21% END LICENSE BLOCK 22% 23% W% 96/01/08 24% 25% Author: Micha Meier 26% 27 28\addtocounter{secnumdepth}{2} 29\chapter{The Finite Domains Library} 30\label{chapdomains} 31\index{library!fd.pl|(} 32 33The library {\bf fd.pl} 34implements constraints over finite domains that can contain 35integer as well as atomic (i.e.\ atoms, strings, floats, etc.) 36and ground compound (e.g.\ {\it f(a, b)}) 37elements. 38Modules that use the library must start with the directive 39\begin{quote} 40{\bf :- use_module(library(fd)).} 41\end{quote} 42 43\section{Terminology} 44Some of the terms frequently used in this chapter are explained below. 45\begin{description} 46\item[domain variable] 47\index{domain variable!definition} 48A domain variable is a variable which can be instantiated only 49to a value from a given finite set. 50Unification with a term outside of this domain fails. 51The domain can be associated with the variable using the predicate 52\biptxtref{::/2}{fd:(::)/2}{../bips/lib/fd/NN-2.html}. 53Built-in predicates that expect domain variables 54treat atomic and other ground terms as variables with singleton domains. 55 56\item[integer domain variable] 57\index{domain variable!integer} 58An integer domain variable is a domain variable 59whose domain contains only integer numbers. 60Only such variables are accepted in inequality constraints 61and in rational terms. 62Note that a non-integer domain variable can become 63an integer domain variable when the non-integer values 64are removed from its domain. 65 66\item[integer interval] 67An integer interval is written as 68\begin{center} 69{\it Min .. Max} 70\end{center} 71with integer expressions 72{\it $Min \leq Max$} 73and it represents 74the set 75\begin{center} 76\{Min, Min + 1, \ldots, Max\}. 77\end{center} 78 79\item[linear term] 80A linear term is a linear integer combination of integer domain variables. 81The constraint predicates accept linear terms even in a non-canonical form, 82containing functors +, - and *, 83e.g.\ 84\begin{center} 85$5*(3+(4-6)*Y-X*3)$. 86\end{center} 87If the constraint predicates encounter 88a variable without a domain, they 89give it a default domain -10000000..10000000. 90\index{domain!default} 91Note that arithmetic operations on linear terms are performed 92with standard machine word integers without any overflow checks. 93If the domain ranges or coefficients are too large, 94the operation will not yield correct results. 95Both the maximum and minimum value of a linear term must 96be representable in a machine word, and so must 97the maximum and minimum value of every 98\begin{latexonly} 99\enableunderscores 100${\it c_i x_i}$ 101\disableunderscores 102\end{latexonly} 103\begin{htmlonly} 104${\it c_i x_i}$ 105\end{htmlonly} 106term. 107 108\item[rational term] 109A rational term is a term constructed from integers and integer 110domain variables using the arithmetic operations 111${\bf +, -, *, /}$. 112Besides that, every subexpression of the form {\it VarA/VarB} must have 113an integer value in the solution. 114The system replaces such a subexpression by a new variable {\it X} 115and adds a new constraint {\it VarA \#= VarB * X}. 116Similarly, all subexpressions of the form {\it VarA*VarB} 117are replaced by a new variable {\it X} 118and a new constraint {\it X \#= VarA * VarB} is added, 119so that in the internal representation, the term is converted 120to a linear term. 121 122\item[constraint expression] 123A constraint expression is either an arithmetic constraint 124or a combination of constraint expressions using the 125logical FD connectives 126{\bf \#\andsy/2, \#\orsy/2, \#=\gt/2, \#\lt=\gt/2, \#\bsl+/1}. 127%\begin{latexonly} 128%${\bf \#/\backslash/2, \#\backslash//2, 129%\#=>/2, \#<=>/2, \#\backslash+/1}$. 130%\end{latexonly} 131%\html{ 132%{\bf #/\verb+\+/2, #\verb+\/+/2, 133%#=>/2, #<=>/2, #\verb+\++/1}. 134%} 135%{\bf \#/\verb+\+/2, \#\verb+\/+/2, 136%\#=>/2, \#<=>/2, \#\verb+\++/1}. 137\end{description} 138 139%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 140\section{Constraint Predicates} 141\begin{description} 142\item[] \biptxtref{?Vars :: ?Domain}{fd:(::)/2}{../bips/lib/fd/NN-2.html}\ \\ 143\index{::/2!fd} 144\index{domain variable!creation} 145{\it Vars} is a variable or a list of variables 146with the associated domain {\it Domain}. 147{\it Domain} can be a closed integer interval denoted as {\it Min .. Max}, 148or a list of intervals and/or atomic or ground elements. 149Although the domain can contain any compound terms that contain 150no variable, 151the functor {\it ../2} is reserved to denote integer intervals 152and thus {\it 1..10} always means an interval and {\it a..b} 153is not accepted as a compound domain element. 154 155If {\it Vars} is already a domain variable, its domain will be updated 156according to the new domain; if it is instantiated, the predicate checks 157if the value lies in the domain. 158Otherwise, if {\it Vars} is a free variable, it is converted to a domain 159variable. 160If {\it Vars} is a domain variable and {\it Domain} is free, 161it is bound to the list of elements and integer intervals 162representing the domain of the variable 163(see also \bipref{dvar_domain/2}{../bips/lib/fd/dvar_domain-2.html} which returns the actual domain). 164 165When a free variable obtains a finite domain or when the domain 166of a domain variable is updated, the {\bf constrained} 167list of its {\bf suspend} attribute is woken, if it has one. 168\index{suspension list!constrained} 169 170\item[] \biptxtref{integers(+Vars)}{fd:integers/1}{../bips/lib/fd/integers-1.html}\ \\ 171\index{integers/1!fd} 172This constrains the list of variables Vars to have integer domains. Any 173non-domain variables in Vars will be given the default integer domain. 174 175\item[] \biptxtref{::(?Var, ?Domain, ?B)}{fd:(::)/3}{../bips/lib/fd/NN-3.html}\ \\ 176\index{::/3!fd} 177{\it B} is equal to 1 iff the domain of the finite domain variable {\it Var} 178is a subset of {\it Domain} and 0 otherwise. 179 180\item[] \biptxtref{atmost(+Number, ?List, +Val)}{fd:atmost/3}{../bips/lib/fd/atmost-3.html}\ \\ 181\index{atmost/3} 182At most {\it Number} elements of the list {\it List} of domain variables 183and ground terms are equal to the ground value {\it Val}. 184 185\item[] \biptxtref{constraints_number(+DVar, -Number)}{constraints_number/2}{../bips/lib/fd/constraints_number-2.html}\ \\ 186\index{constraints_number/2} 187{\it Number} is the number of constraints and suspended goals 188currently attached to the variable {\it DVar}. 189Note that this number may not correspond to the exact number 190of {\it different} constraints attached to {\it DVar}, as goals 191in different suspending lists are counted separately. 192This predicate is often used when looking for the most or least constrained 193variable from a set of domain variables (see also \bipref{deleteffc/3}{../bips/lib/fd/deleteffc-3.html}). 194 195\item[] \biptxtref{element(?Index, +List, ?Value)}{fd:element/3}{../bips/lib/fd/element-3.html}\ \\ 196\index{element/3} 197The {\it Index}'th element of the ground list {\it List} 198is equal to {\it Value}. 199{\it Index} and {\it Value} can be either plain variables, 200in which case a domain will be associated to them, or domain variables. 201Whenever the domain of {\it Index} or {\it Value} is updated, 202the predicate is woken and the domains are updated accordingly. 203 204\item[] \biptxtref{fd\_eval(+E)}{fd:fd_eval/1}{../bips/lib/fd/fd_eval-1.html}\ \\ 205\index{fd\_eval/1} 206The constraint expression {\it E} is evaluated on runtime 207and no compile-time processing is performed. 208This might be necessary in the situations where the 209default compile-time transformation of the given expression 210is not suitable, e.g.\ because it would require type or mode information. 211 212\item[] \biptxtref{indomain(+DVar)}{fd:indomain/1}{../bips/lib/fd/indomain-1.html}\ \\ 213\index{indomain/1} 214This predicate instantiates the domain variable {\it DVar} to 215an element of its domain; on backtracking the subsequent values are taken. 216It is used, for example, to find a value of {\it DVar} which is consistent 217with all currently imposed constraints. 218If {\it DVar} is a ground term, it succeeds. 219Otherwise, if it is not a domain variable, an error is raised. 220 221\item[] \biptxtref{is_domain(?Term)}{fd:is_domain/1}{../bips/lib/fd/is_domain-1.html}\ \\ 222\index{is_domain/1} 223Succeeds if {\it Term} is a domain variable. 224 225\item[] \biptxtref{is_integer_domain(?Term)}{fd:is_integer_domain/1}{../bips/lib/fd/is_integer_domain-1.html}\ \\ 226\index{is_integer_domain/1} 227Succeeds if {\it Term} is an integer domain variable. 228 229\item[] \biptxtref{min_max(+Goal, ?C)}{fd:min_max/2}{../bips/lib/fd/min_max-2.html}\ \\ 230\index{min_max/2} 231If {\it C} is a linear term, 232a solution of the goal {\it Goal} is found that minimises the 233value of {\it C}. 234If {\it C} is a list of linear terms, the returned solution 235minimises the maximum value of terms in the list. 236The solution is found using the {\it branch and bound} method; 237as soon as a partial solution is found that is worse than a previously 238found solution, failure is forced and a new solution is searched for. 239When a new better solution is found, the bound is updated and 240the search restarts from the beginning. 241Each time a new better solution is found, the event 280 is raised. 242If a solution does not make {\it C} ground, an error is raised, 243unless exactly one variable in the list {\it C} remains free, 244in which case the system tries to instantiate it to its minimum. 245 246\item[] \biptxtref{minimize(+Goal, ?Term)}{fd:minimize/2}{../bips/lib/fd/minimize-2.html}\ \\ 247\index{minimize/2!fd} 248Similar to \bipref{min_max/2}{../bips/lib/fd/min_max-2.html}, but {\it Term} must be an integer domain variable. 249When a new better solution is found, the search does not restart 250from the beginning, but a failure is forced and the search continues. 251Each time a new better solution is found, the event 280 is raised. 252Often \bipref{minimize/2}{../bips/lib/fd/minimize-2.html} is faster than \bipref{min_max/2}{../bips/lib/fd/min_max-2.html}, sometimes 253\bipref{min_max/2}{../bips/lib/fd/min_max-2.html} might run faster, but it is difficult to predict 254which one is more appropriate for a given problem. 255 256\item[] \biptxtref{min_max(+Goal, ?Template, ?Solution, ?C)}{fd:min_max/4}{../bips/lib/fd/min_max-4.html} 257\item[] \biptxtref{minimize(+Goal, ?Template, ?Solution, ?Term)}{fd:minimize/4}{../bips/lib/fd/minimize-4.html}\ \\ 258\index{min_max/4} 259\index{minimize/4} 260Similar to \bipref{min_max/2}{../bips/lib/fd/min_max-2.html} 261and \bipref{minimize/2}{../bips/lib/fd/minimize-2.html}, 262but the variables in {\it Goal} do not get 263instantiated to their optimum solutions. Instead, {\it Solutions} will 264be unified with a copy of {\it Template} where the variables are replaced 265with their minimized values. Typically, the template will contain 266all or a subset of {\it Goal}'s variables. 267 268\item[] \biptxtref{min_max(+Goal, ?C, +Low, +High, +Percent)}{fd:min_max/5}{../bips/lib/fd/min_max-5.html} 269\item[] \biptxtref{minimize(+Goal, ?Term, +Low, +High, +Percent)}{fd:minimize/5}{../bips/lib/fd/minimize-5.html}\ \\ 270\index{min_max/5} 271\index{minimize/5} 272Similar to \bipref{min_max/2}{../bips/lib/fd/min_max-2.html} 273and \bipref{minimize/2}{../bips/lib/fd/minimize-2.html}, 274however the branch and bound method 275starts with the assumption that the value to be minimised is less than 276or equal to {\it High}. 277Moreover, as soon as a solution is found 278whose minimised value is less than {\it Low}, this solution is returned. 279Solutions within the range of {\it Percent} \% are considered 280equivalent and so the search for next better solution starts 281with a minimised value {\it Percent} \% less than the previously found one. 282{\it Low}, {\it High} and {\it Percent} must be integers. 283 284\item[] \biptxtref{min_max(+Goal, ?C, +Low, +High, +Percent, +Timeout)}{fd:min_max/6}{../bips/lib/fd/min_max-6.html} 285\item[] \biptxtref{minimize(+Goal, ?Term, +Low, +High, +Percent, +Timeout)}{fd:minimize/6}{../bips/lib/fd/minimize-6.html}\ \\ 286\index{min_max/6} 287\index{minimize/6} 288Similar to \bipref{min_max/5}{../bips/lib/fd/min_max-5.html} 289and \bipref{minimize/5}{../bips/lib/fd/minimize-5.html}, 290but after {\it Timeout} seconds 291the search is aborted and the best solution found so far is 292returned. 293 294\item[] \biptxtref{min_max(+Goal, ?Template, ?Solution, ?C, +Low, +High, +Percent, +Timeout)}{fd:min_max/8}{../bips/lib/fd/min_max-8.html} 295\item[] \biptxtref{minimize(+Goal, ?Template, ?Solution, ?Term, +Low, +High, +Percent, +Timeout)}{fd:minimize/8}{../bips/lib/fd/minimize-8.html}\ \\ 296\index{min_max/8} 297\index{minimize/8} 298The most general variants of the above, with all the optinal parameters. 299 300\end{description} 301 302%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 303\section{Arithmetic Constraint Predicates} 304\begin{description} 305%\latex{ 306%\item[?T1 \#$\backslash$= ?T2] 307%}\html{ 308%\item[?T1 \#\verb+\+= ?T2] 309\item[?T1 \#\bsl= ?T2] 310%} 311\index{\#\bsl=/2} 312The value of the rational term {\it T1} is not equal to the value of the 313rational term {\it T2}. 314 315\item[?T1 \#$<$ ?T2] 316\index{\#$<$/2!fd} 317The value of the rational term {\it T1} is less than the value of the 318rational term {\it T2}. 319 320\item[?T1 \#$<$= ?T2] 321\index{\#$<$=/2!fd} 322The value of the rational term {\it T1} is less than or equal to the value of the 323rational term {\it T2}. 324 325\item[?T1 \#= ?T2] 326\index{\#=/2!fd} 327The value of the rational term {\it T1} is equal to the 328value of the rational term {\it T2}. 329 330\item[?T1 \#$>$ ?T2] 331\index{\#$>$/2!fd} 332The value of the rational term {\it T1} is greater than the 333value of the rational term {\it T2}. 334 335\item[?T1 \#$>$= ?T2] 336\index{\#$>$=/2!fd} 337The value of the rational term {\it T1} is greater than or equal to the 338value of the rational term {\it T2}. 339 340\end{description} 341 342%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 343\section{Logical Constraint Predicates} 344The logical constraints can be used to combine simpler constraints 345and to build complex logical constraint expressions. 346These constraints are preprocessed by the system and transformed 347into a sequence of evaluation constraints and arithmetic constraints. 348The logical operators are declared with the following precedences: 349\begin{quote} 350\begin{verbatim} 351:- op(750, fy, #\+). 352:- op(760, yfx, #/\). 353:- op(770, yfx, #\/). 354:- op(780, yfx, #=>). 355:- op(790, yfx, #<=>). 356\end{verbatim} 357\end{quote} 358 359\begin{description} 360 361%\latex{ 362%\item[\#$\backslash$+ +E1] 363%\index{\#$\backslash$+/1} 364%}\html{ 365\item[\#\bsl+ +E1] 366\index{\#\bsl+/1} 367%} 368{\it E1} is false, i.e.\ the logical negation of the constraint 369expression {\it E1} is imposed. 370 371%\latex{ 372%\item[+E1 \#/$\backslash$ +E2] 373%\index{\#/$\backslash$/2} 374%}\html{ 375\item[+E1 \#\andsy +E2] 376\index{\#\andsy/2} 377%} 378Both constraint expressions {\it E1} and {\it E2} are true. 379This is equivalent to normal conjunction {\it (E1, E2)}. 380 381%\latex{ 382%\item[+E1 \#$\backslash$/ +E2] 383%\index{\#$\backslash$//2} 384%} 385%\html{ 386%\item[+E1 \#\verb+\/+ +E2] 387%\index{\#\verb+\/+/2} 388\item[+E1 \#\orsy +E2] 389\index{\#\orsy/2} 390%} 391At least one of constraint expressions {\it E1} and {\it E2} is true. 392As soon as one of {\it E1} or {\it E2} becomes false, the other constraint 393is imposed. 394 395\item[+E1 \#=$>$ +E2] 396\index{\#=$>$/2} 397The constraint expression {\it E1} implies the 398constraint expression {\it E2}. 399If {\it E1} becomes true, then {\it E2} is imposed. 400If {\it E2} becomes false, then the negation of {\it E1} 401will be imposed. 402 403\item[+E1 \#$<$=$>$ +E2] 404\index{\#$<$=$>$/2} 405The constraint expression {\it E1} is equivalent to the 406constraint expression {\it E2}. 407If one expression becomes true, the other one will be imposed. 408If one expression becomes false, the negation of the other one will be imposed. 409\end{description} 410 411%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 412\section{Evaluation Constraint Predicates} 413These constraint predicates evaluate the given constraint expression 414and associate its truth value with a boolean variable. 415They can be very useful for defining more complex constraints. 416They can be used both to test entailment of a constraint 417and to impose a constraint or its negation on the current constraint store. 418 419\begin{description} 420\item[?B isd +Expr] 421\index{isd/2} 422{\it B} is equal to 1 iff 423the constraint expression {\it Expr} is true, 0 otherwise. 424This predicate is the constraint counterpart of \bipref{is/2}{../bips/kernel/arithmetic/is-2.html} --- 425it takes a constraint expression, transforms all its subexpressions 426into calls to predicates with arity one higher and combines 427the resulting boolean values to yield {\it B}. 428For instance, 429\begin{quote} 430{\bf B isd X \#= Y} 431\end{quote} 432is equivalent to 433\begin{quote} 434{\bf \#=(X, Y, B)} 435\end{quote} 436 437\item[\#$<$(?T1, ?T2, ?B)] 438\index{\#$<$/3!fd} 439{\it B} is equal to 1 iff 440the value of the rational term {\it T1} is less than the value of the 441rational term {\it T2}, 0 otherwise. 442 443\item[\#$<$=(?T1, ?T2, ?B)] 444\index{\#$<$=/3!fd} 445{\it B} is equal to 1 iff 446the value of the rational term {\it T1} is less than or equal to the value of the 447rational term {\it T2}, 0 otherwise. 448 449\item[\#=(?T1, ?T2, ?B)] 450\index{\#=/3!fd} 451{\it B} is equal to 1 iff 452the value of the rational term {\it T1} is equal to the 453value of the rational term {\it T2}, 0 otherwise. 454 455%\latex{ 456%\item[\#$\backslash$=(?T1, ?T2, ?B)] 457%} 458%\html{ 459\item[\#\bsl=(?T1, ?T2, ?B)] 460%} 461\index{\#\bsl=/3} 462{\it B} is equal to 1 iff 463the value of the rational term {\it T1} is different from the 464value of the rational term {\it T2}, 0 otherwise. 465 466\item[\#$>$(?T1, ?T2, ?B)] 467\index{\#$>$/3!fd} 468{\it B} is equal to 1 iff 469the value of the rational term {\it T1} is greater than the 470value of the rational term {\it T2}, 0 otherwise. 471 472\item[\#$>$=(?T1, ?T2, ?B)] 473\index{\#$>$=/3!fd} 474{\it B} is equal to 1 iff 475the value of the rational term {\it T1} is greater than or equal to the 476value of the rational term {\it T2}, 0 otherwise. 477 478 479%\latex{ 480%\item[\#/$\backslash$(+E1, +E2, ?B)] 481%\index{\#/$\backslash$/3} 482%}\html{ 483%\item[\#\verb+/\+(+E1, +E2, ?B)] 484%\index{\#\verb+/\+/3} 485\item[\#\andsy(+E1, +E2, ?B)] 486\index{\#\andsy/3} 487%} 488{\it B} is equal to 1 iff 489both constraint expressions {\it E1} and {\it E2} are true, 4900 otherwise. 491 492%\latex{ 493%\item[\#$\backslash$/(+E1, +E2, ?B)] 494%\index{\#$\backslash$//3} 495%}\html{ 496%\item[\#\verb+\/+(+E1, +E2, ?B)] 497%\index{\#\verb+\/+/3} 498\item[\#\orsy(+E1, +E2, ?B)] 499\index{\#\orsy/3} 500%} 501{\it B} is equal to 1 iff 502at least one of the constraint expressions {\it E1} and {\it E2} is true, 5030 otherwise. 504 505\item[\#$<=>$(+E1, +E2, ?B)] 506\index{\#$<$=$>$/3} 507{\it B} is equal to 1 iff 508the constraint expression {\it E1} is equivalent to the 509constraint expression {\it E2}, 5100 otherwise. 511 512\item[\#=$>$(+E1, +E2, ?B)] 513\index{\#=$>$/3} 514{\it B} is equal to 1 iff 515the constraint expression {\it E1} implies the 516constraint expression {\it E2}, 5170 otherwise. 518 519%\latex{ 520%\item[\#$\backslash$+(+E1, ?B)] 521%\index{\#$\backslash$+/2} 522%}\html{ 523%\item[\#\verb+\++(+E1, ?B)] 524%\index{\#\verb+\++/2} 525\item[\#\bsl+(+E1, ?B)] 526\index{\#\bsl+/2} 527%} 528{\it B} is equal to 1 iff 529{\it E1} is false, 5300 otherwise. 531 532\end{description} 533 534%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 535\section{CHIP Compatibility Constraints Predicates} 536These constraints, defined in the module {\bf fd\_chip}, 537are provided for CHIP v.3 compatibility and they are defined using 538\index{CHIP} 539native \eclipse\ constraints. 540Their source is available in the file {\bf fd\_chip.pl}. 541 542\begin{description} 543\item[?T1 \#\# ?T2] 544\index{\#\#/2} 545The value of the rational term {\it T1} is not equal to the value of the 546rational term {\it T2}. 547 548\item[alldistinct(?List)] 549\index{alldistinct/1} 550All elements of {\it List} (domain variables and ground terms) are pairwise 551different. 552 553\item[deleteff(?Var, +List, -Rest)] 554\index{deleteff/3} 555This predicate is used to select a variable from a list of domain variables 556which has the smallest domain. 557{\it Var} is the selected variable from {\it List}, 558{\it Rest} is the rest of the list without {\it Var}. 559 560\item[deleteffc(?Var, +List, -Rest)] 561\index{deleteffc/3} 562This predicate is used to select the most constrained variable from a list 563of domain variables. 564{\it Var} is the selected variable from {\it List} which has the least domain 565and which has the most constraints attached to it. 566{\it Rest} is the rest of the list without {\it Var}. 567 568\item[deletemin(?Var, +List, -Rest)] 569\index{deletemin/3} 570This predicate is used to select the domain variable with the smallest 571lower domain bound from a list of domain variables. 572{\it Var} is the selected variable from {\it List}, 573{\it Rest} is the rest of the list without {\it Var}. 574 575{\it List} is a list of domain variables or integers. Integers are treated 576as if they were variables with singleton domains. 577 578\item[dom(+DVar, -List)] 579\index{dom/2} 580{\it List} is the list of elements in the domain of the domain variable 581{\it DVar}. 582The predicate {\bf ::/2} can also be used to query the domain 583of a domain variable, however it yields a list of intervals. 584 585{\bf NOTE:} This predicate 586should not be used in \eclipse\ programs, because all intervals 587in the domain will be expanded into element lists which causes 588unnecessary space and time overhead. 589Unless an explicit list representation is required, finite 590domains should be processed by the family of the {\bf dom_*} 591predicates in sections \ref{domaccess} and \ref{dommodify}. 592 593\item[maxdomain(+DVar, -Max)] 594\index{maxdomain/2} 595{\it Max} is the maximum value in the domain of the integer domain 596variable {\it DVar}. 597 598\item[mindomain(+DVar, -Min)] 599\index{mindomain/2} 600{\it Min} is the minimum value in the domain of the integer domain 601variable {\it DVar}. 602 603\end{description} 604 605%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 606\section{Utility Constraints Predicates} 607These constraints are defined in the module {\bf fd\_util} 608and they consist of useful predicates that are often 609needed in constraint programs. 610Their source code is available in the file {\bf fd\_util.pl}. 611 612\begin{description} 613\item[\#(?Min, ?CstList, ?Max)] 614\index{\#/3} 615The cardinality operator. 616{\it CstList} is a list of constraint expressions and this operator 617states that at least {\it Min} and at most {\it Max} out of them 618are valid. 619 620\item[dvar\_domain\_list(?Var, ?List)] 621\index{dvar\_domain\_list/2} 622{\it List} is the list of elements in the domain of the domain variable 623or ground term {\it DVar}. 624The predicate {\bf ::/2} can also be used to query the domain 625of a domain variable, however it yields a list of intervals. 626 627\item[outof(?Var, +List)] 628\index{outof/2} 629The domain variable {\it Var} is different from all elements 630of the list {\it List}. 631 632\item[labeling(+List)] 633\index{labeling/1} 634\index{labeling!fd} 635The elements of the {\it List} are instantiated using the 636\bipref{indomain/1}{../bips/lib/fd/indomain-1.html} predicate. 637 638\end{description} 639 640\section{Search Methods} 641 642A library of different search methods for finite domain problems 643is available as 644\biptxtref{library(fd_search)}{fd_search:_/_}{../bips/lib/fd_search/index.html}. 645See the Reference Manual for details. 646 647 648\section{Domain Output} 649The library {\bf fd\_domain.pl} contains output macros which 650cause an {\bf fd} attribute as well as a domain to be printed 651as lists that represent the domain values. 652A domain variable is an attributed variable whose {\bf fd} attribute 653has a {\bf print} handler which prints it in the same format. 654For instance, 655\begin{quote} 656\begin{verbatim} 657[eclipse 4]: X::1..10, dvar_attribute(X, A), A = fd{domain:D}. 658 659X = X{[1..10]} 660D = [1..10] 661A = [1..10] 662yes. 663[eclipse 5]: A::1..10, printf("%mw", A). 664A{[1..10]} 665A = A{[1..10]} 666yes. 667\end{verbatim} 668\end{quote} 669 670\section{Debugging Constraint Programs} 671The \eclipse\ debugger is a low-level debugger which is 672suitable only to debug small constraint programs or to debug 673small parts of larger programs. Typically, one would use this debugger 674to debug user-defined constraints and Prolog data processing. 675When they are known to work properly, this debugger may 676not be helpful enough to find bugs (correctness debugging) or to speed up 677a working program (performance debugging). 678For this, the {\bf display_matrix} tool from tkeclipse may be the 679appropriate tool. 680 681 682\section{Debugger Support} 683The \eclipse\ debugger supports 684debugging and tracing of finite domain programs in various ways. 685First of all, the debugger commands that handle suspended 686goals can be used to display suspended constraints ({\bf d}, {\bf \verb+^+}, 687{\bf u}) or 688to skip to a particular constraint ({\bf w}, {\bf i}). 689Note that most of the constraints are displayed using a write macro, 690\index{macro!write} 691their internal form is different. 692 693Successive updates of a domain variable can be traced using the 694debug event {\bf Hd}. 695When used, the debugger prompts for a variable name and then it 696skips to the port at which the domain of this variable 697was reduced. 698When a newline is typed instead of a variable name, it skips 699to the update of the previously entered variable. 700 701A sequence of woken goals can be skipped using the debug event {\bf Hw}. 702\index{debug events} 703 704\section{Examples} 705A very simple example of using the finite domains is the {\it send 706more money} puzzle: 707\begin{quote} 708\begin{verbatim} 709 710:- use_module(library(fd)). 711 712send(List) :- 713 List = [S, E, N, D, M, O, R, Y], 714 List :: 0..9, 715 alldifferent(List), 716 1000*S+100*E+10*N+D + 1000*M+100*O+10*R+E #= 717 10000*M+1000*O+100*N+10*E+Y, 718 M #\= 0, 719 S #\= 0, 720 labeling(List). 721\end{verbatim} 722\end{quote} 723 724The problem is stated very simply, one just writes down the conditions 725that must hold for the involved variables and then uses the default 726{\it labeling} procedure, i.e.\ the order in which the variables 727\index{labeling!fd} 728will be instantiated. 729When executing {\bf send/1}, the variables {\it S}, {\it M} 730and {\it O} are instantiated even before the labeling 731procedure starts. 732When a consistent value for the variable {\it E} is found (5), 733and this value is propagated to the other variables, all 734variables become instantiated and thus the rest of the labeling 735procedure only checks groundness of the list. 736 737A slightly more elaborate example is the {\it eight queens} 738puzzle. 739Let us show a solution for this problem generalised to N queens 740and also enhanced by a cost function that evaluates 741every solution. 742The cost can be for example 743 {\it coli - rowi} 744for the i-th queen. 745We are now looking for the solution with the smallest cost, 746i.e.\ one for which the maximum of all 747{\it coli - rowi} 748is minimal: 749 750\begin{quote} 751\begin{verbatim} 752:- use_module(library(fd)). 753 754% Find the minimal solution for the N-queens problem 755cqueens(N, List) :- 756 make_list(N, List), 757 List :: 1..N, 758 constrain_queens(List), 759 make_cost(1, List, C), 760 min_max(labeling(List), C). 761 762% Set up the constraints for the queens 763constrain_queens([]). 764constrain_queens([X|Y]) :- 765 safe(X, Y, 1), 766 constrain_queens(Y). 767 768safe(_, [], _). 769safe(X, [Y|T], K) :- 770 noattack(X, Y, K) , 771 K1 is K + 1 , 772 safe(X, T, K1). 773 774% Queens in rows X and Y cannot attack each other 775noattack(X, Y, K) :- 776 X #\= Y, 777 X + K #\= Y, 778 X - K #\= Y. 779 780% Create a list with N variables 781make_list(0, []) :- !. 782make_list(N, [_|Rest]) :- 783 N1 is N - 1, 784 make_list(N1, Rest). 785 786% Set up the cost expression 787make_cost(_, [], []). 788make_cost(N, [Var|L], [N-Var|Term]) :- 789 N1 is N + 1, 790 make_cost(N1, L, Term). 791 792labeling([]) :- !. 793labeling(L) :- 794 deleteff(Var, L, Rest), 795 indomain(Var), 796 labeling(Rest). 797\end{verbatim} 798\end{quote} 799 800The approach is similar to the previous example: first we create 801the domain variables, one for each column of the board, 802whose values will be the rows. 803We state constraints which must hold between every pair 804of queens and finally 805we make the cost term in the format required for the 806\bipref{min_max/2}{../bips/lib/fd/min_max-2.html} predicate. 807The labeling predicate selects the most constrained variable 808for instantiation using the \bipref{deleteff/3}{../bips/lib/fd/deleteff-3.html} predicate. 809When running the example, we get the following result: 810\begin{quote} 811\begin{verbatim} 812[eclipse 19]: cqueens(8, X). 813Found a solution with cost 5 814Found a solution with cost 4 815 816X = [5, 3, 1, 7, 2, 8, 6, 4] 817yes. 818\end{verbatim} 819\end{quote} 820The time needed to find the minimal solution is about five times 821shorter than the time to generate all solutions. 822This shows the advantage of the {\it branch and bound} method. 823Note also that the board for this `minimal' solution looks 824very nice. 825 826 827\section{General Guidelines to the Use of Domains} 828The {\it send more money} example already shows the general 829principle of solving problems 830using finite domain constraints: 831\begin{itemize} 832\item First the variables are defined and their domains are specified. 833 834\item Then the constraints are imposed on these variables. 835In the above example the constraints are simply built-in predicates. 836For more complicated problems it is often necessary to define 837Prolog predicates that process the variables and impose constraints 838on them. 839 840\item If stating the constraints alone did not solve the problem, 841one tries to assign values to the variables. Since every 842instantiation immediately wakes all constraints associated with the variable, 843and changes are propagated to the other variables, the search space 844is usually quickly reduced and either an early failure occurs 845or the domains of other variables are reduced or directly instantiated. 846This labeling procedure is therefore incomparably more efficient 847\index{labeling} 848than the simple {\it generate and test} algorithm. 849\end{itemize} 850 851The complexity of the program and the efficiency of the solving 852depends very much on the way these three points are performed. 853Quite frequently it is possible to state the same problem 854using different sets of variables with different domains. 855A guideline is that the search space should be as small as possible, 856and thus e.g.\ five variables with domain 1..10 857(i.e.\ search space size is $10^5$) 858are likely to be better than 859twenty variables with domain 0..1 860(space size $2^{20}$). 861 862The choice of constraints is also very important. 863Sometimes a redundant constraint, i.e.\ one that follows from the 864other constraints, can speed up the search considerably. 865This is because the system does not propagate {\it all} 866information it has to all concerned variables, because 867most of the time this would not bring anything, and thus it would 868slow down the search. 869Another reason is that the library performs no meta-level reasoning on 870constraints themselves (unlike the {\sf CHR} library). 871For example, the constraints 872\begin{quote} 873\begin{verbatim} 874X + Y #= 10, X + Y + Z #= 14 875\end{verbatim} 876\end{quote} 877allow only the value 4 for {\it Z}, however the system is not 878able to deduce this and thus it has to be provided 879as a redundant constraint. 880 881The constraints should be stated in such a way that allows the system 882to propagate all important domain updates to the appropriate variables. 883 884Another rule of thumb is that creation of choice points should be delayed 885as long as possible. Disjunctive constraints, if there are any, 886should be postponed as much as possible. Labeling, i.e.\ value 887choosing, should be done after all deterministic operations 888are carried out. 889 890The choice of the labeling procedure is perhaps the most 891\index{labeling} 892sensitive one. 893It is quite common that only a very minor change in the order 894of instantiated variables can speed up or slow down the search 895by several orders of magnitude. 896There are very few common rules available. 897If the search space is large, it usually pays off to spend 898more time in selecting the next variable to instantiate. 899The provided predicates \bipref{deleteff/3}{../bips/lib/fd/deleteff-3.html} and \bipref{deleteffc/3}{../bips/lib/fd/deleteffc-3.html} 900can be used to select the most constrained variable, but in 901many problems it is possible to extract even more information 902about which variable to instantiate next. 903 904Often it is necessary to try out several approaches 905and see how they work, if they do. 906The profiler and the statistics package can be of a great help here, 907it can point to predicates which are executed too often, or 908choice points unnecessarily backtracked over. 909 910\section{User-Defined Constraints} 911The {\bf fd.pl} library defines a set of low-level predicates 912which 913allow the user to process domain variables 914and their domains, modify them and write new constraint 915predicates. 916 917\subsection{The {\it fd} Attribute} 918A domain variable is a metaterm. 919\index{metaterm} 920\index{domain variable!implementation} 921The {\bf fd.pl} library defines a metaterm attribute 922\begin{quote} 923${\bf fd\{domain:D, min:Mi, max:Ma, any:A\}}$ 924\end{quote} 925\label{fd:attribute} 926which stores the domain information together with several suspension lists. 927The attribute arguments have the following meaning: 928\begin{itemize} 929\item {\bf domain} - the representation of the domain itself. 930Domains are treated as abstract data types, the users should not 931access them directly, but only using access and modification 932predicates listed below. 933 934\item {\bf min} - a suspension list that should be woken when the minimum 935 of the domain is updated 936 937\item {\bf max} - a suspension list that should be woken when the maximum 938 of the domain is updated 939 940\item {\bf any} - a suspension list that should be woken when the domain 941 is reduced no matter how. 942\end{itemize} 943The suspension list names can be used in the predicate \bipref{suspend/3}{../bips/kernel/suspensions/suspend-3.html} 944to denote an appropriate waking condition. 945 946The attribute of a domain variable can be accessed 947with the predicate \bipref{dvar_attribute/2}{../bips/lib/fd/dvar_attribute-2.html} 948or by unification in a matching clause: 949\index{matching clause} 950\begin{quote} 951\begin{verbatim} 952get_attribute(_{fd:Attr}, A) :- 953 -?-> 954 Attr = A. 955\end{verbatim} 956\end{quote} 957Note however, that this matching clause succeeds even if the first 958argument is a metaterm but its {\bf fd} attribute is empty. 959To succeed only for domain variables, the clause 960must be 961\begin{quote} 962\begin{verbatim} 963get_attribute(_{fd:Attr}, A) :- 964 -?-> 965 nonvar(Attr), 966 Attr = A. 967\end{verbatim} 968\end{quote} 969or to access directly attribute arguments, e.g.\ the domain 970\begin{quote} 971\begin{verbatim} 972get_domain(_{fd:fd{domain:D}}, Dom) :- 973 -?-> 974 D = Dom. 975\end{verbatim} 976\end{quote} 977The \bipref{dvar_attribute/2}{../bips/lib/fd/dvar_attribute-2.html} has the advantage that it returns 978an attribute-like structure even if its argument is already 979instantiated, which is quite useful when coding {\bf fd} 980constraints. 981 982The attribute arguments can be accessed by macros from 983the {\bf structures.pl} library, 984if e.g.\ {\bf Attr} is the attribute of a domain variable, the max 985list can be obtained as 986 987\begin{quote} 988arg(max of fd, Attr, Max) 989\end{quote} 990or, using a unification 991\begin{quote} 992Attr = fd\{max:Max\} 993\end{quote} 994 995\subsection{Domain Access} 996\label{domaccess} 997The domains are represented as abstract data types, the users are not 998supposed to access them directly, instead a number of 999predicates and macros are available to allow operations on domains. 1000 1001\begin{description} 1002\item[dom_check_in(+Element, +Dom)] 1003\index{dom_check_in/2} 1004Succeed if the integer {\it Element} is in the domain {\it Dom}. 1005 1006\item[dom_compare(?Res, +Dom1, +Dom2)] 1007\index{dom_compare/3} 1008Works like \bipref{compare/3}{../bips/kernel/termcomp/compare-3.html} for terms. 1009{\it Res} is unified with 1010\begin{itemize} 1011\item ${\bf =}$ 1012iff {\it Dom1} is equal to {\it Dom2}, 1013\item ${\bf <}$ 1014iff {\it Dom1} is a proper subset of {\it Dom2}, 1015\item ${\bf >}$ 1016iff {\it Dom2} is a proper subset of {\it Dom1}. 1017\end{itemize} 1018Fails if neither domain is a subset of the other one. 1019 1020\item[dom_member(?Element, +Dom)] 1021\index{dom_member/2} 1022Successively instantiate {\it Element} to the values in the domain {\it Dom} 1023(similar to \bipref{indomain/1}{../bips/lib/fd/indomain-1.html}). 1024 1025\item[dom_range(+Dom, ?Min, ?Max)] 1026\index{dom_range/3} 1027Return the minimum and maximum value in the integer domain {\it Dom}. 1028Fails if {\it Dom} is a domain containing non-integer 1029elements. 1030This predicate can also be used to test if a given domain 1031is integer or not. 1032 1033\item[dom_size(+Dom, ?Size)] 1034\index{dom_size/2} 1035{\it Size} is the number of elements in the domain {\it Dom}. 1036 1037\end{description} 1038 1039\subsection{Domain Operations} 1040\label{dommodify} 1041The following predicates operate on domains alone, without modifying 1042domain {\it variables}. 1043Most of them return the size of the resulting domain which can be used 1044to test if any modification was done. 1045 1046\begin{description} 1047\item[dom_copy(+Dom1, -Dom2)] 1048\index{dom_copy/2} 1049{\it Dom2} is a copy of the domain {\it Dom1}. 1050Since the updates are done in-place, two domain variables must not share 1051the same physical domain and so when defining a new variable 1052with an existing domain, the domain has to be copied first. 1053 1054\item[dom_difference(+Dom1, +Dom2, -DomDiff, ?Size)] 1055\index{dom_difference/4} 1056The domain {\it DomDifference} is 1057%{\it Dom1 \latex{$\setminus$} \html{\verb+\+} Dom2} 1058{\it Dom1 \bsl\ Dom2} 1059%\index{\bsl/2} 1060and {\it Size} is the number of its elements. 1061Fails if {\it Dom1} is a subset of {\it Dom2}. 1062 1063\item[dom_intersection(+Dom1, +Dom2, -DomInt, ?Size)] 1064\index{dom_intersection/4} 1065The domain {\it DomInt} is the intersection of domains 1066{\it Dom1} and {\it Dom2} and {\it Size} is the number of its elements. 1067Fails if the intersection is empty. 1068 1069 1070%\item[dom_remove_element(+Dom, +El, -DomRem, ?Size)] 1071%\index{dom_remove_element/2} 1072%The domain {\it DomRem} is equal to {\it Dom} with the element 1073%{\it El} removed and {\it Size} is its size. 1074%If {\it Dom} does not contain this element, {\it DomRem} 1075%is identical to {\it Dom}. 1076 1077\item[dom_union(+Dom1, +Dom2, -DomUnion, ?Size)] 1078\index{dom_union/4} 1079The domain {\it DomUnion} is the union of domains 1080{\it Dom1} and {\it Dom2} and {\it Size} is the number of its elements. 1081Note that the main use of the predicate is to yield 1082the most specific generalisation of two domains, in the usual cases 1083the domains become smaller, not bigger. 1084 1085\item[list_to_dom(+List, -Dom)] 1086\index{list_to_dom/2} 1087Convert a list of ground terms and integer intervals into 1088a domain {\it Dom}. 1089It does not have to be sorted and integers and intervals 1090may overlap. 1091 1092\item[integer_list_to_dom(+List, -Dom)] 1093\index{integer_list_to_dom/2} 1094Similar to \bipref{list_to_dom/2}{../bips/lib/fd/list_to_dom-2.html} \index{list_to_dom/2}, but the input list should 1095contain only integers and integer intervals and it should be sorted. 1096This predicate will merge adjacent integers and intervals 1097into larger intervals whenever possible. 1098typically, this predicate should be used to convert 1099a sorted list of integers into a finite domain. 1100If the list is known to already contain proper intervals, 1101\bipref{sorted_list_to_dom/2}{../bips/lib/fd/sorted_list_to_dom-2.html} could be used instead. 1102 1103\item[sorted_list_to_dom(+List, -Dom)] 1104\index{sorted_list_to_dom/2} 1105Similar to \bipref{list_to_dom/2}{../bips/lib/fd/list_to_dom-2.html}, \index{list_to_dom/2} but the input list is assumed 1106to be already in the correct format, i.e.\ sorted and with correct integer 1107and interval values. 1108No checking on the list contents is performed. 1109 1110\end{description} 1111 1112\subsection{Accessing Domain Variables} 1113The following predicates perform various operations: 1114 1115\begin{description} 1116\item[dvar_attribute(+DVar, -Attrib)] 1117\index{dvar_attribute/2} 1118{\it Attrib} is the attribute of the domain variable {\it DVar}. 1119If {\it DVar} is instantiated, {\it Attrib} is bound to an attribute 1120with a singleton domain and empty suspension lists. 1121 1122\item[dvar_domain(+DVar, -Dom)] 1123\index{dvar_domain/2} 1124{\it Dom} is the domain of the domain variable {\it DVar}. 1125If {\it DVar} is instantiated, {\it Dom} is bound to 1126a singleton domain. 1127 1128\item[var_fd(?Var, +Dom)] 1129\index{var_fd/2} 1130If {\it Var} is a free variable, 1131it becomes a domain variable with the domain {\it Dom} 1132and with empty suspension lists. 1133The domain {\it Dom} is copied to make in-place updates 1134logically sound. 1135If {\it Var} is already a domain variable, its domain is intersected 1136with the domain {\it Dom}. 1137Fails if {\it Var} is not a variable. 1138 1139\item[dvar_msg(+DVar1, +DVar2, -MsgDVar)] 1140\index{dvar_msg/3} 1141{\it MsgVar} is a domain variable which is the most specific generalisation 1142of domain variables or ground values {\it Var1} and {\it Var2}. 1143 1144\end{description} 1145 1146\subsection{Modifying Domain Variables} 1147When the domain of a domain variable is reduced, some suspension 1148lists stored in the attribute have to be scheduled and woken. 1149 1150{\bf NOTE:} In the {\bf fd.pl} library the suspension lists 1151are woken precisely when the event associated with the 1152list occurs. 1153Thus e.g.\ the {\bf min} list is woken if and only if the minimum 1154value of the variable's domain is changed, but it is not 1155woken when the variable is instantiated to this minimum 1156or when another element from the domain is removed. 1157In this way, user-defined constraints can rely on the fact that 1158when they are executed, the domain was updated in the expected way. 1159On the other hand, user-defined constraints should also comply 1160with this rule and they should take care not to wake lists 1161when their waking condition did not occur. 1162Most predicates in this section actually do all the work themselves 1163so that the user predicates may ignore scheduling and waking completely. 1164 1165\begin{description} 1166\item[dvar_remove_element(+DVar, +El)] 1167\index{dvar_remove_element/2} 1168The element {\it El} is removed from the domain of {\it DVar} and all 1169concerned lists are woken. 1170If the resulting domain is empty, this predicate fails. If it is 1171a singleton, {\it DVar} is instantiated. 1172If the domain does not contain the element, 1173no updates are made. 1174 1175\item[dvar_remove_smaller(+DVar, +El)] 1176\index{dvar_remove_smaller/2} 1177Remove all elements in the domain of {\it DVar} which are smaller than 1178the integer {\it El} and wake all concerned lists. 1179If the resulting domain is empty, this predicate fails; if it is 1180a singleton, {\it DVar} is instantiated. 1181 1182\item[dvar_remove_greater(+DVar, +El)] 1183\index{dvar_remove_greater/2} 1184Remove all elements in the domain of {\it DVar} which are greater than 1185the integer {\it El} and wake all concerned lists. 1186If the resulting domain is empty, this predicate fails; if it is 1187a singleton, {\it DVar} is instantiated. 1188 1189\item[dvar_update(+DVar, +NewDom)] 1190\index{dvar_update/2} 1191If the size of the domain {\it NewDom} is 0, the predicate fails. 1192If it is 1, 1193the domain variable {\it DVar} 1194is instantiated to the value in the domain. 1195Otherwise, 1196if the size of the new domain is smaller than the size of 1197the domain variable's domain, 1198the domain of {\it DVar} is replaced by {\it NewDom}, 1199the appropriate suspension lists in its attribute are passed 1200to the waking scheduler and so is the {\bf constrained} list 1201in the {\bf suspend} attribute of the domain variable. 1202If the size of the new domain is equal to the old one, no 1203updates and no waking is done, i.e.\ this predicate does not 1204check an explicit equality of both domains. 1205If the size of the new domain is greater than the old one, 1206an error is raised. 1207 1208\item[dvar_replace(+DVar, +NewDom)] 1209\index{dvar_replace/2} 1210This predicate is similar to \bipref{dvar_update/2}{../bips/lib/fd/dvar_update-2.html}, but it 1211does not propagate the changes, i.e.\ no waking is done. 1212If the size of the new domain is 1, {\it DVar} 1213is not instantiated, but it is given this singleton domain. 1214This predicate is useful for local consistency checks. 1215 1216\end{description} 1217 1218\section{Extensions} 1219The {\bf fd.pl} library can be used as a basis for further 1220extensions. 1221There are several hooks that make the interfacing easier: 1222\begin{itemize} 1223\item Each time a new domain variable is created, either 1224in the {\bf ::/2} predicate or by giving it a default domain 1225in a rational arithmetic expression, the predicate \bipref{new_domain_var/1}{../bips/lib/fd/new_domain_var-1.html} 1226is called with the variable as argument. 1227Its default definition does nothing. To use it, 1228it is necessary to redefine it, i.e.\ to recompile it 1229in the {\bf fd} module, e.g.\ using \bipref{compile/2}{../bips/kernel/compiler/compile-2.html} 1230or the tool body of \bipref{compile_term/1}{../bips/kernel/compiler/compile_term-1.html}. 1231 1232\item Default domains 1233\index{domain!default} 1234are created in the predicate \bipref{default_domain/1}{../bips/lib/fd/default_domain-1.html} 1235\index{default_domain/1} 1236in the {\bf fd} module, its default definition is 1237 1238\begin{quote} 1239default_domain(Var) :- Var :: -10000000..10000000. 1240\end{quote} 1241 1242It is possible to change default domains by redefining 1243this predicate in the {\bf fd} module. 1244\end{itemize} 1245 1246\section{Example of Defining a New Constraint} 1247We will demonstrate creation of new constraints on the 1248following example. 1249To show that the constraints are not restricted to linear terms, 1250we can take the constraint 1251\begin{quote} 1252$X^2 + Y^2 \leq C.$ 1253\end{quote} 1254Assuming that {\it X} and {\it Y} are domain variables, we would 1255like to define such a predicate that will be woken 1256as soon as one or both variables' domains are updated in such a way that would 1257require updating the other variable's domain, i.e.\ updates 1258that would propagate via this constraint. 1259For simplicity we assume that {\it X} and {\it Y} are nonnegative. 1260We will define the predicate {\bf sq(X, Y, C)} which will 1261implement this constraint: 1262 1263\begin{quote} 1264\begin{verbatim} 1265:- use_module(library(fd)). 1266 1267% A*A + B*B <= C 1268sq(A, B, C) :- 1269 dvar_domain(A, DomA), 1270 dvar_domain(B, DomB), 1271 dom_range(DomA, MinA, MaxA), 1272 dom_range(DomB, MinB, MaxB), 1273 MiA2 is MinA*MinA, 1274 MaB2 is MaxB*MaxB, 1275 (MiA2 + MaB2 > C -> 1276 NewMaxB is fix(sqrt(C - MiA2)), 1277 dvar_remove_greater(B, NewMaxB) 1278 ; 1279 NewMaxB = MaxB 1280 ), 1281 MaA2 is MaxA*MaxA, 1282 MiB2 is MinB*MinB, 1283 (MaA2 + MiB2 > C -> 1284 NewMaxA is fix(sqrt(C - MiB2)), 1285 dvar_remove_greater(A, NewMaxA) 1286 ; 1287 NewMaxA = MaxA 1288 ), 1289 (NewMaxA*NewMaxA + NewMaxB*NewMaxB =< C -> 1290 true 1291 ; 1292 suspend(sq(A, B, C), 3, (A, B)->min) 1293 ), 1294 wake. % Trigger the propagation 1295\end{verbatim} 1296\end{quote} 1297 1298The steps to be executed when this constraint becomes active, 1299i.e.\ when the predicate {\bf sq/3} is called or woken 1300are the following: 1301\begin{enumerate} 1302\item We access the domains of the two variables 1303using the predicate \bipref{dvar_domain/2}{../bips/lib/fd/dvar_domain-2.html} and 1304and obtain their bounds using \bipref{dom_range/3}{../bips/lib/fd/dom_range-3.html}. 1305Note that it may happen that one of the two variables is already instantiated, 1306but these predicates still work as if the variable had a singleton domain. 1307 1308\item We check if the maximum of one or the other variable is still 1309consistent with this constraint, i.e.\ if there is a value 1310in the other variable's domain that satisfies the constraint 1311together with this maximum. 1312 1313\item If the maximum value is no longer consistent, we compute 1314the new maximum of the domain, and then update the domain 1315so that all values greater than this value are removed 1316using the predicate \bipref{dvar_remove_greater/2}{../bips/lib/fd/dvar_remove_greater-2.html}. 1317This predicate also wakes all concerned suspension lists 1318and instantiates the variable if its new domain is a singleton. 1319 1320\item After checking the updates for both variables we test 1321if the constraint is now satisfied for all values 1322in the new domains. 1323If this is not the case, we have to suspend the predicate 1324so that it is woken as soon as the minimum of either domain 1325is changed. 1326This is done using the predicate \bipref{suspend/3}{../bips/kernel/suspensions/suspend-3.html}. 1327 1328\item The last action is to trigger the execution of all goals that 1329are waiting for 1330the updates we have made. 1331It is necessary to wake these goals {\bf after} inserting 1332the new suspension, otherwise updates made in the 1333woken goals would not be propagated back to this constraint. 1334\end{enumerate} 1335 1336Here is what we get: 1337\begin{quote} 1338\begin{verbatim} 1339[eclipse 20]: [X,Y]::1..10, sq(X, Y, 50). 1340 1341X = X{[1..7]} 1342Y = Y{[1..7]} 1343 1344Delayed goals: 1345 sq(X{[1..7]}, Y{[1..7]}, 50) 1346yes. 1347[eclipse 21]: [X,Y]::1..10, sq(X, Y, 50), X #> 5. 1348 1349Y = Y{[1..3]} 1350X = X{[6, 7]} 1351 1352Delayed goals: 1353 sq(X{[6, 7]}, Y{[1..3]}, 50) 1354yes. 1355[eclipse 22]: [X,Y]::1..10, sq(X, Y, 50), X #> 5, Y #> 1. 1356 1357X = 6 1358Y = Y{[2, 3]} 1359yes. 1360[eclipse 23]: [X,Y]::1..10, sq(X, Y, 50), X #> 5, Y #> 2. 1361 1362X = 6 1363Y = 3 1364yes. 1365\end{verbatim} 1366\end{quote} 1367 1368\section{Program Examples} 1369In this section we present some FD programs that show various 1370aspects of the library usage. 1371 1372\subsection{Constraining Variable Pairs} 1373The finite domain library gives the user the possibility 1374to impose constraints on the value of a variable. 1375How, in general, is it possible to impose constraints on two 1376or more variables? 1377For example, let us assume that we have a set of colours and we 1378want to define that some colours fit with each other and others do not. 1379This should work in such a way as to propagate possible changes 1380in the domains as soon as this becomes possible. 1381 1382 1383Let us assume we have a symmetric relation that defines which 1384colours fit with each other: 1385\begin{quote} 1386\begin{verbatim} 1387% The basic relation 1388fit(yellow, blue). 1389fit(yellow, red). 1390fit(blue, yellow). 1391fit(red, yellow). 1392fit(green, orange). 1393fit(orange, green). 1394\end{verbatim} 1395\end{quote} 1396 1397The predicate {\bf nice_pair(X, Y)} is a constraint and any change of 1398the possible values of X or Y is propagated 1399to the other variable. 1400There are many ways in which this pairing can be defined in \eclipse. 1401They are different solutions with different properties, but 1402they yield the same results. 1403 1404\subsubsection{User-Defined Constraints} 1405We use more or less directly the low-level primitives to handle 1406finite domain variables. 1407We collect all consistent values for the two variables, remove 1408all other values from their domains and then suspend 1409the predicate until one of its arguments is updated: 1410\begin{quote} 1411\begin{verbatim} 1412nice_pair(A, B) :- 1413 % get the domains of both variables 1414 dvar_domain(A, DA), 1415 dvar_domain(B, DB), 1416 % make a list of respective matching colours 1417 setof(Y, X^(dom_member(X, DA), fit(X, Y)), BL), 1418 setof(X, Y^(dom_member(Y, DB), fit(X, Y)), AL), 1419 % convert the lists to domains 1420 sorted_list_to_dom(AL, DA1), 1421 sorted_list_to_dom(BL, DB1), 1422 % intersect the lists with the original domains 1423 dom_intersection(DA, DA1, DA_New, _), 1424 dom_intersection(DB, DB1, DB_New, _), 1425 % and impose the result on the variables 1426 dvar_update(A, DA_New), 1427 dvar_update(B, DB_New), 1428 % unless one variable is already instantiated, suspend 1429 % and wake as soon as any element of the domain is removed 1430 (var(A), var(B) -> 1431 suspend(nice_pair(A, B), 2, [A,B]->any) 1432 ; 1433 true 1434 ). 1435 1436% Declare the domains 1437colour(A) :- 1438 findall(X, fit(X, _), L), 1439 A :: L. 1440\end{verbatim} 1441\end{quote} 1442 1443After defining the domains, we can state the constraints: 1444\begin{quote} 1445\begin{verbatim} 1446[eclipse 5]: colour([A,B,C]), nice_pair(A, B), nice_pair(B, C), A #\= green. 1447 1448B = B{[blue, green, red, yellow]} 1449C = C{[blue, orange, red, yellow]} 1450A = A{[blue, orange, red, yellow]} 1451 1452Delayed goals: 1453 nice_pair(A{[blue, orange, red, yellow]}, B{[blue, green, red, yellow]}) 1454 nice_pair(B{[blue, green, red, yellow]}, C{[blue, orange, red, yellow]}) 1455\end{verbatim} 1456\end{quote} 1457 1458This way of defining new constraints is often the most efficient 1459one, but usually also the most tedious one. 1460 1461 1462\subsubsection{Using the {\it element} Constraint} 1463In this case we use the available primitive in the fd library. Whenever 1464it is necessary to associate a fd variable with some other fd variable, 1465the \bipref{element/3}{../bips/lib/fd/element-3.html} constraint is a likely candidate. Sometimes it is 1466rather awkward to use, because additional variables must be used, 1467but it gives enough power: 1468 1469\begin{quote} 1470\begin{verbatim} 1471nice_pair(A, B) :- 1472 element(I, [yellow, yellow, blue, red, green, orange], A), 1473 element(I, [blue, red, yellow, yellow, orange, green], B). 1474\end{verbatim} 1475\end{quote} 1476 1477We define a new variable {\bf I} which is a sort of index into the 1478clauses of the fit predicate. The first colour list contains 1479colours in the first argument of fit/2 and the second list 1480contains colours from the second argument. The propagation is similar 1481to that of the previous one. 1482 1483When \bipref{element/3}{../bips/lib/fd/element-3.html} can be used, it is usually faster 1484than the previous approach, because \bipref{element/3}{../bips/lib/fd/element-3.html} is partly 1485implemented in C. 1486 1487\subsubsection{Using Evaluation Constraints} 1488We can also encode directly the relations between elements 1489in the domains of the two variables: 1490 1491\begin{quote} 1492\begin{verbatim} 1493nice_pair(A, B) :- 1494 np(A, B), 1495 np(B, A). 1496 1497np(A, B) :- 1498 [A,B] :: [yellow, blue, red, orange, green], 1499 A #= yellow #=> B :: [blue, red], 1500 A #= blue #=> B #= yellow, 1501 A #= red #=> B #= yellow, 1502 A #= green #=> B #= orange, 1503 A #= orange #=> B #= green. 1504\end{verbatim} 1505\end{quote} 1506 1507This method is quite simple and does not need any special analysis; 1508on the other hand it potentially creates a huge number of 1509auxiliary constraints and variables. 1510 1511 1512\subsubsection{Using Generalised Propagation} 1513Propia is the first candidate to convert an existing relation into 1514a constraint. One can simply use {\bf infers most} to achieve the propagation: 1515 1516\begin{quote} 1517\begin{verbatim} 1518nice_pair(A, B) :- 1519 fit(A, B) infers most. 1520\end{verbatim} 1521\end{quote} 1522 1523Using Propia is usually very easy and the programs are short 1524and readable, so that this style of constraints writing 1525is quite useful e.g.\ for teaching. 1526It is not as efficient as with user-defined constraints, but 1527if the amount of propagation is more important that the efficiency 1528of the constraint itself, it can yield good results, too. 1529 1530\subsubsection{Using Constraint Handling Rules} 1531The {\tt domain} solver in {\sf CHR} can be used directly with the 1532\bipref{element/3}{../bips/lib/fd/element-3.html} constraint as well, however it is also possible 1533to define directly domains consisting of pairs: 1534\begin{quote} 1535\begin{verbatim} 1536:- lib(chr). 1537:- chr(lib(domain)). 1538 1539nice_pair(A, B) :- 1540 setof(X-Y, fit(X, Y), L), 1541 A-B :: L. 1542 1543\end{verbatim} 1544\end{quote} 1545 1546The pairs are then constrained accordingly: 1547\begin{quote} 1548\begin{verbatim} 1549[eclipse 2]: nice_pair(A, B), nice_pair(B, C), A ne orange. 1550 1551B = B 1552C = C 1553A = A 1554 1555Constraints: 1556(9) A_g1484 - B_g1516 :: [blue - yellow, green - orange, red - yellow, 1557yellow - blue, yellow - red] 1558(10) A_g1484 :: [blue, green, red, yellow] 1559(12) B_g1516 - C_g3730 :: [blue - yellow, orange - green, red - yellow, 1560yellow - blue, yellow - red] 1561(13) B_g1516 :: [blue, orange, red, yellow] 1562(14) C_g3730 :: [blue, green, red, yellow] 1563\end{verbatim} 1564\end{quote} 1565 1566 1567\subsection{Puzzles} 1568Various kinds of puzzles can be easily solved using finite domains. 1569We show here the classical Lewis Carrol's puzzle with five houses and a zebra: 1570\begin{quote} 1571\begin{verbatim} 1572Five men with different nationalities live in the first five houses 1573of a street. They practise five distinct professions, and each of 1574them has a favourite animal and a favourite drink, all of them 1575different. The five houses are painted in different colours. 1576 1577The Englishman lives in a red house. 1578The Spaniard owns a dog. 1579The Japanese is a painter. 1580The Italian drinks tea. 1581The Norwegian lives in the first house on the left. 1582The owner of the green house drinks coffee. 1583The green house is on the right of the white one. 1584The sculptor breeds snails. 1585The diplomat lives in the yellow house. 1586Milk is drunk in the middle house. 1587The Norwegian's house is next to the blue one. 1588The violinist drinks fruit juice. 1589The fox is in a house next to that of the doctor. 1590The horse is in a house next to that of the diplomat. 1591 1592Who owns a Zebra, and who drinks water? 1593\end{verbatim} 1594\end{quote} 1595 1596One may be tempted to define five variables Nationality, 1597Profession, Colour, etc. with atomic domains to represent 1598the problem. 1599Then, however, it is quite difficult to express equalities 1600over these different domains. 1601A much simpler solution is to define 5x5 integer variables for each 1602mentioned item, to number the houses from one to five 1603and to represent the fact that e.g.\ Italian drinks tea 1604by equating Italian = Tea. 1605The value of both variables represents then the number of their house. 1606In this way, no special constraints are needed and 1607the problem is very easily described: 1608\begin{quote} 1609\begin{verbatim} 1610:- lib(fd). 1611 1612zebra([zebra(Zebra), water(Water)]) :- 1613 Sol = [Nat, Color, Profession, Pet, Drink], 1614 Nat = [English, Spaniard, Japanese, Italian, Norwegian], 1615 Color = [Red, Green, White, Yellow, Blue], 1616 Profession = [Painter, Sculptor, Diplomat, Violinist, Doctor], 1617 Pet = [Dog, Snails, Fox, Horse, Zebra], 1618 Drink = [Tea, Coffee, Milk, Juice, Water], 1619 1620 % we specify the domains and the fact 1621 % that the values are exclusive 1622 Nat :: 1..5, 1623 Color :: 1..5, 1624 Profession :: 1..5, 1625 Pet :: 1..5, 1626 Drink :: 1..5, 1627 alldifferent(Nat), 1628 alldifferent(Color), 1629 alldifferent(Profession), 1630 alldifferent(Pet), 1631 alldifferent(Drink), 1632 1633 % and here follow the actual constraints 1634 English = Red, 1635 Spaniard = Dog, 1636 Japanese = Painter, 1637 Italian = Tea, 1638 Norwegian = 1, 1639 Green = Coffee, 1640 Green #= White + 1, 1641 Sculptor = Snails, 1642 Diplomat = Yellow, 1643 Milk = 3, 1644 Dist1 #= Norwegian - Blue, Dist1 :: [-1, 1], 1645 Violinist = Juice, 1646 Dist2 #= Fox - Doctor, Dist2 :: [-1, 1], 1647 Dist3 #= Horse - Diplomat, Dist3 :: [-1, 1], 1648 1649 flatten(Sol, List), 1650 labeling(List). 1651\end{verbatim} 1652\end{quote} 1653 1654\subsection{Bin Packing} 1655In this type of problems the goal is to pack a certain amount of 1656different things into the minimal number of bins under specific constraints. 1657Let us solve an example given by Andre Vellino in the Usenet 1658group comp.lang.prolog, June 93: 1659\begin{itemize} 1660\item There are 5 types of components: 1661 1662 glass, plastic, steel, wood, copper 1663 1664\item There are three types of bins: 1665 1666 red, blue, green 1667 1668\item whose capacity constraints are: 1669 1670\begin{itemize} 1671\item red has capacity 3 1672\item blue has capacity 1 1673\item green has capacity 4 1674\end{itemize} 1675 1676\item containment constraints are: 1677\begin{itemize} 1678\item red can contain glass, wood, copper 1679\item blue can contain glass, steel, copper 1680\item green can contain plastic, wood, copper 1681\end{itemize} 1682 1683\item and requirement constraints are (for all bin types): 1684 1685 wood requires plastic 1686 1687\item Certain component types cannot coexist: 1688 1689\begin{itemize} 1690\item glass exclusive copper 1691\item copper exclusive plastic 1692\end{itemize} 1693 1694\item and certain bin types have capacity constraint for certain 1695components 1696 1697\begin{itemize} 1698\item red contains at most 1 of wood 1699\item green contains at most 2 of wood 1700\end{itemize} 1701 1702\item Given an initial supply of: 17031 of glass, 17042 of plastic, 17051 of steel, 17063 of wood, 17072 of copper, 1708what is the minimum total number of bins required to 1709contain the components? 1710\end{itemize} 1711 1712To solve this problem, it is not enough to state constraints on some 1713variables and to start a labeling procedure on them. 1714The variables are namely not known, because we don't know how many 1715bins we should take. 1716One possibility would be to take a large enough number of bins 1717and to try to find a minimum number. 1718However, usually it is better to generate constraints 1719for an increasing fixed number of bins until a solution is found. 1720 1721The predicate {\bf solve/1} returns the solution for this 1722particular problem, {\bf solve_bin/2} is the general predicate 1723that takes an amount of components packed into a {\bf cont/5} 1724structure and it returns the solution. 1725\begin{quote} 1726\begin{verbatim} 1727solve(Bins) :- 1728 solve_bin(cont(1, 2, 1, 3, 2), Bins). 1729\end{verbatim} 1730\end{quote} 1731 1732{\bf solve_bin/2} computes the sum of all components which is necessary 1733as a limit value for various domains, calls {\bf bins/4} to 1734generate a list {\bf Bins} with an increasing number of elements 1735and finally it labels all variables in the list: 1736\begin{quote} 1737\begin{verbatim} 1738solve_bin(Demand, Bins) :- 1739 Demand = cont(G, P, S, W, C), 1740 Sum is G + P + S + W + C, 1741 bins(Demand, Sum, [Sum, Sum, Sum, Sum, Sum, Sum], Bins), 1742 label(Bins). 1743\end{verbatim} 1744\end{quote} 1745 1746The predicate to generate a list of bins with appropriate 1747constraints works as follows: 1748first it tries to match the amount of remaining components with zero 1749and the list with nil. 1750If this fails, a new bin represented by a list 1751\begin{quote} 1752${\bf [Colour, Glass, Plastic, Steel, Wood, Copper]}$ 1753\end{quote} 1754is added to the bin list, 1755appropriate constraints are imposed on all the new bin's 1756variables, 1757its contents is subtracted from the remaining number of components, 1758and the predicate calls itself recursively: 1759 1760\begin{quote} 1761\begin{verbatim} 1762bins(cont(0, 0, 0, 0, 0), 0, _, []). 1763bins(cont(G0, P0, S0, W0, C0), Sum0, LastBin, [Bin|Bins]) :- 1764 Bin = [_Col, G, P, S, W, C], 1765 bin(Bin, Sum), 1766 G2 #= G0 - G, 1767 P2 #= P0 - P, 1768 S2 #= S0 - S, 1769 W2 #= W0 - W, 1770 C2 #= C0 - C, 1771 Sum2 #= Sum0 - Sum, 1772 ordering(Bin, LastBin), 1773 bins(cont(G2, P2, S2, W2, C2), Sum2, Bin, Bins). 1774\end{verbatim} 1775\end{quote} 1776The {\bf ordering/2} constraints are strictly necessary because 1777this problem has a huge number of symmetric solutions. 1778 1779The constraints imposed on a single bin correspond exactly to the 1780problem statement: 1781\begin{quote} 1782\begin{verbatim} 1783bin([Col, G, P, S, W, C], Sum) :- 1784 Col :: [red, blue, green], 1785 [Capacity, G, P, S, W, C] :: 0..4, 1786 G + P + S + W + C #= Sum, 1787 Sum #> 0, % no empty bins 1788 Sum #<= Capacity, 1789 capacity(Col, Capacity), 1790 contents(Col, G, P, S, W, C), 1791 requires(W, P), 1792 exclusive(G, C), 1793 exclusive(C, P), 1794 at_most(1, red, Col, W), 1795 at_most(2, green, Col, W). 1796\end{verbatim} 1797\end{quote} 1798 1799We will code all of the special constraints with the 1800maximum amount of propagation to show how this can be 1801achieved. 1802In most programs, however, it is not necessary to 1803propagate all values everywhere which simplifies the 1804code quite considerably. 1805Often it is also possible to use some of the built-in symbolic 1806constraints of \eclipse, e.g.\ \bipref{element/3}{../bips/lib/fd/element-3.html} or \bipref{atmost/3}{../bips/lib/fd/atmost-3.html}. 1807 1808\subsubsection{Capacity Constraints} 1809{\bf capacity(Color, Capacity)} should instantiate the capacity 1810if the colour is known, and reduce the colour values 1811if the capacity is known to be greater than 1812some values. 1813If we use evaluation constraints, we can code the constraint directly, 1814using equivalences: 1815\begin{quote} 1816\begin{verbatim} 1817capacity(Color, Capacity) :- 1818 Color #= blue #<=> Capacity #= 1, 1819 Color #= green #<=> Capacity #= 4, 1820 Color #= red #<=> Capacity #= 3. 1821\end{verbatim} 1822\end{quote} 1823 1824A more efficient code would take into account the ordering on the 1825capacities. 1826Concretely, if the capacity is greater than 1, the colour cannot 1827be blue and if it is greater than 3, it must be green: 1828 1829\begin{quote} 1830\begin{verbatim} 1831capacity(Color, Capacity) :- 1832 var(Color), 1833 !, 1834 dvar_domain(Capacity, DC), 1835 dom_range(DC, MinC, _), 1836 (MinC > 1 -> 1837 Color #\= blue, 1838 (MinC > 3 -> 1839 Color = green 1840 ; 1841 suspend(capacity(Color, Capacity), 3, (Color, Capacity)->inst) 1842 ) 1843 ; 1844 suspend(capacity(Color, Capacity), 3, [Color->inst, Capacity->min]) 1845 ). 1846capacity(blue, 1). 1847capacity(green, 4). 1848capacity(red, 3). 1849\end{verbatim} 1850\end{quote} 1851Note that when suspended, the predicate waits for colour instantiation 1852or for minimum of the capacity to be updated (except that 3 is one less 1853than the maximum capacity and thus waiting for its instantiation 1854is equivalent). 1855 1856\subsubsection{Containment Constraints} 1857The containment constraints are stated as logical expressions 1858and this is also the easiest way to medel them. 1859The important point to remember is that a condition like 1860{\it red can contain glass, wood, copper} 1861actually means 1862{\it red cannot contain plastic or steel} 1863which can be written as 1864 1865\begin{quote} 1866\begin{verbatim} 1867contents(Col, G, P, S, W, _) :- 1868 Col #= red #=> P #= 0 #/\ S #= 0, 1869 Col #= blue #=> P #= 0 #/\ W #= 0, 1870 Col #= green #=> G #= 0 #/\ S #= 0. 1871\end{verbatim} 1872\end{quote} 1873 1874If we want to model the containment with low-level domain predicates, 1875it is easier to state them in the equivalent conjugate form: 1876\begin{itemize} 1877\item glass can be contained in red or blue 1878\item plastic can be contained in green 1879\item steel can be contained in blue 1880\item wood can be contained in red, green 1881\item copper can be contained in red, blue, green 1882\end{itemize} 1883 1884or in a further equivalent form that uses at most one bin colour: 1885\begin{itemize} 1886\item glass can not be contained in green 1887\item plastic can be contained in green 1888\item steel can be contained in blue 1889\item wood can not be contained in blue 1890\item copper can be contained in anything 1891\end{itemize} 1892 1893\begin{quote} 1894\begin{verbatim} 1895contents(Col, G, P, S, W, _) :- 1896 not_contained_in(Col, G, green), 1897 contained_in(Col, P, green), 1898 contained_in(Col, S, blue), 1899 not_contained_in(Col, W, blue). 1900\end{verbatim} 1901\end{quote} 1902 1903{\bf contained_in(Color, Component, In)} states that 1904if Color is different from In, there can be no such component 1905in it, i.e.\ Component is zero: 1906\begin{quote} 1907\begin{verbatim} 1908contained_in(Col, Comp, In) :- 1909 nonvar(Col), 1910 !, 1911 (Col \== In -> 1912 Comp = 0 1913 ; 1914 true 1915 ). 1916contained_in(Col, Comp, In) :- 1917 dvar_domain(Comp, DM), 1918 dom_range(DM, MinD, _), 1919 (MinD > 0 -> 1920 Col = In 1921 ; 1922 suspend(contained_in(Col, Comp, In), 2, [Comp->min, Col->inst]) 1923 ). 1924\end{verbatim} 1925\end{quote} 1926 1927{\bf not_contained_in(Color, Component, In)} states that if the bin is of the given 1928colour, the component cannot be contained in it: 1929\begin{quote} 1930\begin{verbatim} 1931not_contained_in(Col, Comp, In) :- 1932 nonvar(Col), 1933 !, 1934 (Col == In -> 1935 Comp = 0 1936 ; 1937 true 1938 ). 1939not_contained_in(Col, Comp, In) :- 1940 dvar_domain(Comp, DM), 1941 dom_range(DM, MinD, _), 1942 (MinD > 0 -> 1943 Col #\= In 1944 ; 1945 suspend(not_contained_in(Col, Comp, In), 2, [Comp->min, Col->any]) 1946 ). 1947\end{verbatim} 1948\end{quote} 1949 1950As you can see again, modeling with the low-level domain predicates 1951might give a faster and more precise programs, 1952but it is much more difficult than using constraint 1953expressions and evaluation constraints. 1954A good approach is thus to start with constraint expressions 1955and only if they are not efficient enough, to (stepwise) recode 1956some or all constraints with the low-level predicates. 1957 1958\subsubsection{Requirement Constraints} 1959The constraint `A requires B' is written as 1960 1961\begin{quote} 1962\begin{verbatim} 1963requires(A, B) :- 1964 A #> 0 #=> B #> 0. 1965\end{verbatim} 1966\end{quote} 1967 1968With low-level predicates, 1969the constraint `A requires B' is woken as soon as some 1970A is present or B is known: 1971\begin{quote} 1972\begin{verbatim} 1973requires(A, B) :- 1974 nonvar(B), 1975 !, 1976 ( B = 0 -> 1977 A = 0 1978 ; 1979 true 1980 ). 1981requires(A, B) :- 1982 dvar_domain(A, DA), 1983 dom_range(DA, MinA, _), 1984 ( MinA > 0 -> 1985 B #> 0 1986 ; 1987 suspend(requires(A, B), 2, [A->min, B->inst]) 1988 ). 1989\end{verbatim} 1990\end{quote} 1991 1992\subsubsection{Exclusive Constraints} 1993The exclusive constraint can be written as 1994\begin{quote} 1995\begin{verbatim} 1996exclusive(A, B) :- 1997 A #> 0 #=> B #= 0, 1998 B #> 0 #=> A #= 0. 1999\end{verbatim} 2000\end{quote} 2001however a simple form with one disjunction is enough: 2002\begin{quote} 2003\begin{verbatim} 2004exclusive(A, B) :- 2005 A #= 0 #\/ B #= 0. 2006\end{verbatim} 2007\end{quote} 2008 2009With low-level domain predicates, 2010the exclusive constraint defines a suspension which is woken 2011as soon as one of the two components is present: 2012\begin{quote} 2013\begin{verbatim} 2014exclusive(A, B) :- 2015 dvar_domain(A, DA), 2016 dom_range(DA, MinA, MaxA), 2017 ( MinA > 0 -> 2018 B = 0 2019 ; MaxA = 0 -> 2020 % A == 0 2021 true 2022 ; 2023 dvar_domain(B, DB), 2024 dom_range(DB, MinB, MaxB), 2025 ( MinB > 0 -> 2026 A = 0 2027 ; MaxB = 0 -> 2028 % B == 0 2029 true 2030 ; 2031 suspend(exclusive(A, B), 3, (A,B)->min) 2032 ) 2033 ). 2034\end{verbatim} 2035\end{quote} 2036 2037\subsubsection{Atmost Constraints} 2038{\bf at_most(N, In, Colour, Components)} states that if Colour 2039is equal to In, then there can be at most N Components 2040and vice versa, if there are more than N Components, the colour 2041cannot be In. 2042With constraint expressions, this can be simply coded as 2043\begin{quote} 2044\begin{verbatim} 2045at_most(N, In, Col, Comp) :- 2046 Col #= In #=> Comp #<= N. 2047\end{verbatim} 2048\end{quote} 2049 2050A low-level solution looks as follows: 2051\begin{quote} 2052\begin{verbatim} 2053at_most(N, In, Col, Comp) :- 2054 nonvar(Col), 2055 !, 2056 (In = Col -> 2057 Comp #<= N 2058 ; 2059 true 2060 ). 2061at_most(N, In, Col, Comp) :- 2062 dvar_domain(Comp, DM), 2063 dom_range(DM, MinM, _), 2064 (MinM > N -> 2065 Col #\= In 2066 ; 2067 suspend(at_most(N, In, Col, Comp), 2, [In->inst, Comp->min]) 2068 ). 2069\end{verbatim} 2070\end{quote} 2071 2072\subsubsection{Ordering Constraints} 2073To filter out symmetric solutions we can e.g.\ impose a lexicographic 2074ordering on the bins in the list, i.e.\ the second bin must be 2075lexicographically greater or equal than the first one etc. 2076As long as the corresponding most significant 2077variables in two consecutive bins 2078are not instantiated, we cannot constrain the following ones 2079and thus we suspend the ordering on the {\bf inst} lists: 2080 2081\begin{quote} 2082\begin{verbatim} 2083ordering([], []). 2084ordering([Val1|Bin1], [Val2|Bin2]) :- 2085 Val1 #<= Val2, 2086 (integer(Val1) -> 2087 (integer(Val2) -> 2088 (Val1 = Val2 -> 2089 ordering(Bin1, Bin2) 2090 ; 2091 true 2092 ) 2093 ; 2094 suspend(ordering([Val1|Bin1], [Val2|Bin2]), 2, Val2->inst) 2095 ) 2096 ; 2097 suspend(ordering([Val1|Bin1], [Val2|Bin2]), 2, Val1->inst) 2098 ). 2099\end{verbatim} 2100\end{quote} 2101 2102There is a problem with the representation of the colour: 2103If the colour is represented by an atom, we cannot apply 2104the {\bf \#\verb+<=+/2} predicate on it. 2105To keep the ordering predicate simple and still have a symbolic 2106representation of the colour in the program, we can define 2107input macros that transform the colour atoms into integers: 2108 2109\begin{quote} 2110\begin{verbatim} 2111:- define_macro(no_macro_expansion(blue)/0, tr_col/2, []). 2112:- define_macro(no_macro_expansion(green)/0, tr_col/2, []). 2113:- define_macro(no_macro_expansion(red)/0, tr_col/2, []). 2114 2115tr_col(no_macro_expansion(red), 1). 2116tr_col(no_macro_expansion(green), 2). 2117tr_col(no_macro_expansion(blue), 3). 2118\end{verbatim} 2119\end{quote} 2120 2121\subsubsection{Labeling} 2122A straightforward labeling would be to flatten the list with 2123the bins and use e.g.\ \bipref{deleteff/3}{../bips/lib/fd/deleteff-3.html} to label a variable out of it. 2124However, for this example not all variables have the same 2125importance --- the colour variables propagate much more data 2126when instantiated. 2127Therefore, we first filter out the colours and label 2128them before all the component variables: 2129\begin{quote} 2130\begin{verbatim} 2131label(Bins) :- 2132 colours(Bins, Colors, Things), 2133 flatten(Things, List), 2134 labeleff(Colors), 2135 labeleff(List). 2136 2137colours([], [], []). 2138colours([[Col|Rest]|Bins], [Col|Cols], [Rest|Things]) :- 2139 colours(Bins, Cols, Things). 2140 2141labeleff([]). 2142labeleff(L) :- 2143 deleteff(V, L, Rest), 2144 indomain(V), 2145 labeleff(Rest). 2146\end{verbatim} 2147\end{quote} 2148 2149Note also that we need a special version of {\bf flatten/3} 2150that works with nonground lists. 2151 2152\section{Current Known Restrictions and Bugs} 2153 2154\begin{enumerate} 2155 2156\item The default domain for integer finite domain variables 2157is -10000000..10000000. 2158Larger domains must be stated explicitly using the ::/2 predicate, 2159however neither bound can be outside the standard integer 2160range for the machine (usually 32 bits). 2161 2162\item Linear integer terms are processed using machine integers 2163and thus if the maximum or minimum value of a linear term 2164overflows this range (usually 32 bits), incorrect results 2165are reported. 2166This may occur if large coefficients are used, if domains are 2167too large or a combination of the two. 2168 2169\end{enumerate} 2170 2171 2172 2173\index{library!fd.pl|)} 2174