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--; ) {
365 opt(opt0), height(opt.height()), width(opt.width()), colors(opt.colors()),
366 x(*this, height*width, 1, colors),
367 max_color(*this, 1, colors)
370 max(*
this, x, max_color);
375 if (opt.
model() & MODEL_CORNERS) {
376 for (
unsigned int c1 = 0; c1 < width; ++c1) {
377 for (
unsigned int c2 = c1+1; c2 < width; ++c2) {
378 for (
unsigned int r1 = 0; r1 < height; ++r1) {
379 for (
unsigned int r2 = r1+1; r2 < height; ++r2) {
380 not_all_equal(
IntVarArgs() << m(c1,r1) << m(c1,r2) << m(c2,r1) << m(c2,r2));
390 if (opt.
model() & MODEL_ROWS) {
391 for (
unsigned int r1 = 0; r1 < height; ++r1) {
392 for (
unsigned int r2 = r1+1; r2 < height; ++r2) {
393 no_monochrome_rectangle(m.
row(r1), m.
row(r2));
397 if (opt.
model() & MODEL_COLUMNS) {
398 for (
unsigned int c1 = 0; c1 < width; ++c1) {
399 for (
unsigned int c2 = c1+1; c2 < width; ++c2) {
400 no_monochrome_rectangle(m.
col(c1), m.
col(c2));
408 if (opt.
symmetry() & SYMMETRY_MATRIX) {
409 for (
unsigned int r = 0;
r < height-1; ++
r) {
412 for (
unsigned int c = 0;
c < width-1; ++
c) {
418 if (opt.
symmetry() & SYMMETRY_VALUES) {
435 for (
unsigned int r = 0;
r < height; ++
r) {
437 for (
unsigned int c = 0;
c < width; ++
c) {
438 os << m(
c,
r) <<
" ";
443 os <<
"\tmax color: " << max_color << std::endl;
450 height(s.height), width(s.width), colors(s.colors) {
463 _height(
"height",
"Height of matrix", 8),
464 _width(
"width",
"Width of matrix", 8),
465 _size(
"size",
"If different from 0, used as both width and height", 0),
466 _colors(
"colors",
"Maximum number of colors", 4),
467 _not_all_equal(
"not-all-equal",
"How to implement the not all equals constraint (used in corners model)",
469 _same_or_0(
"same-or-0",
"How to implement the same or 0 constraint (used in the decomposed no monochrome rectangle constraint)",
471 _distinct_except_0(
"distinct-except-0",
"How to implement the distinct except 0 constraint (used in the decomposed no monochrome rectangle constraint)",
473 _no_monochrome_rectangle(
"no-monochrome-rectangle",
"How to implement no monochrome rectangle (used in the rows model)",
482 add(_distinct_except_0);
483 add(_no_monochrome_rectangle);
495 "both",
"Order both rows/columns and values");
502 "both",
"Use both rows and corners model");
505 "matrix",
"Use both rows and columns model");
529 "Use decompositions into same_or_0 and distinct_except_0.");
532 "Use DFA as direct implementation.");
541 opt.
parse(argc,argv);
543 Script::run<ColoredMatrix,DFS,ColoredMatrixOptions>(
opt);
545 Script::run<ColoredMatrix,BAB,ColoredMatrixOptions>(
opt);
567 const int start_state = 0;
568 const int not_equal_state = 2*colors+1;
569 const int final_state = 2*colors+2;
571 int n_transitions = colors*colors + 2*colors + 2;
573 int current_transition = 0;
576 for (
unsigned int color = 1; color <=
colors; ++color) {
577 trans[current_transition++] =
583 for (
unsigned int state = 1; state <=
colors; ++state) {
584 for (
unsigned int color = 1; color <=
colors; ++color) {
585 if (color == state) {
586 trans[current_transition++] =
589 trans[current_transition++] =
597 for (
unsigned int color = 1; color <=
colors; ++color) {
598 trans[current_transition++] =
603 trans[current_transition++] =
607 trans[current_transition++] =
610 int final_states[] = {final_state, -1};
612 DFA result(start_state, trans, final_states,
true);
619 TupleSet same_or_0_tuple_set(
unsigned int colors) {
621 for (
unsigned int i = 1;
i <=
colors; ++
i) {
622 for (
unsigned int j = 1; j <=
colors; ++j) {
634 DFA distinct_except_0_dfa(
unsigned int colors)
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;
678 DFA no_monochrome_rectangle_dfa(
unsigned int colors)
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;
740 IntSetArgs distinct_except_0_counts(
unsigned int colors,
unsigned int size)
744 result[0] =
IntSet(0, size);
746 for (
unsigned int i = 1;
i <=
colors; ++
i) {
754 DFA not_all_equal_dfa(
unsigned int colors)
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.
int size(void) const
Return size of array (number of elements)
Example: Colored matrix example.
void 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.
const FloatNum max
Largest allowed float value.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
unsigned int colors(void) const
Return number of colors.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
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.
void ipl(IntPropLevel i)
Set default integer propagation level.
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
Parametric base-class for scripts.
Use dfa for no monochrome rectangle.
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.
void nvalues(Home home, const IntVarArgs &x, IntRelType irt, int y, IntPropLevel)
Post propagator for .
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
unsigned int height(void) const
Return height.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
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.
void distinct_except_0(const IntVarArgs &v)
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Driver::StringOption _search
Search options.
Use model on pairs of rows.
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Driver::StringOption _symmetry
General symmetry options.
Passing integer variables.
Passing Boolean variables.
void search(int v)
Set default search value.
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Boolean integer variables.
Post propagator for SetVar SetOpType SetVar SetRelType r
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 no_monochrome_rectangle(IntVarArgs v1, IntVarArgs v2)
Use reification for implemeting not all equals.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Gecode::IntArgs v1(4, Gecode::Int::Limits::min+4, 0, 1, Gecode::Int::Limits::max)
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
int same_or_0(void) const
Return how to implement same or 0.
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
ColoredMatrix(const ColoredMatrixOptions &opt0)
Actual model.
Slice< A > row(int r) const
Access row r.
IntVarArray x
Array for matrix variables.
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel)
Post propagator that s precedes t in x.
int main(int argc, char *argv[])
Main-function.
virtual void print(std::ostream &os) const
Print solution.
void symmetry(int v)
Set default symmetry value.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Use dfa for distinct except 0.
ColoredMatrix(ColoredMatrix &s)
Constructor for cloning s.
Post propagator for SetVar x
Matrix-interface for arrays.
const unsigned int colors
Number of colors to use.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
virtual Space * copy(void)
Copy during cloning.
void model(int v)
Set default model value.
Gecode toplevel namespace
IntVar max_color
Maximum color used.
unsigned int width(void) const
Return width.
ColoredMatrixOptions(const char *n)
Initialize options for example with name n.
#define GECODE_NEVER
Assert that this command is never executed.
Use model on pairs of columns.
Use count for distinct except 0.
Gecode::IntArgs v2(4, Gecode::Int::Limits::min, 0, 1, Gecode::Int::Limits::max-4)
Use naive reification for implemeting not all equals.