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);
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);
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));
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();
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) {
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.");
540 opt.
parse(argc,argv);
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;
744 result[0] =
IntSet(0, size);
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);
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Use count for implementing not all equals.
Use model on pairs of rows.
void value(int v)
Set default value to v.
virtual void print(std::ostream &os) const
Print solution.
Use nvalues for implementing not all equals.
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)
int size(void) const
Return size of array (number of elements)
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.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
unsigned int width(void) const
Return width.
void add(int v, const char *o, const char *h=NULL)
Add option value for value v, string o, and help text h.
IntVar same_or_0(const IntVar &a, const IntVar &b)
unsigned int height(void) const
Return height.
Use direct constraint for implemeting not all equals.
Use dfa for implementing not all equals.
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.
Use dfa for distinct except 0.
Use model on pairs of columns.
Use tuple set for same or 0.
Parametric base-class for scripts.
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.
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
int same_or_0(void) const
Return how to implement same or 0.
Driver::StringOption _model
General model options.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
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)
Use dfa for no monochrome rectangle.
int n
Number of negative literals for node type.
void not_all_equal(const IntVarArgs &v)
unsigned int colors(void) const
Return number of colors.
Use reification for same or 0.
int distinct_except_0(void) const
Return how to implement distinct except 0.
virtual IntVar cost(void) const
Return cost.
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.
Order rows and columns of matrix.
DFA not_all_equal_dfa(unsigned int colors)
Slice< A > row(int r) const
Access row r.
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.
Driver::StringOption _symmetry
General symmetry options.
Passing integer variables.
DFA no_monochrome_rectangle_dfa(unsigned int colors)
Passing integer arguments.
Passing Boolean variables.
void search(int v)
Set default search value.
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)
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Use model on corner combinations.
Node * x
Pointer to corresponding Boolean expression node.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Use decomposition for no monochrome rectangle.
ColoredMatrix(const ColoredMatrixOptions &opt0)
Actual model.
IntVarArray x
Array for matrix variables.
DFA distinct_except_0_dfa(unsigned int colors)
int main(int argc, char *argv[])
Main-function.
void symmetry(int v)
Set default symmetry value.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
DFA same_or_0_dfa(unsigned int colors)
int not_all_equal(void) const
Return how to implement not all equals.
ColoredMatrix(bool share, ColoredMatrix &s)
Constructor for cloning s.
Matrix-interface for arrays.
const unsigned int colors
Number of colors to use.
Use reification for distinct except 0.
void model(int v)
Set default model value.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Use naive reification for implemeting not all equals.
IntVar max_color
Maximum color used.
Slice< A > col(int c) const
Access column c.
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.
Use reification for implemeting not all equals.
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 .
void icl(IntConLevel i)
Set default integer consistency level.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Use count for distinct except 0.