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);
192 switch (
opt.same_or_0()) {
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);
223 switch (
opt.distinct_except_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));
249 switch (
opt.not_all_equal()) {
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();
293 switch (
opt.no_monochrome_rectangle()) {
294 case NO_MONOCHROME_DECOMPOSITION: {
296 for (
unsigned int i = 0;
i < length; ++
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.");
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);
622 for (
unsigned int i = 1;
i <= colors; ++
i) {
623 for (
unsigned int j = 1; j <= colors; ++j) {
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;
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;
747 for (
unsigned int i = 1;
i <= colors; ++
i) {
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);