70 void parse(
int& argc,
char* argv[]) {
76 if (_size.value() == 0U)
77 return static_cast<int>(_height.value());
79 return static_cast<int>(_size.value());
83 if (_size.value() == 0U)
84 return static_cast<int>(_width.value());
86 return static_cast<int>(_size.value());
89 int colors(
void)
const {
return static_cast<int>(_colors.value()); }
93 int same_or_0(
void)
const {
return _same_or_0.value(); }
98 return _no_monochrome_rectangle.value();
188 switch (
opt.same_or_0()) {
211 return IntVar(*
this, 0, 0);
219 switch (
opt.distinct_except_0()) {
221 for (
int i = v.size(); i--; ) {
223 for (
int j = i; j--; ) {
224 rel(*
this, viIsZero || (v[i] != v[j]));
245 switch (
opt.not_all_equal()) {
254 for (
int i = v.size(); i--; )
255 for (
int j = i; j--; )
256 disequalities <<
expr(*
this, v[i] != v[j]);
263 for (
int i = 0; i < v.size()-1; ++i)
264 equalities <<
expr(*
this, v[i] == v[i+1]);
288 const int length = v1.
size();
289 switch (
opt.no_monochrome_rectangle()) {
292 for (
int i = 0; i < length; ++i) {
301 for (
int i = length; i--; ) {
372 for (
int c1 = 0; c1 <
width; ++c1) {
373 for (
int c2 = c1+1; c2 <
width; ++c2) {
374 for (
int r1 = 0; r1 <
height; ++r1) {
375 for (
int r2 = r1+1; r2 <
height; ++r2) {
387 for (
int r1 = 0; r1 <
height; ++r1) {
388 for (
int r2 = r1+1; r2 <
height; ++r2) {
394 for (
int c1 = 0; c1 <
width; ++c1) {
395 for (
int c2 = c1+1; c2 <
width; ++c2) {
408 for (
int c = 0; c <
width-1; ++c) {
433 for (
int c = 0; c <
width; ++c) {
434 os << m(c,
r) <<
" ";
439 os <<
"\tmax color: " <<
max_color << std::endl;
447 x.update(*
this, s.
x);
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);
548 DFA same_or_0_dfa(
int colors)
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;
570 int current_transition = 0;
573 for (
int color = 1; color <= colors; ++color) {
574 trans[current_transition++] =
580 for (
int state = 1; state <= colors; ++state) {
581 for (
int color = 1; color <= colors; ++color) {
582 if (color == state) {
583 trans[current_transition++] =
586 trans[current_transition++] =
594 for (
int color = 1; color <= colors; ++color) {
595 trans[current_transition++] =
600 trans[current_transition++] =
604 trans[current_transition++] =
607 int final_states[] = {final_state, -1};
609 DFA result(start_state, trans, final_states,
true);
616 TupleSet same_or_0_tuple_set(
int colors) {
618 for (
int i = 1;
i <= colors; ++
i) {
619 for (
int j = 1; j <= colors; ++j) {
621 result.add({
i, j,
i});
623 result.add({
i, j, 0});
631 DFA distinct_except_0_dfa(
int colors)
642 const int nstates = 1 << colors;
643 const int start_state = nstates-1;
647 int current_transition = 0;
649 for (
int state = nstates; state--; ) {
652 for (
int color = 1; color <= colors; ++color) {
653 const int color_bit = (1 << (color-1));
654 if (state & color_bit) {
655 trans[current_transition++] =
662 int* final_states =
new int[nstates+1];
663 final_states[nstates] = -1;
664 for (
int i = nstates;
i--; ) {
668 DFA result(start_state, trans, final_states);
671 delete[] final_states;
676 DFA no_monochrome_rectangle_dfa(
int colors)
692 const int base_states = 1 << colors;
693 const int start_state = base_states-1;
694 const int nstates = base_states + colors*base_states;
697 int current_transition = 0;
699 for (
int state = base_states; state--; ) {
700 for (
int color = 1; color <= colors; ++color) {
701 const int color_bit = (1 << (color-1));
702 const int color_remembered_state = state + color*base_states;
704 trans[current_transition++] =
707 for (
int next_color = 1; next_color <= colors; ++next_color) {
708 if (next_color == color) {
710 if (state & color_bit) {
711 trans[current_transition++] =
715 trans[current_transition++] =
722 assert(current_transition <= nstates*colors+1);
724 int* final_states =
new int[base_states+1];
725 final_states[base_states] = -1;
726 for (
int i = base_states;
i--; ) {
730 DFA result(start_state, trans, final_states);
733 delete[] final_states;
738 IntSetArgs distinct_except_0_counts(
int colors,
int size)
742 result[0] =
IntSet(0, size);
744 for (
int i = 1;
i <= colors; ++
i) {
752 DFA not_all_equal_dfa(
int colors)
762 const int nstates = 1 + colors + 1;
763 const int start_state = 0;
764 const int final_state = nstates-1;
767 int current_transition = 0;
770 for (
int color = 1; color <= colors; ++color) {
771 trans[current_transition++] =
DFA::Transition(start_state, color, color);
775 for (
int state = 1; state <= colors; ++state) {
776 for (
int color = 1; color <= colors; ++color) {
777 if (state == color) {
780 trans[current_transition++] =
DFA::Transition(state, color, final_state);
786 for (
int color = 1; color <= colors; ++color) {
787 trans[current_transition++] =
DFA::Transition(final_state, color, final_state);
792 int final_states[] = {final_state, -1};
794 DFA result(start_state, trans, final_states);
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
int colors(void) const
Return number of colors.
int distinct_except_0(void) const
Return how to implement distinct except 0.
int same_or_0(void) const
Return how to implement same or 0.
int height(void) const
Return height.
int width(void) const
Return width.
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
ColoredMatrixOptions(const char *n)
Initialize options for example with name n.
int not_all_equal(void) const
Return how to implement not all equals.
Example: Colored matrix example.
IntVar same_or_0(const IntVar &a, const IntVar &b)
int main(int argc, char *argv[])
Main-function.
void distinct_except_0(const IntVarArgs &v)
const ColoredMatrixOptions & opt
Options for model.
DFA not_all_equal_dfa(int colors)
DFA no_monochrome_rectangle_dfa(int colors)
IntSetArgs distinct_except_0_counts(int colors, int size)
virtual void print(std::ostream &os) const
Print solution.
@ SYMMETRY_MATRIX
Order rows and columns of matrix.
@ SYMMETRY_NONE
No symmetry breaking.
@ SYMMETRY_VALUES
Order value occurences.
const int colors
Number of colors to use.
void not_all_equal(const IntVarArgs &v)
ColoredMatrix(ColoredMatrix &s)
Constructor for cloning s.
void no_monochrome_rectangle(IntVarArgs v1, IntVarArgs v2)
@ DISTINCT_EXCEPT_0_DFA
Use dfa for distinct except 0.
@ DISTINCT_EXCEPT_0_COUNT
Use count for distinct except 0.
@ DISTINCT_EXCEPT_0_REIFIED
Use reification for distinct except 0.
@ SEARCH_DFS
Find solution.
@ SEARCH_BAB
Find optimal solution.
virtual Space * copy(void)
Copy during cloning.
@ NO_MONOCHROME_DFA
Use dfa for no monochrome rectangle.
@ NO_MONOCHROME_DECOMPOSITION
Use decomposition for no monochrome rectangle.
DFA distinct_except_0_dfa(int colors)
@ MODEL_COLUMNS
Use model on pairs of columns.
@ MODEL_ROWS
Use model on pairs of rows.
@ MODEL_CORNERS
Use model on corner combinations.
TupleSet same_or_0_tuple_set(int colors)
@ SAME_OR_0_DFA
Use dfa for same or 0.
@ SAME_OR_0_TUPLE_SET
Use tuple set for same or 0.
@ SAME_OR_0_REIFIED
Use reification for same or 0.
virtual IntVar cost(void) const
Return cost.
IntVarArray x
Array for matrix variables.
ColoredMatrix(const ColoredMatrixOptions &opt0)
Actual model.
DFA same_or_0_dfa(int colors)
const int width
Width of matrix.
IntVar max_color
Maximum color used.
@ NOT_ALL_EQUAL_NQ
Use direct constraint for implemeting not all equals.
@ NOT_ALL_EQUAL_REIFIED
Use reification for implemeting not all equals.
@ NOT_ALL_EQUAL_NVALUES
Use nvalues for implementing not all equals.
@ NOT_ALL_EQUAL_NAIVE
Use naive reification for implemeting not all equals.
@ NOT_ALL_EQUAL_COUNT
Use count for implementing not all equals.
@ NOT_ALL_EQUAL_DFA
Use dfa for implementing not all equals.
const int height
Height of matrix.
int size(void) const
Return size of array (number of elements)
void add(Driver::BaseOption &o)
Add new option o.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Passing Boolean variables.
Boolean integer variables.
Specification of a DFA transition.
Deterministic finite automaton (DFA)
static void run(const Options &opt, Script *s=NULL)
String-valued option (integer value defined by strings)
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Passing integer variables.
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Slice< A > row(int r) const
Access row r.
Driver::StringOption _model
General model options.
Driver::StringOption _search
Search options.
Options(const char *s)
Initialize options for script with name s.
Driver::StringOption _symmetry
General symmetry options.
Class represeting a set of tuples.
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel=IPL_DEF)
Post propagator that s precedes t in x.
Gecode toplevel namespace
ArgArray< IntSet > IntSetArgs
Passing set arguments.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType r
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
IntValBranch INT_VAL_MIN(void)
Select smallest value.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void nvalues(Home home, const IntVarArgs &x, IntRelType irt, int y, IntPropLevel ipl=IPL_DEF)
Post propagator for .
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Gecode::IntArgs i({1, 2, 3, 4})
#define GECODE_NEVER
Assert that this command is never executed.