Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
colored-matrix.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Copyright:
7  * Mikael Lagerkvist, 2012
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/driver.hh>
35 #include <gecode/int.hh>
36 #include <gecode/minimodel.hh>
37 
38 #include <fstream>
39 
40 using namespace Gecode;
41 
46 class ColoredMatrixOptions : public Options {
47 private:
57  Driver::StringOption _not_all_equal;
59  Driver::StringOption _same_or_0;
61  Driver::StringOption _distinct_except_0;
63  Driver::StringOption _no_monochrome_rectangle;
64 
65 public:
67  ColoredMatrixOptions(const char* n);
68 
70  void parse(int& argc, char* argv[]) {
71  Options::parse(argc,argv);
72  }
73 
75  unsigned int height(void) const {
76  if (_size.value() == 0)
77  return _height.value();
78  else
79  return _size.value();
80  }
82  unsigned int width(void) const {
83  if (_size.value() == 0)
84  return _width.value();
85  else
86  return _size.value();
87  }
89  unsigned int colors(void) const { return _colors.value(); }
91  int not_all_equal(void) const { return _not_all_equal.value(); }
93  int same_or_0(void) const { return _same_or_0.value(); }
95  int distinct_except_0(void) const { return _distinct_except_0.value(); }
97  int no_monochrome_rectangle(void) const {
98  return _no_monochrome_rectangle.value();
99  }
100 };
101 
102 namespace {
111 
118  DFA same_or_0_dfa(unsigned int colors);
119 
126  TupleSet same_or_0_tuple_set(unsigned int colors);
127 
130  DFA distinct_except_0_dfa(unsigned int colors);
131 
134  DFA no_monochrome_rectangle_dfa(unsigned int colors);
135 
138  IntSetArgs distinct_except_0_counts(unsigned int colors, unsigned int size);
139 
142  DFA not_all_equal_dfa(unsigned int colors);
143 
145 }
146 
165 protected:
170  const unsigned int height;
171  const unsigned int width;
172  const unsigned int colors;
173 
174 
178  IntVarArray x;
183 
186  IntVar same_or_0(const IntVar& a, const IntVar& b)
187  {
188  switch (opt.same_or_0()) {
189  case SAME_OR_0_REIFIED: {
190  IntVar result(*this, 0, colors);
191  BoolVar same = expr(*this, (a == b));
192  rel(*this, result, IRT_EQ, a, same);
193  // Redundant (implied by previous), but improves efficiency
194  rel(*this, result, IRT_NQ, 0, same);
195  return result;
196  }
197  case SAME_OR_0_TUPLE_SET: {
198  static TupleSet table = same_or_0_tuple_set(colors);
199  IntVar result(*this, 0, colors);
200  extensional(*this, IntVarArgs() << a << b << result, table);
201  return result;
202  }
203  case SAME_OR_0_DFA: {
204  static const DFA automaton = same_or_0_dfa(colors);
205  IntVar result(*this, 0, colors);
206  extensional(*this, IntVarArgs() << a << b << result, automaton);
207  return result;
208  }
209  default:
210  GECODE_NEVER;
211  return IntVar(*this, 0, 0);
212  }
213  }
214 
218  {
219  switch (opt.distinct_except_0()) {
220  case DISTINCT_EXCEPT_0_REIFIED:
221  for (int i = v.size(); i--; ) {
222  BoolVar viIsZero = expr(*this, v[i] == 0);
223  for (int j = i; j--; ) {
224  rel(*this, viIsZero || (v[i] != v[j]));
225  }
226  }
227  break;
228  case DISTINCT_EXCEPT_0_DFA: {
229  static const DFA automaton = distinct_except_0_dfa(colors);
230  extensional(*this, v, automaton);
231  break;
232  }
233  case DISTINCT_EXCEPT_0_COUNT: {
234  static const IntSetArgs counts = distinct_except_0_counts(colors, std::max(width, height));
235  count(*this, v, counts, opt.ipl());
236  break;
237  }
238  }
239  }
240 
244  {
245  switch (opt.not_all_equal()) {
246  case NOT_ALL_EQUAL_NQ: {
247  rel(*this, v, IRT_NQ);
248  break;
249  }
250  case NOT_ALL_EQUAL_NAIVE: {
251  // At least one pair must be different.
252  // Bad decomposition since too many disjuncts are created.
253  BoolVarArgs disequalities;
254  for (int i = v.size(); i--; )
255  for (int j = i; j--; )
256  disequalities << expr(*this, v[i] != v[j]);
257  rel(*this, BOT_OR, disequalities, 1);
258  break;
259  }
260  case NOT_ALL_EQUAL_REIFIED: {
261  // It must not be the case that all are equal
262  BoolVarArgs equalities;
263  for (int i = 0; i < v.size()-1; ++i)
264  equalities << expr(*this, v[i] == v[i+1]);
265  rel(*this, BOT_AND, equalities, 0);
266  break;
267  }
268  case NOT_ALL_EQUAL_NVALUES:
269  // More than one number
270  nvalues(*this, v, IRT_GR, 1);
271  break;
272  case NOT_ALL_EQUAL_COUNT:
273  // No number in all positions
274  count(*this, v, IntSet(0, v.size()-1), IntArgs::create(colors, 1), opt.ipl());
275  break;
276  case NOT_ALL_EQUAL_DFA: {
277  static const DFA automaton = not_all_equal_dfa(colors);
278  extensional(*this, v, automaton);
279  break;
280  }
281  }
282  }
283 
288  const unsigned int length = v1.size();
289  switch (opt.no_monochrome_rectangle()) {
290  case NO_MONOCHROME_DECOMPOSITION: {
291  IntVarArgs z(length);
292  for (unsigned int i = 0; i < length; ++i) {
293  z[i] = same_or_0(v1[i], v2[i]);
294  }
295  distinct_except_0(z);
296  break;
297  }
298  case NO_MONOCHROME_DFA: {
299  static const DFA automaton = no_monochrome_rectangle_dfa(colors);
300  IntVarArgs z(2*length);
301  for (int i = length; i--; ) {
302  z[2*i + 0] = v1[i];
303  z[2*i + 1] = v2[i];
304  }
305  extensional(*this, z, automaton);
306  break;
307  }
308  }
309  }
310 
311 
312 public:
314  enum {
317  };
319  enum {
320  SYMMETRY_NONE = 0,
321  SYMMETRY_MATRIX = 1,
322  SYMMETRY_VALUES = 2,
323  };
325  enum {
326  MODEL_CORNERS = 1,
327  MODEL_ROWS = 2,
328  MODEL_COLUMNS = 4,
329  };
331  enum {
338  };
340  enum {
344  };
346  enum {
350  };
352  enum {
355  };
356 
357 
360  : IntMinimizeScript(opt0),
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)
364  {
365 
366  max(*this, x, max_color);
367 
368  Matrix<IntVarArray> m(x, width, height);
369 
370  // For each pair of columns and rows, the intersections may not be equal.
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));
377  }
378  }
379  }
380  }
381  }
382  // Given two rows/columns, construct variables representing if
383  // the corresponding places are equal (and if so, what value).
384  // For the new values, no non-zero value may appear more than
385  // once.
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));
390  }
391  }
392  }
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));
397  }
398  }
399  }
400 
401  // Symmetry breaking constraints.
402  {
403  // Lexical order for all columns and rows (all are interchangable)
404  if (opt.symmetry() & SYMMETRY_MATRIX) {
405  for (unsigned int r = 0; r < height-1; ++r) {
406  rel(*this, m.row(r), IRT_LE, m.row(r+1));
407  }
408  for (unsigned int c = 0; c < width-1; ++c) {
409  rel(*this, m.col(c), IRT_LE, m.col(c+1));
410  }
411  }
412 
413  // Value precedence. Compatible with row/column ordering
414  if (opt.symmetry() & SYMMETRY_VALUES) {
415  precede(*this, x, IntArgs::create(colors, 1));
416  }
417  }
418 
420  }
421 
423  virtual IntVar cost(void) const {
424  return max_color;
425  }
426 
428  virtual void
429  print(std::ostream& os) const {
430  Matrix<IntVarArray> m(x, width, height);
431  for (unsigned int r = 0; r < height; ++r) {
432  os << "\t";
433  for (unsigned int c = 0; c < width; ++c) {
434  os << m(c, r) << " ";
435  }
436  os << std::endl;
437  }
438  os << std::endl;
439  os << "\tmax color: " << max_color << std::endl;
440  os << std::endl;
441  }
442 
445  : IntMinimizeScript(s), opt(s.opt),
446  height(s.height), width(s.width), colors(s.colors) {
447  x.update(*this, s.x);
448  max_color.update(*this, s.max_color);
449  }
451  virtual Space*
452  copy(void) {
453  return new ColoredMatrix(*this);
454  }
455 };
456 
458  : Options(n),
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)",
464  ColoredMatrix::NOT_ALL_EQUAL_NQ),
465  _same_or_0("same-or-0", "How to implement the same or 0 constraint (used in the decomposed no monochrome rectangle constraint)",
466  ColoredMatrix::SAME_OR_0_DFA),
467  _distinct_except_0("distinct-except-0", "How to implement the distinct except 0 constraint (used in the decomposed no monochrome rectangle constraint)",
468  ColoredMatrix::DISTINCT_EXCEPT_0_DFA),
469  _no_monochrome_rectangle("no-monochrome-rectangle", "How to implement no monochrome rectangle (used in the rows model)",
470  ColoredMatrix::NO_MONOCHROME_DFA)
471 {
472  add(_height);
473  add(_width);
474  add(_size);
475  add(_colors);
476  add(_not_all_equal);
477  add(_same_or_0);
478  add(_distinct_except_0);
479  add(_no_monochrome_rectangle);
480 
481  // Add search options
482  _search.add(ColoredMatrix::SEARCH_DFS, "dfs", "Find a solution.");
483  _search.add(ColoredMatrix::SEARCH_BAB, "bab", "Find an optimal solution.");
485 
486  // Add symmetry options
487  _symmetry.add(ColoredMatrix::SYMMETRY_NONE, "none", "Don't use symmetry breaking.");
488  _symmetry.add(ColoredMatrix::SYMMETRY_MATRIX, "matrix", "Order matrix rows and columns");
489  _symmetry.add(ColoredMatrix::SYMMETRY_VALUES, "values", "Order values");
491  "both", "Order both rows/columns and values");
493 
494  // Add model options
495  _model.add(ColoredMatrix::MODEL_CORNERS, "corner", "Use direct corners model with not-all-equal constraints.");
496  _model.add(ColoredMatrix::MODEL_ROWS, "rows", "Use model on pairs of rows (same_or_0 and distinct_except_0 constraints).");
498  "both", "Use both rows and corners model");
499  _model.add(ColoredMatrix::MODEL_COLUMNS, "columns", "Use model on pairs of columns (same_or_0 and distinct_except_0 constraints).");
501  "matrix", "Use both rows and columns model");
503 
504  // Add not all equal variants
505  _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NQ, "nq", "Use nq constraint.");
506  _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NAIVE, "naive", "Use naive reified decomposition.");
507  _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_REIFIED, "reified", "Use reified decomposition.");
508  _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NVALUES, "nvalues", "Use nvalues.");
509  _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_COUNT, "count", "Use count.");
510  _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_DFA, "dfa", "Use dfa.");
511 
512  // Add same or 0 variants
513  _same_or_0.add(ColoredMatrix::SAME_OR_0_REIFIED, "reified", "Use reified decomposition.");
514  _same_or_0.add(ColoredMatrix::SAME_OR_0_TUPLE_SET, "tuple-set", "Use tuple set representation.");
515  _same_or_0.add(ColoredMatrix::SAME_OR_0_DFA, "dfa", "Use dfa representation.");
516 
517  // Add distinct except 0 variants
518  _distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_REIFIED, "reified", "Use reified decomposition.");
519  _distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_DFA, "dfa", "Use dfa decomposition.");
520  _distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_COUNT, "count", "Use global cardinality.");
521 
522  // Add no monochrome rectangle variants
523  _no_monochrome_rectangle.add(ColoredMatrix::NO_MONOCHROME_DECOMPOSITION,
524  "decompositions",
525  "Use decompositions into same_or_0 and distinct_except_0.");
526  _no_monochrome_rectangle.add(ColoredMatrix::NO_MONOCHROME_DFA,
527  "dfa",
528  "Use DFA as direct implementation.");
529 }
530 
534 int
535 main(int argc, char* argv[]) {
536  ColoredMatrixOptions opt("Colored matrix");
537  opt.parse(argc,argv);
538  if (opt.search() == ColoredMatrix::SEARCH_DFS) {
539  Script::run<ColoredMatrix,DFS,ColoredMatrixOptions>(opt);
540  } else {
541  Script::run<ColoredMatrix,BAB,ColoredMatrixOptions>(opt);
542  }
543  return 0;
544 }
545 
546 
547 namespace {
548  DFA same_or_0_dfa(unsigned int colors)
549  {
550  /* DFA over variable sequences (x,y,z) where z equals x/y if x and
551  * y are equal, and z equals 0 otherwise.
552  *
553  * DFA is constructed to contain paths
554  * start -- c --> node -- c --> node' -- c --> end
555  * for all colors c representing the case when x and y
556  * are equal.
557  *
558  * For the cases where x and y are non-equal (c and c'), paths
559  * start -- c --> node -- c' --> not-equal -- 0 --> end
560  * are added.
561  */
562 
563  const int start_state = 0;
564  const int not_equal_state = 2*colors+1;
565  const int final_state = 2*colors+2;
566 
567  int n_transitions = colors*colors + 2*colors + 2;
568  DFA::Transition* trans = new DFA::Transition[n_transitions];
569  int current_transition = 0;
570 
571  // From start state
572  for (unsigned int color = 1; color <= colors; ++color) {
573  trans[current_transition++] =
574  DFA::Transition(start_state, color, color);
575  }
576 
577  // From first level states (indices [1..color])
578  // To second-level if same color, otherwise to not_equal_state
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++] =
583  DFA::Transition(state, color, colors+state);
584  } else {
585  trans[current_transition++] =
586  DFA::Transition(state, color, not_equal_state);
587  }
588  }
589  }
590 
591  // From second level states (indices [colors+1..colors+colors])
592  // To final state with the same color
593  for (unsigned int color = 1; color <= colors; ++color) {
594  trans[current_transition++] =
595  DFA::Transition(colors+color, color, final_state);
596  }
597 
598  // From not equal state to final state
599  trans[current_transition++] =
600  DFA::Transition(not_equal_state, 0, final_state);
601 
602  // End sentinel
603  trans[current_transition++] =
604  DFA::Transition(-1, 0, -1);
605 
606  int final_states[] = {final_state, -1};
607 
608  DFA result(start_state, trans, final_states, true);
609 
610  delete[] trans;
611 
612  return result;
613  }
614 
615  TupleSet same_or_0_tuple_set(unsigned int colors) {
616  TupleSet result(3);
617  for (int i = 1; i <= colors; ++i) {
618  for (int j = 1; j <= colors; ++j) {
619  if (i == j) {
620  result.add({i, j, i});
621  } else {
622  result.add({i, j, 0});
623  }
624  }
625  }
626  result.finalize();
627  return result;
628  }
629 
630  DFA distinct_except_0_dfa(unsigned int colors)
631  {
632  /* DFA for a sequence that may use each color only once (and all
633  * others are zero).
634  *
635  * For n colors, 2^n nodes are used. For each node, if bit b is one, then
636  * that color has not been used yet. All nodes have self-loops for zero, and
637  * edges for still usable colors to the node with the corresponding bit un-set.
638  * All nodes are final nodes.
639  */
640 
641  const int nstates = 1 << colors;
642  const int start_state = nstates-1;
643 
644  DFA::Transition* trans = new DFA::Transition[nstates*colors + 1];
645  int current_transition = 0;
646 
647  for (int state = nstates; state--; ) {
648  trans[current_transition++] = DFA::Transition(state, 0, state);
649 
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++] =
654  DFA::Transition(state, color, state & ~color_bit);
655  }
656  }
657  }
658  trans[current_transition++] = DFA::Transition(-1, 0, -1);
659 
660  int* final_states = new int[nstates+1];
661  final_states[nstates] = -1;
662  for (int i = nstates; i--; ) {
663  final_states[i] = i;
664  }
665 
666  DFA result(start_state, trans, final_states);
667 
668  delete[] trans;
669  delete[] final_states;
670 
671  return result;
672  }
673 
674  DFA no_monochrome_rectangle_dfa(unsigned int colors)
675  {
676  /* DFA for a sequence of pairs, where each monochromatic pair may
677  * only appear once.
678  *
679  * For n colors, there are 2^n base states representing which
680  * monochromatic pairs are still available. For each base state s,
681  * the color seen goes to a new intermediate state. A different
682  * color will go back to state s. Seeing the same color will move
683  * to the next base state with that color combination removed (if
684  * it is still allowed).
685  *
686  * In essence, this DFA represents the combination of same_or_0
687  * and distinct_except_0 as a single constraint.
688  */
689 
690  const int base_states = 1 << colors;
691  const int start_state = base_states-1;
692  const int nstates = base_states + colors*base_states;
693 
694  DFA::Transition* trans = new DFA::Transition[nstates*colors + 1];
695  int current_transition = 0;
696 
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;
701 
702  trans[current_transition++] =
703  DFA::Transition(state, color, color_remembered_state);
704 
705  for (unsigned int next_color = 1; next_color <= colors; ++next_color) {
706  if (next_color == color) {
707  // Two equal adjacent, only transition if color still allowed
708  if (state & color_bit) {
709  trans[current_transition++] =
710  DFA::Transition(color_remembered_state, color, state & ~color_bit);
711  }
712  } else {
713  trans[current_transition++] =
714  DFA::Transition(color_remembered_state, next_color, state);
715  }
716  }
717  }
718  }
719  trans[current_transition++] = DFA::Transition(-1, 0, -1);
720  assert(current_transition <= nstates*colors+1);
721 
722  int* final_states = new int[base_states+1];
723  final_states[base_states] = -1;
724  for (int i = base_states; i--; ) {
725  final_states[i] = i;
726  }
727 
728  DFA result(start_state, trans, final_states);
729 
730  delete[] trans;
731  delete[] final_states;
732 
733  return result;
734  }
735 
736  IntSetArgs distinct_except_0_counts(unsigned int colors, unsigned int size)
737  {
738  IntSetArgs result(colors+1);
739 
740  result[0] = IntSet(0, size);
741 
742  for (unsigned int i = 1; i <= colors; ++i) {
743  result[i] = IntSet(0, 1);
744  }
745 
746  return result;
747  }
748 
749 
750  DFA not_all_equal_dfa(unsigned int colors)
751  {
752  /* DFA for not all equal.
753  *
754  * From the start state, there is a transition for each color to
755  * that colors state. As long as the same color is seen, the
756  * automaton stays in that state. If a different color is seen,
757  * then it goes to the accepting state.
758  */
759 
760  const int nstates = 1 + colors + 1;
761  const int start_state = 0;
762  const int final_state = nstates-1;
763 
764  DFA::Transition* trans = new DFA::Transition[2*colors + colors*colors + 1];
765  int current_transition = 0;
766 
767  // Each color to its own state
768  for (unsigned int color = 1; color <= colors; ++color) {
769  trans[current_transition++] = DFA::Transition(start_state, color, color);
770  }
771 
772  // Each colors state loops on itself, and goes to final on all others
773  for (unsigned int state = 1; state <= colors; ++state) {
774  for (unsigned int color = 1; color <= colors; ++color) {
775  if (state == color) {
776  trans[current_transition++] = DFA::Transition(state, color, state);
777  } else {
778  trans[current_transition++] = DFA::Transition(state, color, final_state);
779  }
780  }
781  }
782 
783  // Loop on all colors in final state
784  for (unsigned int color = 1; color <= colors; ++color) {
785  trans[current_transition++] = DFA::Transition(final_state, color, final_state);
786  }
787 
788  trans[current_transition++] = DFA::Transition(-1, 0, -1);
789 
790  int final_states[] = {final_state, -1};
791 
792  DFA result(start_state, trans, final_states);
793 
794  delete[] trans;
795 
796  return result;
797  }
798 
799 }
800 
801 
802 // STATISTICS: example-any
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 .
Definition: array.hpp:76
void value(int v)
Set default value to v.
Definition: options.hpp:58
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.
Definition: matrix.hpp:183
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:155
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
No symmetry breaking.
Find optimal solution.
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.
Definition: branch.cpp:39
Use dfa for same or 0.
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
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.
Definition: array.hpp:995
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 .
Definition: arithmetic.cpp:49
void add(int v, const char *o, const char *h=NULL)
Add option value for value v, string o, and help text h.
Definition: options.cpp:138
Use reification for distinct except 0.
IntVar same_or_0(const IntVar &a, const IntVar &b)
Conjunction.
Definition: int.hh:951
Use model on corner combinations.
Use count for implementing not all equals.
Integer variable array.
Definition: int.hh:763
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Greater ( )
Definition: int.hh:931
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
Use dfa for no monochrome rectangle.
void add(Driver::BaseOption &o)
Add new option o.
Definition: options.cpp:466
void value(unsigned int v)
Set default value to v.
Definition: options.hpp:91
Driver::StringOption _model
General model options.
Definition: driver.hh:370
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)
Definition: int.hh:2048
const ColoredMatrixOptions & opt
Options for model.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
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 .
Definition: nvalues.cpp:40
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:186
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.
Definition: val.hpp:55
Specification of a DFA transition.
Definition: int.hh:2057
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.
Unsigned integer option.
Definition: driver.hh:229
void distinct_except_0(const IntVarArgs &v)
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
Driver::StringOption _search
Search options.
Definition: driver.hh:382
ColoredMatrixOptions.
Use model on pairs of rows.
Less ( )
Definition: int.hh:929
Integer sets.
Definition: int.hh:174
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Driver::StringOption _symmetry
General symmetry options.
Definition: driver.hh:371
Disjunction.
Definition: int.hh:952
Passing integer variables.
Definition: int.hh:656
Passing Boolean variables.
Definition: int.hh:712
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition: array.hpp:1899
void search(int v)
Set default search value.
Definition: options.hpp:270
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:627
Boolean integer variables.
Definition: int.hh:512
Order value occurences.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:540
const int v[7]
Definition: distinct.cpp:259
Class represeting a set of tuples.
Definition: int.hh:2190
const unsigned int width
Width of matrix.
String-valued option (integer value defined by strings)
Definition: driver.hh:174
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition: tiebreak.hpp:80
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.
Definition: var.hpp:206
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.
Definition: matrix.hpp:177
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.
Definition: precede.cpp:43
Integer variables.
Definition: int.hh:371
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.
Definition: options.hpp:190
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Use dfa for distinct except 0.
ColoredMatrix(ColoredMatrix &s)
Constructor for cloning s.
Post propagator for SetVar x
Definition: set.hh:767
Matrix-interface for arrays.
Definition: minimodel.hh:2048
const unsigned int colors
Number of colors to use.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
virtual Space * copy(void)
Copy during cloning.
void model(int v)
Set default model value.
Definition: options.hpp:177
Gecode toplevel namespace
Gecode::IntArgs v1({Gecode::Int::Limits::min+4, 0, 1, Gecode::Int::Limits::max})
IntVar max_color
Maximum color used.
Disequality ( )
Definition: int.hh:927
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.
Definition: macros.hpp:56
Options for scripts
Definition: driver.hh:366
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.