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.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
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)
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)
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.
struct Gecode::@512::NNF::@54::@55 b
For binary nodes (and, or, eqv)
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.
Slice< A > col(int c) const
Access column c.
Use reification for distinct except 0.
void model(int v)
Set default model value.
Gecode toplevel namespace
Use naive reification for implemeting not all equals.
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.
struct Gecode::@512::NNF::@54::@56 a
For atomic nodes.
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 .
Slice< A > row(int r) const
Access row r.
void icl(IntConLevel i)
Set default integer consistency level.
Use count for distinct except 0.