[ library(fd_global_gac) | Reference Manual | Alphabetic Index ]

gcc_matrix(++RowBounds, ++ColBounds, +Matrix)

Constrain the cardinality of values taken in the rows and columns of Matrix as specified by RowBounds and ColBounds, respectively
RowBounds
A list of M sublists with elements of the form gcc(Low,High,Value), where Low, High and Value are integers, and High and Low are non-negative (High >= Low), and Value must be different from other Values in RowBounds
ColBounds
A list of N sublists with elements of the form gcc(Low,High,Value), where Low, High and Value are integers, and High and Low are non-negative (High >= Low), and Value must be different from other Values in ColBounds
Matrix
A two dimensional MxN matrix of Variables or integer

Description

This constraint ensures that the cardinality (the number of occurrences) of values in each row and column of Matrix conforms to the specifications in RowBounds and ColBounds, respectively. RowBounds and ColBounds are lists of triples in the form gcc(Low,High,Value) where Value is an integer, a value that Vars is to be assigned to, and must occur only once as a Value in the row/column, and whose cardinality |Value| is specified by Low =< |Value| =< High, where Low and High are non-negative integers. Vars cannot take values not specified in a gcc triplet. This constraint is logically equivalent to imposing M+N individual gcc constraints, on each row and column of Matrix, but allows more reasoning because of the interaction of the values between the rows and columns. The gcc used is from lib(fd_global_gac), but the extra inferences performed between the rows and columns themselves may be not fully domain consistent.

This is currently a prototype -- the constraint has not been tested very extensively and little effort has been spent to optimise performance. We welcome any feedback on using this constraint.

This constraint is described in J.-C. Regin and C. Gomes, 'The Cardinality Matrix Constraint', CP 2004.