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(ic_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 ic_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(ic). 43:-lib(ic_kernel). 44:-lib(graph_algorithms). 45:- lib(max_flow). 46:-lib(hash). 47:-lib(lists). 48:- lib(ic_generic_interface). 49 50:- import get_bounds/3 from ic_generic_interface. 51 52:- include(generic_global_gac). 53 54:- export alldifferent_matrix/1, 55 gcc_matrix/3. 56 57alldifferent_matrix(Matrix) :- 58 ic_global:alldifferent_matrix_internal(Matrix,ic_global_gac). 59 60gcc_matrix(Row,Col,Matrix) :- 61 ic_global:gcc_matrix_internal(Row,Col,Matrix,ic_global_gac). 62 63:- lib(ic_sequence). 64:- reexport sequence/5, 65 sequence/4 66 from ic_sequence. 67 68 69:-comment(gcc_matrix/3,[ 70 summary:"Constrain the cardinality of values taken in the rows and" 71 " columns of Matrix as specified by RowBounds and ColBounds," 72 " respectively", 73 amode:gcc_matrix(++,++,+), 74 75 args:["RowBounds":"A list of M sublists with elements of the form " 76 "gcc(Low,High,Value), where Low, High and Value are " 77 "integers, and High and Low are non-negative " 78 "(High >= Low), and Value must be different from " 79 "other Values in RowBounds", 80 "ColBounds":"A list of N sublists with elements of the form " 81 "gcc(Low,High,Value), where Low, High and Value are " 82 "integers, and High and Low are non-negative " 83 "(High >= Low), and Value must be different from " 84 "other Values in ColBounds", 85 "Matrix":"A two dimensional MxN matrix of Variables or integer"], 86 see_also: [ic_global_gac:gcc/2], 87 kind:[constraint:[root:ic]], 88 desc:html("\ 89 This constraint ensures that the cardinality (the number of occurrences) 90 of values in each row and column of Matrix conforms to the specifications 91 in RowBounds and ColBounds, respectively. RowBounds and ColBounds are 92 lists of triples in the form gcc(Low,High,Value) where Value is an integer, 93 a value that Vars is to be assigned to, and must occur only once as a 94 Value in the row/column, and whose cardinality |Value| is specified by 95 Low =< |Value| =< High, where Low and High are non-negative integers. 96 Vars cannot take values not specified in a gcc triplet. 97 This constraint is logically equivalent to imposing M+N individual gcc 98 constraints on each row and column of Matrix, but allows more reasoning 99 because of the interaction of the values between the rows and columns. 100 The gcc used is from lib(ic_global_gac), but the extra inferences 101 performed between the rows and columns themselves may be not fully 102 domain consistent. 103</P><P> 104 This is currently a prototype -- the constraint has not been tested 105 very extensively and little effort has been spent to optimise performance. 106 We welcome any feedback on using this constraint. 107</P><P> 108 This constraint is described in J.-C. Regin and C. Gomes, 109 'The Cardinality Matrix Constraint', CP 2004. 110")]). 111 112:-comment(alldifferent_matrix/1,[ 113 summary:"Constrain the rows and columns of Matrix to be different values", 114 amode:alldifferent_matrix(+), 115 args:["Matrix":"A two dimensional square matrix of Variables or integer"], 116 see_also:[ic_global_gac:alldifferent/1,_:alldifferent_matrix/1], 117 kind:[constraint:[root:ic]], 118 desc:html("\ 119<P> 120 This constraint is a matrix version of alldifferent. Matrix is a two 121 dimensional square (NxN) matrix, and the constraint ensures that the 122 elements in each row and column of the matrix are different. The same 123 value can occur in different rows and columns. It is logically 124 equivalent to imposing 2N alldifferent constraints, on each row and column, 125 but it allows more reasoning because it consider the rows and columns 126 together. This version uses alldifferent from lib(ic_global_gac), but the 127 extra inferences performed between the rows and columns themselves may be not 128 fully domain consistent. The maximum propagation occurs when the 129 variables' domains also have N values. 130</P><P> 131 This is currently a prototype -- the constraint has not been tested 132 very extensively and little effort has been spent to optimise performance. 133 We welcome any feedback on using this constraint. 134</P><P> 135 This constraint is described in J.-C. Regin and C. Gomes, 136 'The Cardinality Matrix Constraint', CP 2004. 137") ]). 138 139:- comment(sequence/5, [ 140 amode: sequence(+,+,+,+,++), 141 args: ["Low":"Non-negative integer", 142 "High":"Positive integer", 143 "K": "Postive integer", 144 "Vars": "A list of variables or integers", 145 "Values": "A list of (different) integers" 146 ], 147 summary: "The number of values taken from Values is between Low and" 148 " High for all sequences of K variables in Vars.", 149 see_also: [ic_global_gac:sequence/4,ic:element/3,ic_global:sequence_total/6,ic_global:sequence_total/7], 150 kind:[constraint:[root:ic]], 151 desc: html("\ 152<P> 153 This constraint ensures that the number of values taken from the set 154 specified in Values is at least Low and at most High for all sequences 155 of K consecutive variables/values in Vars. 156</P><P> 157 This is currently a prototype -- the constraint has not been tested 158 very extensively and little effort has been spent to optimise performance. 159 We welcome any feedback on using this constraint. 160</P><P> 161 This constraint is known as among_seq in the global constraint catalog. 162 The algorithm implemented is described in M. Maher et al.'s paper 163 'Flow-Based Propagators for the SEQUENCE and Related Global Constraints' 164 in CP'2008. 165") 166 ] 167). 168 169:- comment(sequence/4, [ 170 amode: sequence(+,+,+,+), 171 args: ["Low":"Non-negative integer", 172 "High":"Positive integer", 173 "K": "Postive integer", 174 "ZeroOnes": "A collection of 0/1 variables or integers" 175 ], 176 summary: "The number of occurrences of the value 1 is between Low and" 177 " High for all sequences of K variables in ZeroOnes", 178 see_also: [ic_global_gac:sequence/5,ic:element/3,ic_global:sequence_total/6,ic_global:sequence_total/7], 179 kind:[constraint:[root:ic]], 180 desc: html("\ 181<P> 182 This constraint ensures that the number of occurrences of the value 1 183 is at least Low and at most High for all sequences of K consecutive 184 variables/values in ZeroOnes. ZeroOnes are 0/1 variables (or integers), 185 i.e. they have the domain [0,1]. 186</P><P> 187 The ZeroOnes can be interpreted as the fulfillment of various 188 conditions if the variables are linked to these conditions. For example, 189 sequence/5 is implemented by linking the N ZeroOnes variables to a 190 matching collection of N finite domain `original' variables using 191 element/3 constraints to constrain the ZeroOnes to be 1 if the 192 corresponding original value takes one of the specified values. The 193 ZeroOnes can then be used in further constraint reasoning. 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