1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% BEGIN LICENSE BLOCK 3% Version: CMPL 1.1 4% 5% The contents of this file are subject to the Cisco-style Mozilla Public 6% License Version 1.1 (the "License"); you may not use this file except 7% in compliance with the License. You may obtain a copy of the License 8% at www.eclipse-clp.org/license. 9% 10% Software distributed under the License is distributed on an "AS IS" 11% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 12% the License for the specific language governing rights and limitations 13% under the License. 14% 15% The Original Code is The Generalized Arc Consistent all-different global 16% constraint. 17% The Initial Developer of the Original Code is Helmut Simonis 18% Portions created by the Initial Developer are Copyright (C)2008. 19% All Rights Reserved. 20% 21% Contributor(s): Helmut Simonis, 4C, University College Cork 22% 23% END LICENSE BLOCK 24% 25%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 26 27:-module(fd_global_gac). 28:- comment(categories, ["Constraints","Algorithms"]). 29:-comment(summary,"Library of global constraints which achieve" 30 " generalized arc consistency"). 31:-comment(desc,"This library is intended for global constraints for" 32 " which GAC (generalized arc consistency, also called hyper arc" 33 " consistency, or domain consistency) is maintained." 34 " The first example is a version of the alldifferent" 35 " constraint which performs more pruning than the bound" 36 " consistent version in the fd_global library."). 37:-comment(author,"H. Simonis, 4C, University College Cork"). 38:-comment(copyright,"2008, H. Simonis, 4C, University College Cork"). 39:-comment(status,prototype). 40:-comment(date,"2008"). 41 42:-lib(fd). 43:-lib(graph_algorithms). 44:- lib(max_flow). 45:-lib(hash). 46:-lib(lists). 47:- lib(fd_generic_interface). 48 49:- import get_bounds/3 from fd_generic_interface. 50 51:- include(generic_global_gac). 52 53:- export alldifferent_matrix/1, 54 gcc_matrix/3. 55 56alldifferent_matrix(Matrix) :- 57 fd_global:alldifferent_matrix_internal(Matrix,fd_global_gac). 58 59gcc_matrix(Row,Col,Matrix) :- 60 fd_global:gcc_matrix_internal(Row,Col,Matrix,fd_global_gac). 61 62:- lib(fd_sequence). 63:- reexport sequence/5, 64 sequence/4 65 from fd_sequence. 66 67:-comment(gcc_matrix/3,[ 68 summary:"Constrain the cardinality of values taken in the rows and" 69 " columns of Matrix as specified by RowBounds and ColBounds," 70 " respectively", 71 amode:gcc_matrix(++,++,+), 72 73 args:["RowBounds":"A list of M sublists with elements of the form " 74 "gcc(Low,High,Value), where Low, High and Value are " 75 "integers, and High and Low are non-negative " 76 "(High >= Low), and Value must be different from " 77 "other Values in RowBounds", 78 "ColBounds":"A list of N sublists with elements of the form " 79 "gcc(Low,High,Value), where Low, High and Value are " 80 "integers, and High and Low are non-negative " 81 "(High >= Low), and Value must be different from " 82 "other Values in ColBounds", 83 "Matrix":"A two dimensional MxN matrix of Variables or integer"], 84 see_also: [fd_global_gac:gcc/2], 85 kind:[constraint:[root:fd]], 86 desc:html("\ 87 This constraint ensures that the cardinality (the number of occurrences) 88 of values in each row and column of Matrix conforms to the specifications 89 in RowBounds and ColBounds, respectively. RowBounds and ColBounds are 90 lists of triples in the form gcc(Low,High,Value) where Value is an integer, 91 a value that Vars is to be assigned to, and must occur only once as a 92 Value in the row/column, and whose cardinality |Value| is specified by 93 Low =< |Value| =< High, where Low and High are non-negative integers. 94 Vars cannot take values not specified in a gcc triplet. 95 This constraint is logically equivalent to imposing M+N individual gcc 96 constraints, on each row and column of Matrix, but allows more reasoning 97 because of the interaction of the values between the rows and columns. 98 The gcc used is from lib(fd_global_gac), but the extra inferences 99 performed between the rows and columns themselves may be not fully 100 domain consistent. 101</P><P> 102 This is currently a prototype -- the constraint has not been tested 103 very extensively and little effort has been spent to optimise performance. 104 We welcome any feedback on using this constraint. 105</P><P> 106 This constraint is described in J.-C. Regin and C. Gomes, 107 'The Cardinality Matrix Constraint', CP 2004. 108")]). 109 110:-comment(alldifferent_matrix/1,[ 111 summary:"Constrain the rows and columns of Matrix to be different values", 112 amode:alldifferent_matrix(+), 113 args:["Matrix":"A two dimensional square matrix of Variables or integer"], 114 see_also:[fd_global_gac:alldifferent/1,_:alldifferent_matrix/1], 115 kind:[constraint:[root:fd]], 116 desc:html("\ 117<P> 118 This constraint is a matrix version of alldifferent. Matrix is a two 119 dimensional square (NxN) matrix, and the constraint ensures that the 120 elements in each row and column of the matrix are different. The same 121 value can occur in different rows and columns. It is logically 122 equivalent to imposing 2N alldifferent constraints on each row and column, 123 but it allows more reasoning because it consider the rows and columns 124 together. The version uses alldifferent from lib(fd_global_gac), but the 125 extra inferences performed between the rows and columns themselves not be 126 fully domain consistent. The maximum propagation occurs when the 127 variables' domains also have N values. 128</P><P> 129 This is currently a prototype -- the constraint has not been tested 130 very extensively and little effort has been spent to optimise performance. 131 We welcome any feedback on using this constraint. 132</P><P> 133 This constraint is described in J.-C. Regin and C. Gomes, 134 'The Cardinality Matrix Constraint', CP 2004. 135") ]). 136 137:- comment(sequence/5, [ 138 amode: sequence(+,+,+,+,++), 139 args: ["Low":"Non-negative integer", 140 "High":"Positive integer", 141 "K": "Postive integer", 142 "Vars": "A list of variables or integers", 143 "Values": "A list of (different) integers" 144 ], 145 summary: "The number of values taken from Values is between Low and" 146 " High for all sequences of K variables in Vars.", 147 see_also: [fd_global_gac:sequence/5,fd:element/3,fd_global:sequence_total/6,fd_global:sequence_total/7], 148 kind:[constraint:[root:fd]], 149 desc: html("\ 150<P> 151 This constraint ensures that the number of values taken from the set 152 specified in Values is at least Low and at most High for all sequences 153 of K consecutive variables/values in Vars. 154</P><P> 155 This is currently a prototype -- the constraint has not been tested 156 very extensively and little effort has been spent to optimise performance. 157 We welcome any feedback on using this constraint. 158</P><P> 159 This constraint is known as among_seq in the global constraint catalog. 160 The algorithm implemented is described in M. Maher et al.'s paper 161 'Flow-Based Propagators for the SEQUENCE and Related Global Constraints' 162 in CP'2008. 163") 164 ] 165). 166 167:- comment(sequence/4, [ 168 amode: sequence(+,+,+,+), 169 args: ["Low":"Non-negative integer", 170 "High":"Positive integer", 171 "K": "Postive integer", 172 "ZeroOnes": "A collection of 0/1 variables or integers" 173 ], 174 summary: "The number of occurrences of the value 1 is between Low and" 175 " High for all sequences of K variables in ZeroOnes", 176 see_also: [fd_global_gac:sequence/5,fd:element/3,fd_global:sequence_total/6,fd_global:sequence_total/7], 177 kind:[constraint:[root:fd]], 178 desc: html("\ 179<P> 180 This constraint ensures that the number of occurrences of the value 1 181 is at least Low and at most High for all sequences of K consecutive 182 variables/values in ZeroOnes. ZeroOnes are 0/1 variables (or itnegers), 183 i.e. they have the domain [0,1]. 184</P><P> 185 The ZeroOnes can be interpreted as the fulfillment of various 186 conditions if the variables are linked to these conditions. For example, 187 sequence/5 is implemented by linking the N ZeroOnes variables to a 188 matching collection of N finite domain `original' variables using 189 element/3 constraints to constrain the ZeroOnes to be 1 if the 190 corresponding original value takes one of the specified values. The 191 ZeroOnes can then be used in further constraint reasoning. 192</P><P> 193 Note: this constraint is different from sequence/4 in lib(fd). 194</P><P> 195 This is currently a prototype -- the constraint has not been tested 196 very extensively and little effort has been spent to optimise performance. 197 We welcome any feedback on using this constraint. 198") 199 ] 200). 201 202:-pragma(debug). 203