74 void parse(
int& argc,
char* argv[]) {
80 if (_size.
value() == 0)
81 return _height.
value();
86 unsigned int width(
void)
const {
87 if (_size.
value() == 0)
88 return _width.
value();
102 return _no_monochrome_rectangle.
value();
122 DFA same_or_0_dfa(
unsigned int colors);
130 TupleSet same_or_0_tuple_set(
unsigned int colors);
134 DFA distinct_except_0_dfa(
unsigned int colors);
138 DFA no_monochrome_rectangle_dfa(
unsigned int colors);
142 IntSetArgs distinct_except_0_counts(
unsigned int colors,
unsigned int size);
146 DFA not_all_equal_dfa(
unsigned int colors);
192 switch (
opt.same_or_0()) {
193 case SAME_OR_0_REIFIED: {
194 IntVar result(*
this, 0, colors);
201 case SAME_OR_0_TUPLE_SET: {
202 static TupleSet table = same_or_0_tuple_set(colors);
203 IntVar result(*
this, 0, colors);
207 case SAME_OR_0_DFA: {
208 static const DFA automaton = same_or_0_dfa(colors);
209 IntVar result(*
this, 0, colors);
215 return IntVar(*
this, 0, 0);
223 switch (
opt.distinct_except_0()) {
224 case DISTINCT_EXCEPT_0_REIFIED:
225 for (
int i =
v.size();
i--; ) {
227 for (
int j =
i; j--; ) {
228 rel(*
this, viIsZero || (
v[
i] !=
v[j]));
232 case DISTINCT_EXCEPT_0_DFA: {
233 static const DFA automaton = distinct_except_0_dfa(colors);
237 case DISTINCT_EXCEPT_0_COUNT: {
238 static const IntSetArgs counts = distinct_except_0_counts(colors,
std::max(width, height));
249 switch (
opt.not_all_equal()) {
250 case NOT_ALL_EQUAL_NQ: {
254 case NOT_ALL_EQUAL_NAIVE: {
258 for (
int i =
v.size();
i--; )
259 for (
int j =
i; j--; )
260 disequalities <<
expr(*
this,
v[
i] !=
v[j]);
264 case NOT_ALL_EQUAL_REIFIED: {
267 for (
int i = 0;
i <
v.size()-1; ++
i)
268 equalities <<
expr(*
this,
v[
i] ==
v[
i+1]);
272 case NOT_ALL_EQUAL_NVALUES:
276 case NOT_ALL_EQUAL_COUNT:
280 case NOT_ALL_EQUAL_DFA: {
281 static const DFA automaton = not_all_equal_dfa(colors);
292 const unsigned int length =
v1.size();
293 switch (
opt.no_monochrome_rectangle()) {
294 case NO_MONOCHROME_DECOMPOSITION: {
296 for (
unsigned int i = 0;
i < length; ++
i) {
297 z[
i] = same_or_0(
v1[
i],
v2[
i]);
299 distinct_except_0(z);
302 case NO_MONOCHROME_DFA: {
303 static const DFA automaton = no_monochrome_rectangle_dfa(colors);
305 for (
int i = length;
i--; ) {
364 :
opt(opt0), height(
opt.height()), width(
opt.width()), colors(
opt.colors()),
365 x(*this, height*width, 1, colors),
366 max_color(*this, 1, colors)
369 max(*
this,
x, max_color);
374 if (
opt.model() & MODEL_CORNERS) {
375 for (
unsigned int c1 = 0; c1 < width; ++c1) {
376 for (
unsigned int c2 = c1+1; c2 < width; ++c2) {
377 for (
unsigned int r1 = 0; r1 < height; ++r1) {
378 for (
unsigned int r2 = r1+1; r2 < height; ++r2) {
379 not_all_equal(
IntVarArgs() << m(c1,r1) << m(c1,r2) << m(c2,r1) << m(c2,r2));
389 if (
opt.model() & MODEL_ROWS) {
390 for (
unsigned int r1 = 0; r1 < height; ++r1) {
391 for (
unsigned int r2 = r1+1; r2 < height; ++r2) {
392 no_monochrome_rectangle(m.
row(r1), m.
row(r2));
396 if (
opt.model() & MODEL_COLUMNS) {
397 for (
unsigned int c1 = 0; c1 < width; ++c1) {
398 for (
unsigned int c2 = c1+1; c2 < width; ++c2) {
399 no_monochrome_rectangle(m.
col(c1), m.
col(c2));
407 if (
opt.symmetry() & SYMMETRY_MATRIX) {
408 for (
unsigned int r = 0;
r < height-1; ++
r) {
411 for (
unsigned int c = 0;
c < width-1; ++
c) {
417 if (
opt.symmetry() & SYMMETRY_VALUES) {
434 for (
unsigned int r = 0;
r < height; ++
r) {
436 for (
unsigned int c = 0;
c < width; ++
c) {
437 os << m(
c,
r) <<
" ";
442 os <<
"\tmax color: " << max_color << std::endl;
449 height(s.height), width(s.width), colors(s.colors) {
450 x.update(*
this, share, s.
x);
462 _height(
"-height",
"Height of matrix", 8),
463 _width(
"-width",
"Width of matrix", 8),
464 _size(
"-size",
"If different from 0, used as both width and height", 0),
465 _colors(
"-colors",
"Maximum number of colors", 4),
466 _not_all_equal(
"-not-all-equal",
"How to implement the not all equals constraint (used in corners model)",
468 _same_or_0(
"-same-or-0",
"How to implement the same or 0 constraint (used in the decomposed no monochrome rectangle constraint)",
470 _distinct_except_0(
"-distinct-except-0",
"How to implement the distinct except 0 constraint (used in the decomposed no monochrome rectangle constraint)",
472 _no_monochrome_rectangle(
"-no-monochrome-rectangle",
"How to implement no monochrome rectangle (used in the rows model)",
481 add(_distinct_except_0);
482 add(_no_monochrome_rectangle);
494 "both",
"Order both rows/columns and values");
501 "both",
"Use both rows and corners model");
504 "matrix",
"Use both rows and columns model");
528 "Use decompositions into same_or_0 and distinct_except_0.");
531 "Use DFA as direct implementation.");
542 Script::run<ColoredMatrix,DFS,ColoredMatrixOptions>(
opt);
544 Script::run<ColoredMatrix,BAB,ColoredMatrixOptions>(
opt);
566 const int start_state = 0;
567 const int not_equal_state = 2*colors+1;
568 const int final_state = 2*colors+2;
570 int n_transitions = colors*colors + 2*colors + 2;
572 int current_transition = 0;
575 for (
unsigned int color = 1; color <= colors; ++color) {
576 trans[current_transition++] =
582 for (
unsigned int state = 1; state <= colors; ++state) {
583 for (
unsigned int color = 1; color <= colors; ++color) {
584 if (color == state) {
585 trans[current_transition++] =
588 trans[current_transition++] =
596 for (
unsigned int color = 1; color <= colors; ++color) {
597 trans[current_transition++] =
602 trans[current_transition++] =
606 trans[current_transition++] =
609 int final_states[] = {final_state, -1};
611 DFA result(start_state, trans, final_states,
true);
621 for (
unsigned int i = 1;
i <= colors; ++
i) {
622 for (
unsigned int j = 1; j <= colors; ++j) {
645 const int nstates = 1 << colors;
646 const int start_state = nstates-1;
649 int current_transition = 0;
651 for (
int state = nstates; state--; ) {
654 for (
unsigned int color = 1; color <= colors; ++color) {
655 const unsigned int color_bit = (1 << (color-1));
656 if (state & color_bit) {
657 trans[current_transition++] =
664 int* final_states =
new int[nstates+1];
665 final_states[nstates] = -1;
666 for (
int i = nstates;
i--; ) {
670 DFA result(start_state, trans, final_states);
673 delete[] final_states;
694 const int base_states = 1 << colors;
695 const int start_state = base_states-1;
696 const int nstates = base_states + colors*base_states;
699 int current_transition = 0;
701 for (
int state = base_states; state--; ) {
702 for (
unsigned int color = 1; color <= colors; ++color) {
703 const unsigned int color_bit = (1 << (color-1));
704 const int color_remembered_state = state + color*base_states;
706 trans[current_transition++] =
709 for (
unsigned int next_color = 1; next_color <= colors; ++next_color) {
710 if (next_color == color) {
712 if (state & color_bit) {
713 trans[current_transition++] =
717 trans[current_transition++] =
724 assert(current_transition <= nstates*colors+1);
726 int* final_states =
new int[base_states+1];
727 final_states[base_states] = -1;
728 for (
int i = base_states;
i--; ) {
732 DFA result(start_state, trans, final_states);
735 delete[] final_states;
746 for (
unsigned int i = 1;
i <= colors; ++
i) {
764 const int nstates = 1 + colors + 1;
765 const int start_state = 0;
766 const int final_state = nstates-1;
769 int current_transition = 0;
772 for (
unsigned int color = 1; color <= colors; ++color) {
773 trans[current_transition++] =
DFA::Transition(start_state, color, color);
777 for (
unsigned int state = 1; state <= colors; ++state) {
778 for (
unsigned int color = 1; color <= colors; ++color) {
779 if (state == color) {
782 trans[current_transition++] =
DFA::Transition(state, color, final_state);
788 for (
unsigned int color = 1; color <= colors; ++color) {
789 trans[current_transition++] =
DFA::Transition(final_state, color, final_state);
794 int final_states[] = {final_state, -1};
796 DFA result(start_state, trans, final_states);
Use dfa for implementing not all equals.
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
void value(int v)
Set default value to v.
Use decomposition for no monochrome rectangle.
Use nvalues for implementing not all equals.
Use reification for same or 0.
Order rows and columns of matrix.
Slice< A > col(int c) const
Access column c.
void finalize(void)
Finalize tuple set.
Example: Colored matrix example.
virtual Space * copy(bool share)
Copy during cloning.
const FloatNum max
Largest allowed float value.
TupleSet same_or_0_tuple_set(unsigned int colors)
unsigned int colors(void) const
Return number of colors.
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
const unsigned int height
Height of matrix.
virtual IntVar cost(void) const
Return cost.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void add(int v, const char *o, const char *h=NULL)
Add option value for value v, string o, and help text h.
Use reification for distinct except 0.
IntVar same_or_0(const IntVar &a, const IntVar &b)
Use model on corner combinations.
Use count for implementing not all equals.
struct Gecode::@511::NNF::@54::@55 b
For binary nodes (and, or, eqv)
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
Parametric base-class for scripts.
Use dfa for no monochrome rectangle.
IntSetArgs distinct_except_0_counts(unsigned int colors, unsigned int size)
void add(Driver::BaseOption &o)
Add new option o.
void value(unsigned int v)
Set default value to v.
Driver::StringOption _model
General model options.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Use direct constraint for implemeting not all equals.
Gecode::FloatVal c(-8, 8)
Deterministic finite automaton (DFA)
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
const ColoredMatrixOptions & opt
Options for model.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
void not_all_equal(const IntVarArgs &v)
int not_all_equal(void) const
Return how to implement not all equals.
int distinct_except_0(void) const
Return how to implement distinct except 0.
unsigned int height(void) const
Return height.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Specification of a DFA transition.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Use tuple set for same or 0.
DFA not_all_equal_dfa(unsigned int colors)
void distinct_except_0(const IntVarArgs &v)
Driver::StringOption _search
Search options.
void precede(Home home, const IntVarArgs &x, int s, int t, IntConLevel)
Post propagator that s precedes t in x.
Use model on pairs of rows.
Driver::StringOption _symmetry
General symmetry options.
Passing integer variables.
DFA no_monochrome_rectangle_dfa(unsigned int colors)
Passing integer arguments.
Passing Boolean variables.
struct Gecode::@511::NNF::@54::@56 a
For atomic nodes.
Boolean integer variables.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Class represeting a set of tuples.
const unsigned int width
Width of matrix.
String-valued option (integer value defined by strings)
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
void no_monochrome_rectangle(IntVarArgs v1, IntVarArgs v2)
Use reification for implemeting not all equals.
int same_or_0(void) const
Return how to implement same or 0.
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Node * x
Pointer to corresponding Boolean expression node.
void parse(int argc, char *argv[])
Parse commandline arguments.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
ColoredMatrix(const ColoredMatrixOptions &opt0)
Actual model.
Slice< A > row(int r) const
Access row r.
IntVarArray x
Array for matrix variables.
DFA distinct_except_0_dfa(unsigned int colors)
int main(int argc, char *argv[])
Main-function.
virtual void print(std::ostream &os) const
Print solution.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Use dfa for distinct except 0.
DFA same_or_0_dfa(unsigned int colors)
ColoredMatrix(bool share, ColoredMatrix &s)
Constructor for cloning s.
Matrix-interface for arrays.
const unsigned int colors
Number of colors to use.
Gecode toplevel namespace
IntVar max_color
Maximum color used.
BrancherHandle branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
unsigned int width(void) const
Return width.
ColoredMatrixOptions(const char *n)
Initialize options for example with name n.
void add(const IntArgs &tuple)
Add tuple to tuple set.
#define GECODE_NEVER
Assert that this command is never executed.
void nvalues(Home home, const IntVarArgs &x, IntRelType irt, int y, IntConLevel)
Post propagator for .
Use model on pairs of columns.
Use count for distinct except 0.
Use naive reification for implemeting not all equals.