70 void parse(
int& argc,
char* argv[]) {
76 if (_size.
value() == 0)
77 return _height.
value();
82 unsigned int width(
void)
const {
83 if (_size.
value() == 0)
84 return _width.
value();
98 return _no_monochrome_rectangle.
value();
118 DFA same_or_0_dfa(
unsigned int colors);
126 TupleSet same_or_0_tuple_set(
unsigned int colors);
130 DFA distinct_except_0_dfa(
unsigned int colors);
134 DFA no_monochrome_rectangle_dfa(
unsigned int colors);
138 IntSetArgs distinct_except_0_counts(
unsigned int colors,
unsigned int size);
142 DFA not_all_equal_dfa(
unsigned int colors);
189 case SAME_OR_0_REIFIED: {
190 IntVar result(*
this, 0, colors);
197 case SAME_OR_0_TUPLE_SET: {
198 static TupleSet table = same_or_0_tuple_set(colors);
199 IntVar result(*
this, 0, colors);
203 case SAME_OR_0_DFA: {
204 static const DFA automaton = same_or_0_dfa(colors);
205 IntVar result(*
this, 0, colors);
211 return IntVar(*
this, 0, 0);
220 case DISTINCT_EXCEPT_0_REIFIED:
221 for (
int i = v.
size();
i--; ) {
223 for (
int j =
i; j--; ) {
224 rel(*
this, viIsZero || (v[
i] != v[j]));
228 case DISTINCT_EXCEPT_0_DFA: {
229 static const DFA automaton = distinct_except_0_dfa(colors);
233 case DISTINCT_EXCEPT_0_COUNT: {
234 static const IntSetArgs counts = distinct_except_0_counts(colors,
std::max(width, height));
246 case NOT_ALL_EQUAL_NQ: {
250 case NOT_ALL_EQUAL_NAIVE: {
254 for (
int i = v.
size();
i--; )
255 for (
int j =
i; j--; )
256 disequalities <<
expr(*
this, v[
i] != v[j]);
260 case NOT_ALL_EQUAL_REIFIED: {
263 for (
int i = 0;
i < v.
size()-1; ++
i)
264 equalities <<
expr(*
this, v[
i] == v[
i+1]);
268 case NOT_ALL_EQUAL_NVALUES:
272 case NOT_ALL_EQUAL_COUNT:
276 case NOT_ALL_EQUAL_DFA: {
277 static const DFA automaton = not_all_equal_dfa(colors);
288 const unsigned int length = v1.
size();
290 case NO_MONOCHROME_DECOMPOSITION: {
292 for (
unsigned int i = 0;
i < length; ++
i) {
293 z[
i] = same_or_0(v1[
i], v2[i]);
295 distinct_except_0(z);
298 case NO_MONOCHROME_DFA: {
299 static const DFA automaton = no_monochrome_rectangle_dfa(colors);
301 for (
int i = length;
i--; ) {
361 opt(opt0), height(opt.height()), width(opt.width()), colors(opt.colors()),
362 x(*this, height*width, 1, colors),
363 max_color(*this, 1, colors)
366 max(*
this, x, max_color);
371 if (opt.
model() & MODEL_CORNERS) {
372 for (
unsigned int c1 = 0; c1 < width; ++c1) {
373 for (
unsigned int c2 = c1+1; c2 < width; ++c2) {
374 for (
unsigned int r1 = 0; r1 < height; ++r1) {
375 for (
unsigned int r2 = r1+1; r2 < height; ++r2) {
376 not_all_equal(
IntVarArgs() << m(c1,r1) << m(c1,r2) << m(c2,r1) << m(c2,r2));
386 if (opt.
model() & MODEL_ROWS) {
387 for (
unsigned int r1 = 0; r1 < height; ++r1) {
388 for (
unsigned int r2 = r1+1; r2 < height; ++r2) {
389 no_monochrome_rectangle(m.
row(r1), m.
row(r2));
393 if (opt.
model() & MODEL_COLUMNS) {
394 for (
unsigned int c1 = 0; c1 < width; ++c1) {
395 for (
unsigned int c2 = c1+1; c2 < width; ++c2) {
396 no_monochrome_rectangle(m.
col(c1), m.
col(c2));
404 if (opt.
symmetry() & SYMMETRY_MATRIX) {
405 for (
unsigned int r = 0;
r < height-1; ++
r) {
408 for (
unsigned int c = 0;
c < width-1; ++
c) {
414 if (opt.
symmetry() & SYMMETRY_VALUES) {
431 for (
unsigned int r = 0;
r < height; ++
r) {
433 for (
unsigned int c = 0;
c < width; ++
c) {
434 os << m(
c,
r) <<
" ";
439 os <<
"\tmax color: " << max_color << std::endl;
446 height(s.height), width(s.width), colors(s.colors) {
459 _height(
"height",
"Height of matrix", 8),
460 _width(
"width",
"Width of matrix", 8),
461 _size(
"size",
"If different from 0, used as both width and height", 0),
462 _colors(
"colors",
"Maximum number of colors", 4),
463 _not_all_equal(
"not-all-equal",
"How to implement the not all equals constraint (used in corners model)",
465 _same_or_0(
"same-or-0",
"How to implement the same or 0 constraint (used in the decomposed no monochrome rectangle constraint)",
467 _distinct_except_0(
"distinct-except-0",
"How to implement the distinct except 0 constraint (used in the decomposed no monochrome rectangle constraint)",
469 _no_monochrome_rectangle(
"no-monochrome-rectangle",
"How to implement no monochrome rectangle (used in the rows model)",
478 add(_distinct_except_0);
479 add(_no_monochrome_rectangle);
491 "both",
"Order both rows/columns and values");
498 "both",
"Use both rows and corners model");
501 "matrix",
"Use both rows and columns model");
525 "Use decompositions into same_or_0 and distinct_except_0.");
528 "Use DFA as direct implementation.");
537 opt.
parse(argc,argv);
539 Script::run<ColoredMatrix,DFS,ColoredMatrixOptions>(
opt);
541 Script::run<ColoredMatrix,BAB,ColoredMatrixOptions>(
opt);
563 const int start_state = 0;
564 const int not_equal_state = 2*colors+1;
565 const int final_state = 2*colors+2;
567 int n_transitions = colors*colors + 2*colors + 2;
569 int current_transition = 0;
572 for (
unsigned int color = 1; color <=
colors; ++color) {
573 trans[current_transition++] =
579 for (
unsigned int state = 1; state <=
colors; ++state) {
580 for (
unsigned int color = 1; color <=
colors; ++color) {
581 if (color == state) {
582 trans[current_transition++] =
585 trans[current_transition++] =
593 for (
unsigned int color = 1; color <=
colors; ++color) {
594 trans[current_transition++] =
599 trans[current_transition++] =
603 trans[current_transition++] =
606 int final_states[] = {final_state, -1};
608 DFA result(start_state, trans, final_states,
true);
615 TupleSet same_or_0_tuple_set(
unsigned int colors) {
618 for (
int j = 1; j <=
colors; ++j) {
620 result.
add({
i, j,
i});
622 result.
add({
i, j, 0});
630 DFA distinct_except_0_dfa(
unsigned int colors)
641 const int nstates = 1 <<
colors;
642 const int start_state = nstates-1;
645 int current_transition = 0;
647 for (
int state = nstates; state--; ) {
650 for (
unsigned int color = 1; color <=
colors; ++color) {
651 const unsigned int color_bit = (1 << (color-1));
652 if (state & color_bit) {
653 trans[current_transition++] =
660 int* final_states =
new int[nstates+1];
661 final_states[nstates] = -1;
662 for (
int i = nstates;
i--; ) {
666 DFA result(start_state, trans, final_states);
669 delete[] final_states;
674 DFA no_monochrome_rectangle_dfa(
unsigned int colors)
690 const int base_states = 1 <<
colors;
691 const int start_state = base_states-1;
692 const int nstates = base_states + colors*base_states;
695 int current_transition = 0;
697 for (
int state = base_states; state--; ) {
698 for (
unsigned int color = 1; color <=
colors; ++color) {
699 const unsigned int color_bit = (1 << (color-1));
700 const int color_remembered_state = state + color*base_states;
702 trans[current_transition++] =
705 for (
unsigned int next_color = 1; next_color <=
colors; ++next_color) {
706 if (next_color == color) {
708 if (state & color_bit) {
709 trans[current_transition++] =
713 trans[current_transition++] =
720 assert(current_transition <= nstates*colors+1);
722 int* final_states =
new int[base_states+1];
723 final_states[base_states] = -1;
724 for (
int i = base_states;
i--; ) {
728 DFA result(start_state, trans, final_states);
731 delete[] final_states;
736 IntSetArgs distinct_except_0_counts(
unsigned int colors,
unsigned int size)
740 result[0] =
IntSet(0, size);
742 for (
unsigned int i = 1;
i <=
colors; ++
i) {
750 DFA not_all_equal_dfa(
unsigned int colors)
760 const int nstates = 1 + colors + 1;
761 const int start_state = 0;
762 const int final_state = nstates-1;
765 int current_transition = 0;
768 for (
unsigned int color = 1; color <=
colors; ++color) {
769 trans[current_transition++] =
DFA::Transition(start_state, color, color);
773 for (
unsigned int state = 1; state <=
colors; ++state) {
774 for (
unsigned int color = 1; color <=
colors; ++color) {
775 if (state == color) {
778 trans[current_transition++] =
DFA::Transition(state, color, final_state);
784 for (
unsigned int color = 1; color <=
colors; ++color) {
785 trans[current_transition++] =
DFA::Transition(final_state, color, final_state);
790 int final_states[] = {final_state, -1};
792 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)
const ColoredMatrixOptions & opt
Options for model.
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.
Gecode::IntArgs i({1, 2, 3, 4})
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.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
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.
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
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.
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.
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
Gecode::IntArgs v1({Gecode::Int::Limits::min+4, 0, 1, Gecode::Int::Limits::max})
IntVar max_color
Maximum color used.
unsigned int width(void) const
Return width.
ColoredMatrixOptions(const char *n)
Initialize options for example with name n.
Gecode::IntArgs v2({Gecode::Int::Limits::min, 0, 1, Gecode::Int::Limits::max-4})
#define GECODE_NEVER
Assert that this command is never executed.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Use model on pairs of columns.
Use count for distinct except 0.
Use naive reification for implemeting not all equals.