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)
622 for (
unsigned int i = 1;
i <=
colors; ++
i) {
623 for (
unsigned int j = 1; j <=
colors; ++j) {
635 DFA distinct_except_0_dfa(
unsigned int colors)
646 const int nstates = 1 <<
colors;
647 const int start_state = nstates-1;
650 int current_transition = 0;
652 for (
int state = nstates; state--; ) {
655 for (
unsigned int color = 1; color <=
colors; ++color) {
656 const unsigned int color_bit = (1 << (color-1));
657 if (state & color_bit) {
658 trans[current_transition++] =
665 int* final_states =
new int[nstates+1];
666 final_states[nstates] = -1;
667 for (
int i = nstates;
i--; ) {
671 DFA result(start_state, trans, final_states);
674 delete[] final_states;
679 DFA no_monochrome_rectangle_dfa(
unsigned int colors)
695 const int base_states = 1 <<
colors;
696 const int start_state = base_states-1;
697 const int nstates = base_states + colors*base_states;
700 int current_transition = 0;
702 for (
int state = base_states; state--; ) {
703 for (
unsigned int color = 1; color <=
colors; ++color) {
704 const unsigned int color_bit = (1 << (color-1));
705 const int color_remembered_state = state + color*base_states;
707 trans[current_transition++] =
710 for (
unsigned int next_color = 1; next_color <=
colors; ++next_color) {
711 if (next_color == color) {
713 if (state & color_bit) {
714 trans[current_transition++] =
718 trans[current_transition++] =
725 assert(current_transition <= nstates*colors+1);
727 int* final_states =
new int[base_states+1];
728 final_states[base_states] = -1;
729 for (
int i = base_states;
i--; ) {
733 DFA result(start_state, trans, final_states);
736 delete[] final_states;
741 IntSetArgs distinct_except_0_counts(
unsigned int colors,
unsigned int size)
745 result[0] =
IntSet(0, size);
747 for (
unsigned int i = 1;
i <=
colors; ++
i) {
755 DFA not_all_equal_dfa(
unsigned int colors)
765 const int nstates = 1 + colors + 1;
766 const int start_state = 0;
767 const int final_state = nstates-1;
770 int current_transition = 0;
773 for (
unsigned int color = 1; color <=
colors; ++color) {
774 trans[current_transition++] =
DFA::Transition(start_state, color, color);
778 for (
unsigned int state = 1; state <=
colors; ++state) {
779 for (
unsigned int color = 1; color <=
colors; ++color) {
780 if (state == color) {
783 trans[current_transition++] =
DFA::Transition(state, color, final_state);
789 for (
unsigned int color = 1; color <=
colors; ++color) {
790 trans[current_transition++] =
DFA::Transition(final_state, color, final_state);
795 int final_states[] = {final_state, -1};
797 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.
virtual Space * copy(bool share)
Copy during cloning.
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, 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.
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.
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)
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Use direct constraint for implemeting not all equals.
Gecode::FloatVal c(-8, 8)
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.
Deterministic finite automaton (DFA)
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
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 .
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)
Driver::StringOption _search
Search options.
Use model on pairs of rows.
Driver::StringOption _symmetry
General symmetry options.
Passing integer variables.
Passing integer arguments.
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.
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.
Gecode::IntArgs v1(4, Gecode::Int::Limits::min+4, 0, 1, Gecode::Int::Limits::max)
int same_or_0(void) const
Return how to implement same or 0.
Node * x
Pointer to corresponding Boolean expression node.
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(bool share, ColoredMatrix &s)
Constructor for cloning s.
Matrix-interface for arrays.
const unsigned int colors
Number of colors to use.
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.
void add(const IntArgs &tuple)
Add tuple to tuple set.
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
#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.