Generated on Sat May 25 2013 18:00:37 for Gecode by doxygen 1.8.3.1
ldsb.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christopher Mears <chris.mears@monash.edu>
5  *
6  * Copyright:
7  * Christopher Mears, 2012
8  *
9  * Last modified:
10  * $Date: 2013-03-08 04:21:30 +0100 (Fri, 08 Mar 2013) $ by $Author: mears $
11  * $Revision: 13477 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/kernel.hh>
39 #include <gecode/int.hh>
40 #include <gecode/int/branch.hh>
41 
42 #ifdef GECODE_HAS_SET_VARS
43 #include <gecode/set.hh>
44 #include <gecode/set/branch.hh>
45 #endif
46 
47 #include <gecode/minimodel.hh>
48 
49 #include "test/test.hh"
50 
51 #include <vector>
52 
57 namespace Test { namespace LDSB {
58 
59  using namespace Gecode;
60 
63  bool
64  equal(const IntArgs& a, const IntArgs& b) {
65  if (a.size() != b.size()) return false;
66  for (int i = 0 ; i < a.size() ; ++i)
67  if (a[i] != b[i])
68  return false;
69  return true;
70  }
71 
72 #ifdef GECODE_HAS_SET_VARS
73 
74 
75  bool
76  equal(const IntSetArgs& a, const IntSetArgs& b) {
77  if (a.size() != b.size()) return false;
78  for (int i = 0 ; i < a.size() ; ++i) {
79  // Compare the two sets a[i] and b[i].
80  // Perhaps TODO: use Iter::Ranges::equal instead.
81  if (a[i].size() != b[i].size()) return false;
82  IntSetValues x(a[i]);
83  IntSetValues y(b[i]);
84  while (x() && y()) {
85  if (x.val() != y.val()) return false;
86  ++x;
87  ++y;
88  }
89  }
90  return true;
91  }
92 #endif
93 
103  template <class T, class VarArgsType>
104  bool
105  check(DFS<T>& e, std::vector<VarArgsType> expected) {
106  int nexpected = expected.size();
107  for (int i = 0 ; i < nexpected ; ++i) {
108  T* s = e.next();
109  if (s == NULL) {
110  if (opt.log) {
111  olog << "Expected a solution but there are no more solutions." << std::endl;
112  olog << "(Expected " << nexpected << " but only found " << i << ")" << std::endl;
113  olog << "Expected: " << expected[i] << std::endl;
114  }
115  return false;
116  }
117  if (!equal(s->solution(), expected[i])) {
118  if (opt.log) {
119  olog << "Solution does not match expected." << std::endl;
120  olog << "Solution: " << s->solution() << std::endl;
121  olog << "Expected: " << expected[i] << std::endl;
122  }
123  return false;
124  }
125  delete s;
126  }
127  T* s = e.next();
128  if (s != NULL) {
129  if (opt.log) {
130  olog << "More solutions than expected:" << std::endl;
131  olog << "(Expected only " << nexpected << ")" << std::endl;
132  olog << s->solution() << std::endl;
133  }
134  return false;
135  }
136 
137  // Nothing went wrong.
138  return true;
139  }
140 
141 
143  class OneArray : public Space {
144  public:
148  OneArray(int n, int l, int u) : xs(*this,n,l,u) {
149  }
151  OneArray(bool share, OneArray& s) : Space(share,s) {
152  xs.update(*this,share,s.xs);
153  }
155  virtual Space* copy(bool share) {
156  return new OneArray(share,*this);
157  }
160  IntArgs a(xs.size());
161  for (int i = 0 ; i < a.size() ; ++i)
162  a[i] = xs[i].val();
163  return a;
164  }
166  virtual IntArgs* expectedSolutions(void) { return NULL; }
167  };
168 
169 #ifdef GECODE_HAS_SET_VARS
170 
171  class OneArraySet : public Space {
172  public:
176  OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) {
177  }
179  OneArraySet(bool share, OneArraySet& s) : Space(share,s) {
180  xs.update(*this,share,s.xs);
181  }
183  virtual Space* copy(bool share) {
184  return new OneArraySet(share,*this);
185  }
188  IntSetArgs a(xs.size());
189  for (int i = 0 ; i < a.size() ; ++i) {
190  SetVarGlbRanges glbranges(xs[i]);
191  a[i] = IntSet(glbranges);
192  }
193  return a;
194  }
196  virtual IntSetArgs* expectedSolutions(void) { return NULL; }
197  };
198 #endif
199 
201  template <class T>
202  class LDSB : public Base {
203  public:
205  unsigned int c_d;
207  unsigned int a_d;
209  LDSB(std::string label, unsigned int c=0, unsigned int a=0)
210  : Test::Base("LDSB::" + label),
211  c_d(c), a_d(a) {}
213  bool run(void) {
214  OneArray *s = new OneArray(T::n, T::l, T::u);
215  T::setup(*s, s->xs);
217  if (c_d != 0) o.c_d = c_d;
218  if (a_d != 0) o.a_d = a_d;
219  DFS<OneArray> e(s,o);
220  bool r = check(e, T::expectedSolutions());
221  delete s;
222  return r;
223  }
224  };
225 
226 #ifdef GECODE_HAS_SET_VARS
227 
228  template <class T>
229  class LDSBSet : public Base {
230  public:
232  unsigned int c_d;
234  unsigned int a_d;
236  LDSBSet(std::string label, unsigned int c=0, unsigned int a=0)
237  : Test::Base("LDSB::" + label),
238  c_d(c), a_d(a) {}
240  bool run(void) {
241  OneArraySet *s = new OneArraySet(T::n, T::l, T::u);
242  T::setup(*s, s->xs);
244  if (c_d != 0) o.c_d = c_d;
245  if (a_d != 0) o.a_d = a_d;
246  DFS<OneArraySet> e(s,o);
247  bool r = check(e, T::expectedSolutions());
248  delete s;
249  return r;
250  }
251  };
252 #endif
253 
254  // Test cases
255 
257  class VarSym1 {
258  public:
260  static const int n = 4;
262  static const int l = 0;
264  static const int u = 3;
266  static void setup(Home h, IntVarArray& xs) {
267  Symmetries syms;
268  IntArgs indices(4, 0,1,2,3);
269  syms << VariableSymmetry(xs, indices);
270  distinct(h, xs);
271  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
272  }
274  static std::vector<IntArgs> expectedSolutions(void) {
275  static std::vector<IntArgs> expected;
276  expected.clear();
277  expected.push_back(IntArgs(4, 0,1,2,3));
278  return expected;
279  }
280  };
281 
283  class VarSym1b {
284  public:
286  static const int n = 4;
288  static const int l = 0;
290  static const int u = 3;
292  static void setup(Home h, IntVarArray& xs) {
293  distinct(h, xs);
294  Symmetries syms;
295  syms << VariableSymmetry(xs);
296  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
297  }
299  static std::vector<IntArgs> expectedSolutions(void) {
300  static std::vector<IntArgs> expected;
301  expected.clear();
302  expected.push_back(IntArgs(4, 0,1,2,3));
303  return expected;
304  }
305  };
306 
308  class VarSym2 {
309  public:
311  static const int n = 4;
313  static const int l = 0;
315  static const int u = 3;
317  static void setup(Home h, IntVarArray& xs) {
318  Symmetries syms;
319  IntArgs indices(4, 0,1,2,3);
320  syms << VariableSymmetry(xs);
321  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
322  }
324  static std::vector<IntArgs> expectedSolutions(void) {
325  static std::vector<IntArgs> expected;
326  expected.clear();
327  expected.push_back(IntArgs(4, 0,0,0,0));
328  expected.push_back(IntArgs(4, 0,0,0,1));
329  expected.push_back(IntArgs(4, 0,0,0,2));
330  expected.push_back(IntArgs(4, 0,0,0,3));
331  expected.push_back(IntArgs(4, 0,0,1,1));
332  expected.push_back(IntArgs(4, 0,0,1,2));
333  expected.push_back(IntArgs(4, 0,0,1,3));
334  expected.push_back(IntArgs(4, 0,0,2,2));
335  expected.push_back(IntArgs(4, 0,0,2,3));
336  expected.push_back(IntArgs(4, 0,0,3,3));
337  expected.push_back(IntArgs(4, 0,1,1,1));
338  expected.push_back(IntArgs(4, 0,1,1,2));
339  expected.push_back(IntArgs(4, 0,1,1,3));
340  expected.push_back(IntArgs(4, 0,1,2,2));
341  expected.push_back(IntArgs(4, 0,1,2,3));
342  expected.push_back(IntArgs(4, 0,1,3,3));
343  expected.push_back(IntArgs(4, 0,2,2,2));
344  expected.push_back(IntArgs(4, 0,2,2,3));
345  expected.push_back(IntArgs(4, 0,2,3,3));
346  expected.push_back(IntArgs(4, 0,3,3,3));
347  expected.push_back(IntArgs(4, 1,1,1,1));
348  expected.push_back(IntArgs(4, 1,1,1,2));
349  expected.push_back(IntArgs(4, 1,1,1,3));
350  expected.push_back(IntArgs(4, 1,1,2,2));
351  expected.push_back(IntArgs(4, 1,1,2,3));
352  expected.push_back(IntArgs(4, 1,1,3,3));
353  expected.push_back(IntArgs(4, 1,2,2,2));
354  expected.push_back(IntArgs(4, 1,2,2,3));
355  expected.push_back(IntArgs(4, 1,2,3,3));
356  expected.push_back(IntArgs(4, 1,3,3,3));
357  expected.push_back(IntArgs(4, 2,2,2,2));
358  expected.push_back(IntArgs(4, 2,2,2,3));
359  expected.push_back(IntArgs(4, 2,2,3,3));
360  expected.push_back(IntArgs(4, 2,3,3,3));
361  expected.push_back(IntArgs(4, 3,3,3,3));
362  return expected;
363  }
364  };
365 
367  class VarSym3 {
368  public:
370  static const int n = 4;
372  static const int l = 0;
374  static const int u = 3;
376  static void setup(Home h, IntVarArray& xs) {
377  Symmetries syms;
378  distinct(h, xs);
379  syms << VariableSymmetry(IntVarArgs() << xs[0] << xs[1]);
380  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
381  }
383  static std::vector<IntArgs> expectedSolutions(void) {
384  static std::vector<IntArgs> expected;
385  expected.clear();
386  expected.push_back(IntArgs(4, 0,1,2,3));
387  expected.push_back(IntArgs(4, 0,1,3,2));
388  expected.push_back(IntArgs(4, 0,2,1,3));
389  expected.push_back(IntArgs(4, 0,2,3,1));
390  expected.push_back(IntArgs(4, 0,3,1,2));
391  expected.push_back(IntArgs(4, 0,3,2,1));
392  expected.push_back(IntArgs(4, 1,2,0,3));
393  expected.push_back(IntArgs(4, 1,2,3,0));
394  expected.push_back(IntArgs(4, 1,3,0,2));
395  expected.push_back(IntArgs(4, 1,3,2,0));
396  expected.push_back(IntArgs(4, 2,3,0,1));
397  expected.push_back(IntArgs(4, 2,3,1,0));
398  return expected;
399  }
400  };
401 
403  class VarSym4 {
404  public:
406  static const int n = 3;
408  static const int l = 0;
410  static const int u = 2;
412  static void setup(Home h, IntVarArray& xs) {
413  distinct(h, xs);
414  Symmetries s;
415  IntVarArgs symvars;
416  symvars << xs[0];
417  s << VariableSymmetry(symvars);
418  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
419  }
421  static std::vector<IntArgs> expectedSolutions(void) {
422  static std::vector<IntArgs> expected;
423  expected.clear();
424  expected.push_back(IntArgs(3, 0,1,2));
425  expected.push_back(IntArgs(3, 0,2,1));
426  expected.push_back(IntArgs(3, 1,0,2));
427  expected.push_back(IntArgs(3, 1,2,0));
428  expected.push_back(IntArgs(3, 2,0,1));
429  expected.push_back(IntArgs(3, 2,1,0));
430  return expected;
431  }
432  };
433 
435  class VarSym5 {
436  public:
438  static const int n = 4;
440  static const int l = 0;
442  static const int u = 3;
444  static void setup(Home h, IntVarArray& xs) {
445  distinct(h, xs);
446  Matrix<IntVarArray> m(xs, 4, 1);
447  Symmetries s;
448  s << VariableSymmetry(m.slice(0,2, 0,1));
449  s << VariableSymmetry(m.slice(2,4, 0,1));
450  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
451  }
453  static std::vector<IntArgs> expectedSolutions(void) {
454  static std::vector<IntArgs> expected;
455  expected.clear();
456  expected.push_back(IntArgs(4, 0,1,2,3));
457  expected.push_back(IntArgs(4, 0,2,1,3));
458  expected.push_back(IntArgs(4, 0,3,1,2));
459  expected.push_back(IntArgs(4, 1,2,0,3));
460  expected.push_back(IntArgs(4, 1,3,0,2));
461  expected.push_back(IntArgs(4, 2,3,0,1));
462  return expected;
463  }
464  };
465 
467  class MatSym1 {
468  public:
470  static const int n = 6;
472  static const int l = 0;
474  static const int u = 1;
476  static void setup(Home h, IntVarArray& xs) {
477  Matrix<IntVarArray> m(xs, 2, 3);
478  Symmetries s;
479  s << rows_interchange(m);
480  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
481  }
483  static std::vector<IntArgs> expectedSolutions(void) {
484  static std::vector<IntArgs> expected;
485  expected.clear();
486  expected.push_back(IntArgs(6, 0,0, 0,0, 0,0));
487  expected.push_back(IntArgs(6, 0,0, 0,0, 0,1));
488  expected.push_back(IntArgs(6, 0,0, 0,0, 1,0));
489  expected.push_back(IntArgs(6, 0,0, 0,0, 1,1));
490  expected.push_back(IntArgs(6, 0,0, 0,1, 0,0));
491  expected.push_back(IntArgs(6, 0,0, 0,1, 0,1));
492  expected.push_back(IntArgs(6, 0,0, 0,1, 1,0));
493  expected.push_back(IntArgs(6, 0,0, 0,1, 1,1));
494  expected.push_back(IntArgs(6, 0,0, 1,0, 1,0));
495  expected.push_back(IntArgs(6, 0,0, 1,0, 1,1));
496  expected.push_back(IntArgs(6, 0,0, 1,1, 1,1));
497  expected.push_back(IntArgs(6, 0,1, 0,0, 0,0));
498  expected.push_back(IntArgs(6, 0,1, 0,0, 0,1));
499  expected.push_back(IntArgs(6, 0,1, 0,0, 1,0));
500  expected.push_back(IntArgs(6, 0,1, 0,0, 1,1));
501  expected.push_back(IntArgs(6, 0,1, 0,1, 0,0));
502  expected.push_back(IntArgs(6, 0,1, 0,1, 0,1));
503  expected.push_back(IntArgs(6, 0,1, 0,1, 1,0));
504  expected.push_back(IntArgs(6, 0,1, 0,1, 1,1));
505  expected.push_back(IntArgs(6, 0,1, 1,0, 1,0));
506  expected.push_back(IntArgs(6, 0,1, 1,0, 1,1));
507  expected.push_back(IntArgs(6, 0,1, 1,1, 1,1));
508  expected.push_back(IntArgs(6, 1,0, 1,0, 1,0));
509  expected.push_back(IntArgs(6, 1,0, 1,0, 1,1));
510  expected.push_back(IntArgs(6, 1,0, 1,1, 1,1));
511  expected.push_back(IntArgs(6, 1,1, 1,1, 1,1));
512  return expected;
513  }
514  };
515 
517  class MatSym2 {
518  public:
520  static const int n = 6;
522  static const int l = 0;
524  static const int u = 1;
526  static void setup(Home h, IntVarArray& xs) {
527  Matrix<IntVarArray> m(xs, 2, 3);
528  Symmetries s;
529  s << columns_interchange(m);
530  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
531  }
533  static std::vector<IntArgs> expectedSolutions(void) {
534  static std::vector<IntArgs> expected;
535  expected.clear();
536  expected.push_back(IntArgs(6, 0,0, 0,0, 0,0));
537  expected.push_back(IntArgs(6, 0,0, 0,0, 0,1));
538  expected.push_back(IntArgs(6, 0,0, 0,0, 1,1));
539  expected.push_back(IntArgs(6, 0,0, 0,1, 0,0));
540  expected.push_back(IntArgs(6, 0,0, 0,1, 0,1));
541  expected.push_back(IntArgs(6, 0,0, 0,1, 1,0));
542  expected.push_back(IntArgs(6, 0,0, 0,1, 1,1));
543  expected.push_back(IntArgs(6, 0,0, 1,1, 0,0));
544  expected.push_back(IntArgs(6, 0,0, 1,1, 0,1));
545  expected.push_back(IntArgs(6, 0,0, 1,1, 1,1));
546  expected.push_back(IntArgs(6, 0,1, 0,0, 0,0));
547  expected.push_back(IntArgs(6, 0,1, 0,0, 0,1));
548  expected.push_back(IntArgs(6, 0,1, 0,0, 1,0));
549  expected.push_back(IntArgs(6, 0,1, 0,0, 1,1));
550  expected.push_back(IntArgs(6, 0,1, 0,1, 0,0));
551  expected.push_back(IntArgs(6, 0,1, 0,1, 0,1));
552  expected.push_back(IntArgs(6, 0,1, 0,1, 1,0));
553  expected.push_back(IntArgs(6, 0,1, 0,1, 1,1));
554  expected.push_back(IntArgs(6, 0,1, 1,0, 0,0));
555  expected.push_back(IntArgs(6, 0,1, 1,0, 0,1));
556  expected.push_back(IntArgs(6, 0,1, 1,0, 1,0));
557  expected.push_back(IntArgs(6, 0,1, 1,0, 1,1));
558  expected.push_back(IntArgs(6, 0,1, 1,1, 0,0));
559  expected.push_back(IntArgs(6, 0,1, 1,1, 0,1));
560  expected.push_back(IntArgs(6, 0,1, 1,1, 1,0));
561  expected.push_back(IntArgs(6, 0,1, 1,1, 1,1));
562  expected.push_back(IntArgs(6, 1,1, 0,0, 0,0));
563  expected.push_back(IntArgs(6, 1,1, 0,0, 0,1));
564  expected.push_back(IntArgs(6, 1,1, 0,0, 1,1));
565  expected.push_back(IntArgs(6, 1,1, 0,1, 0,0));
566  expected.push_back(IntArgs(6, 1,1, 0,1, 0,1));
567  expected.push_back(IntArgs(6, 1,1, 0,1, 1,0));
568  expected.push_back(IntArgs(6, 1,1, 0,1, 1,1));
569  expected.push_back(IntArgs(6, 1,1, 1,1, 0,0));
570  expected.push_back(IntArgs(6, 1,1, 1,1, 0,1));
571  expected.push_back(IntArgs(6, 1,1, 1,1, 1,1));
572  return expected;
573  }
574  };
575 
577  class MatSym3 {
578  public:
580  static const int n = 6;
582  static const int l = 0;
584  static const int u = 1;
586  static void setup(Home h, IntVarArray& xs) {
587  Matrix<IntVarArray> m(xs, 2, 3);
588  Symmetries s;
589  s << rows_interchange(m);
590  s << columns_interchange(m);
591  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
592  }
594  static std::vector<IntArgs> expectedSolutions(void) {
595  static std::vector<IntArgs> expected;
596  expected.clear();
597  expected.push_back(IntArgs(6, 0,0, 0,0, 0,0));
598  expected.push_back(IntArgs(6, 0,0, 0,0, 0,1));
599  expected.push_back(IntArgs(6, 0,0, 0,0, 1,1));
600  expected.push_back(IntArgs(6, 0,0, 0,1, 0,0));
601  expected.push_back(IntArgs(6, 0,0, 0,1, 0,1));
602  expected.push_back(IntArgs(6, 0,0, 0,1, 1,0));
603  expected.push_back(IntArgs(6, 0,0, 0,1, 1,1));
604  expected.push_back(IntArgs(6, 0,0, 1,1, 1,1));
605  expected.push_back(IntArgs(6, 0,1, 0,0, 0,0));
606  expected.push_back(IntArgs(6, 0,1, 0,0, 0,1));
607  expected.push_back(IntArgs(6, 0,1, 0,0, 1,0));
608  expected.push_back(IntArgs(6, 0,1, 0,0, 1,1));
609  expected.push_back(IntArgs(6, 0,1, 0,1, 0,0));
610  expected.push_back(IntArgs(6, 0,1, 0,1, 0,1));
611  expected.push_back(IntArgs(6, 0,1, 0,1, 1,0));
612  expected.push_back(IntArgs(6, 0,1, 0,1, 1,1));
613  expected.push_back(IntArgs(6, 0,1, 1,0, 1,0));
614  expected.push_back(IntArgs(6, 0,1, 1,0, 1,1));
615  expected.push_back(IntArgs(6, 0,1, 1,1, 1,1));
616  expected.push_back(IntArgs(6, 1,1, 1,1, 1,1));
617  return expected;
618  }
619  };
620 
622  class MatSym4 {
623  public:
625  static const int n = 4;
627  static const int l = 0;
629  static const int u = 1;
631  static void setup(Home h, IntVarArray& xs) {
632  Matrix<IntVarArray> m(xs, 1, 4);
633  Symmetries s;
634  s << rows_reflect(m);
635  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
636  }
638  static std::vector<IntArgs> expectedSolutions(void) {
639  static std::vector<IntArgs> expected;
640  expected.clear();
641  expected.push_back(IntArgs(4, 0, 0, 0, 0));
642  expected.push_back(IntArgs(4, 0, 0, 0, 1));
643  expected.push_back(IntArgs(4, 0, 0, 1, 0));
644  expected.push_back(IntArgs(4, 0, 0, 1, 1));
645  expected.push_back(IntArgs(4, 0, 1, 0, 0));
646  expected.push_back(IntArgs(4, 0, 1, 0, 1));
647  expected.push_back(IntArgs(4, 0, 1, 1, 0));
648  expected.push_back(IntArgs(4, 0, 1, 1, 1));
649  expected.push_back(IntArgs(4, 1, 0, 0, 1));
650  expected.push_back(IntArgs(4, 1, 0, 1, 1));
651  expected.push_back(IntArgs(4, 1, 1, 1, 1));
652  return expected;
653  }
654  };
655 
658  public:
660  static const int n = 12;
662  static const int l = 0;
664  static const int u = 3;
666  static void setup(Home h, IntVarArray& xs) {
667  Matrix<IntVarArray> m(xs, 3, 4);
668  // The values in the first column are distinct.
669  distinct(h, m.col(0));
670  // Each row sums to 3.
671  for (int i = 0 ; i < 4 ; ++i)
672  linear(h, m.row(i), IRT_EQ, 3);
673 
674  // Rows are interchangeable.
675  Symmetries s;
676  s << VariableSequenceSymmetry(xs, 3);
677  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
678  }
680  static std::vector<IntArgs> expectedSolutions(void) {
681  static std::vector<IntArgs> expected;
682  expected.clear();
683  expected.push_back(IntArgs(12, 0,0,3, 1,0,2, 2,0,1, 3,0,0));
684  expected.push_back(IntArgs(12, 0,0,3, 1,0,2, 2,1,0, 3,0,0));
685  expected.push_back(IntArgs(12, 0,0,3, 1,1,1, 2,0,1, 3,0,0));
686  expected.push_back(IntArgs(12, 0,0,3, 1,1,1, 2,1,0, 3,0,0));
687  expected.push_back(IntArgs(12, 0,0,3, 1,2,0, 2,0,1, 3,0,0));
688  expected.push_back(IntArgs(12, 0,0,3, 1,2,0, 2,1,0, 3,0,0));
689  expected.push_back(IntArgs(12, 0,1,2, 1,0,2, 2,0,1, 3,0,0));
690  expected.push_back(IntArgs(12, 0,1,2, 1,0,2, 2,1,0, 3,0,0));
691  expected.push_back(IntArgs(12, 0,1,2, 1,1,1, 2,0,1, 3,0,0));
692  expected.push_back(IntArgs(12, 0,1,2, 1,1,1, 2,1,0, 3,0,0));
693  expected.push_back(IntArgs(12, 0,1,2, 1,2,0, 2,0,1, 3,0,0));
694  expected.push_back(IntArgs(12, 0,1,2, 1,2,0, 2,1,0, 3,0,0));
695  expected.push_back(IntArgs(12, 0,2,1, 1,0,2, 2,0,1, 3,0,0));
696  expected.push_back(IntArgs(12, 0,2,1, 1,0,2, 2,1,0, 3,0,0));
697  expected.push_back(IntArgs(12, 0,2,1, 1,1,1, 2,0,1, 3,0,0));
698  expected.push_back(IntArgs(12, 0,2,1, 1,1,1, 2,1,0, 3,0,0));
699  expected.push_back(IntArgs(12, 0,2,1, 1,2,0, 2,0,1, 3,0,0));
700  expected.push_back(IntArgs(12, 0,2,1, 1,2,0, 2,1,0, 3,0,0));
701  expected.push_back(IntArgs(12, 0,3,0, 1,0,2, 2,0,1, 3,0,0));
702  expected.push_back(IntArgs(12, 0,3,0, 1,0,2, 2,1,0, 3,0,0));
703  expected.push_back(IntArgs(12, 0,3,0, 1,1,1, 2,0,1, 3,0,0));
704  expected.push_back(IntArgs(12, 0,3,0, 1,1,1, 2,1,0, 3,0,0));
705  expected.push_back(IntArgs(12, 0,3,0, 1,2,0, 2,0,1, 3,0,0));
706  expected.push_back(IntArgs(12, 0,3,0, 1,2,0, 2,1,0, 3,0,0));
707  return expected;
708  }
709  };
710 
714  static const int nrows = 4;
716  static const int ncols = 3;
717  public:
719  static const int n = nrows*ncols;
721  static const int l = 0;
723  static const int u = 3;
725  static void setup(Home h, IntVarArray& xs) {
726  Matrix<IntVarArray> m(xs, 3, 4);
727  // The values in the first column are distinct.
728  distinct(h, m.col(0));
729  // Each row sums to 3.
730  for (int i = 0 ; i < nrows ; ++i)
731  linear(h, m.row(i), IRT_EQ, 3);
732 
733  Symmetries s;
734 
735  IntArgs a = IntArgs::create(n, 0);
736  // Rows are interchangeable.
737  s << VariableSequenceSymmetry(xs, 3);
738  // Elements (i,1) and (i,2) in row i are interchangeable,
739  // separately for each row.
740  for (int i = 0 ; i < nrows ; i++) {
741  IntVarArgs symvars;
742  symvars << m(1,i) << m(2,i);
743  s << VariableSymmetry(symvars);
744  }
745  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
746  }
748  static std::vector<IntArgs> expectedSolutions(void) {
749  static std::vector<IntArgs> expected;
750  expected.clear();
751  expected.push_back(IntArgs(12, 0,0,3, 1,0,2, 2,0,1, 3,0,0));
752  expected.push_back(IntArgs(12, 0,0,3, 1,1,1, 2,0,1, 3,0,0));
753  expected.push_back(IntArgs(12, 0,1,2, 1,0,2, 2,0,1, 3,0,0));
754  expected.push_back(IntArgs(12, 0,1,2, 1,1,1, 2,0,1, 3,0,0));
755  return expected;
756  }
757  };
758 
761  public:
763  static const int n = 2;
765  static const int l = 0;
767  static const int u = 6;
769  static void setup(Home h, IntVarArray& xs) {
770  rel(h, xs[0] + xs[1] == 6);
771  // Values 0,1,2 are symmetric with 6,5,4.
772  IntArgs values(6, 0,1,2, 6,5,4);
773  Symmetries s;
774  s << ValueSequenceSymmetry(values, 3);
775  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
776  }
778  static std::vector<IntArgs> expectedSolutions(void) {
779  static std::vector<IntArgs> expected;
780  expected.clear();
781  expected.push_back(IntArgs(2, 0,6));
782  expected.push_back(IntArgs(2, 1,5));
783  expected.push_back(IntArgs(2, 2,4));
784  expected.push_back(IntArgs(2, 3,3));
785  return expected;
786  }
787  };
788 
791  public:
793  static const int n = 3;
795  static const int l = 0;
797  static const int u = 8;
799  static void setup(Home h, IntVarArray& xs) {
800  TupleSet tuples;
801  tuples.add(IntArgs(3, 1,1,1));
802  tuples.add(IntArgs(3, 4,4,4));
803  tuples.add(IntArgs(3, 7,7,7));
804  tuples.add(IntArgs(3, 0,1,5));
805  tuples.add(IntArgs(3, 0,1,8));
806  tuples.add(IntArgs(3, 3,4,2));
807  tuples.add(IntArgs(3, 3,4,8));
808  tuples.add(IntArgs(3, 6,7,2));
809  tuples.add(IntArgs(3, 6,7,5));
810  tuples.finalize();
811  extensional(h, xs, tuples);
812 
813  // Values 0,1,2 are symmetric with 3,4,5, and with 6,7,8.
814  IntArgs values(9, 0,1,2, 3,4,5, 6,7,8);
815  Symmetries s;
816  s << ValueSequenceSymmetry(values, 3);
817  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
818  }
820  static std::vector<IntArgs> expectedSolutions(void) {
821  static std::vector<IntArgs> expected;
822  expected.clear();
823  expected.push_back(IntArgs(3, 0,1,5));
824  expected.push_back(IntArgs(3, 1,1,1));
825  return expected;
826  }
827  };
828 
830  class ValSym1 {
831  public:
833  static const int n = 4;
835  static const int l = 0;
837  static const int u = 3;
839  static void setup(Home h, IntVarArray& xs) {
840  distinct(h, xs);
841  Symmetries s;
842  IntArgs indices(4, 0,1,2,3);
843  s << ValueSymmetry(indices);
844  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
845  }
847  static std::vector<IntArgs> expectedSolutions(void) {
848  static std::vector<IntArgs> expected;
849  expected.clear();
850  expected.push_back(IntArgs(4, 0,1,2,3));
851  return expected;
852  }
853  };
854 
856  class ValSym1b {
857  public:
859  static const int n = 4;
861  static const int l = 0;
863  static const int u = 3;
865  static void setup(Home h, IntVarArray& xs) {
866  distinct(h, xs);
867  Symmetries s;
868  s << ValueSymmetry(xs[0]);
869  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
870  }
872  static std::vector<IntArgs> expectedSolutions(void) {
873  static std::vector<IntArgs> expected;
874  expected.clear();
875  expected.push_back(IntArgs(4, 0,1,2,3));
876  return expected;
877  }
878  };
879 
881  class ValSym1c {
882  public:
884  static const int n = 4;
886  static const int l = 0;
888  static const int u = 3;
890  static void setup(Home h, IntVarArray& xs) {
891  distinct(h, xs);
892  Symmetries s;
893  s << ValueSymmetry(xs[0]);
894  branch(h, xs, INT_VAR_NONE(), INT_VAL_MAX(), s);
895  }
897  static std::vector<IntArgs> expectedSolutions(void) {
898  static std::vector<IntArgs> expected;
899  expected.clear();
900  expected.push_back(IntArgs(4, 3,2,1,0));
901  return expected;
902  }
903  };
904 
906  class ValSym2 {
907  public:
909  static const int n = 4;
911  static const int l = 0;
913  static const int u = 3;
915  static void setup(Home h, IntVarArray& xs) {
916  Symmetries s;
917  IntArgs indices(4, 0,1,2,3);
918  s << ValueSymmetry(indices);
919  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
920  }
922  static std::vector<IntArgs> expectedSolutions(void) {
923  static std::vector<IntArgs> expected;
924  expected.clear();
925  expected.push_back(IntArgs(4, 0,0,0,0));
926  expected.push_back(IntArgs(4, 0,0,0,1));
927  expected.push_back(IntArgs(4, 0,0,1,0));
928  expected.push_back(IntArgs(4, 0,0,1,1));
929  expected.push_back(IntArgs(4, 0,0,1,2));
930  expected.push_back(IntArgs(4, 0,1,0,0));
931  expected.push_back(IntArgs(4, 0,1,0,1));
932  expected.push_back(IntArgs(4, 0,1,0,2));
933  expected.push_back(IntArgs(4, 0,1,1,0));
934  expected.push_back(IntArgs(4, 0,1,1,1));
935  expected.push_back(IntArgs(4, 0,1,1,2));
936  expected.push_back(IntArgs(4, 0,1,2,0));
937  expected.push_back(IntArgs(4, 0,1,2,1));
938  expected.push_back(IntArgs(4, 0,1,2,2));
939  expected.push_back(IntArgs(4, 0,1,2,3));
940  return expected;
941  }
942  };
943 
945  class ValSym2b {
946  public:
948  static const int n = 4;
950  static const int l = 0;
952  static const int u = 3;
954  static void setup(Home h, IntVarArray& xs) {
955  Symmetries s;
956  s << ValueSymmetry(xs[0]);
957  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
958  }
960  static std::vector<IntArgs> expectedSolutions(void) {
961  static std::vector<IntArgs> expected;
962  expected.clear();
963  expected.push_back(IntArgs(4, 0,0,0,0));
964  expected.push_back(IntArgs(4, 0,0,0,1));
965  expected.push_back(IntArgs(4, 0,0,1,0));
966  expected.push_back(IntArgs(4, 0,0,1,1));
967  expected.push_back(IntArgs(4, 0,0,1,2));
968  expected.push_back(IntArgs(4, 0,1,0,0));
969  expected.push_back(IntArgs(4, 0,1,0,1));
970  expected.push_back(IntArgs(4, 0,1,0,2));
971  expected.push_back(IntArgs(4, 0,1,1,0));
972  expected.push_back(IntArgs(4, 0,1,1,1));
973  expected.push_back(IntArgs(4, 0,1,1,2));
974  expected.push_back(IntArgs(4, 0,1,2,0));
975  expected.push_back(IntArgs(4, 0,1,2,1));
976  expected.push_back(IntArgs(4, 0,1,2,2));
977  expected.push_back(IntArgs(4, 0,1,2,3));
978  return expected;
979  }
980  };
981 
983  class ValSym3 {
984  public:
986  static const int n = 4;
988  static const int l = 0;
990  static const int u = 3;
992  static void setup(Home h, IntVarArray& xs) {
993  distinct(h, xs);
994  Symmetries s;
995  IntArgs indices(2, 0,1);
996  s << ValueSymmetry(indices);
997  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
998  }
1000  static std::vector<IntArgs> expectedSolutions(void) {
1001  static std::vector<IntArgs> expected;
1002  expected.clear();
1003  expected.push_back(IntArgs(4, 0,1,2,3));
1004  expected.push_back(IntArgs(4, 0,1,3,2));
1005  expected.push_back(IntArgs(4, 0,2,1,3));
1006  expected.push_back(IntArgs(4, 0,2,3,1));
1007  expected.push_back(IntArgs(4, 0,3,1,2));
1008  expected.push_back(IntArgs(4, 0,3,2,1));
1009  expected.push_back(IntArgs(4, 2,0,1,3));
1010  expected.push_back(IntArgs(4, 2,0,3,1));
1011  expected.push_back(IntArgs(4, 2,3,0,1));
1012  expected.push_back(IntArgs(4, 3,0,1,2));
1013  expected.push_back(IntArgs(4, 3,0,2,1));
1014  expected.push_back(IntArgs(4, 3,2,0,1));
1015  return expected;
1016  }
1017  };
1018 
1020  class ValSym4 {
1021  public:
1023  static const int n = 3;
1025  static const int l = 0;
1027  static const int u = 2;
1029  static void setup(Home h, IntVarArray& xs) {
1030  distinct(h, xs);
1031  Symmetries s;
1032  IntArgs indices(1, 0);
1033  s << ValueSymmetry(indices);
1034  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1035  }
1037  static std::vector<IntArgs> expectedSolutions(void) {
1038  static std::vector<IntArgs> expected;
1039  expected.clear();
1040  expected.push_back(IntArgs(3, 0,1,2));
1041  expected.push_back(IntArgs(3, 0,2,1));
1042  expected.push_back(IntArgs(3, 1,0,2));
1043  expected.push_back(IntArgs(3, 1,2,0));
1044  expected.push_back(IntArgs(3, 2,0,1));
1045  expected.push_back(IntArgs(3, 2,1,0));
1046  return expected;
1047  }
1048  };
1049 
1051  class ValSym5 {
1052  public:
1054  static const int n = 4;
1056  static const int l = 0;
1058  static const int u = 3;
1060  static void setup(Home h, IntVarArray& xs) {
1061  distinct(h, xs);
1062  Symmetries s;
1063  IntArgs indices0(2, 0,1);
1064  IntArgs indices1(2, 2,3);
1065  s << ValueSymmetry(indices0);
1066  s << ValueSymmetry(indices1);
1067  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1068  }
1070  static std::vector<IntArgs> expectedSolutions(void) {
1071  static std::vector<IntArgs> expected;
1072  expected.clear();
1073  expected.push_back(IntArgs(4, 0,1,2,3));
1074  expected.push_back(IntArgs(4, 0,2,1,3));
1075  expected.push_back(IntArgs(4, 0,2,3,1));
1076  expected.push_back(IntArgs(4, 2,0,1,3));
1077  expected.push_back(IntArgs(4, 2,0,3,1));
1078  expected.push_back(IntArgs(4, 2,3,0,1));
1079  return expected;
1080  }
1081  };
1082 
1084  class VarValSym1 {
1085  public:
1087  static const int n = 4;
1089  static const int l = 0;
1091  static const int u = 3;
1093  static void setup(Home h, IntVarArray& xs) {
1094  Symmetries s;
1095  s << VariableSymmetry(xs);
1096  s << ValueSymmetry(IntArgs::create(4,0));
1097  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1098  }
1100  static std::vector<IntArgs> expectedSolutions(void) {
1101  static std::vector<IntArgs> expected;
1102  expected.clear();
1103  expected.push_back(IntArgs(4, 0,0,0,0));
1104  expected.push_back(IntArgs(4, 0,0,0,1));
1105  expected.push_back(IntArgs(4, 0,0,1,1));
1106  expected.push_back(IntArgs(4, 0,0,1,2));
1107  expected.push_back(IntArgs(4, 0,1,1,1));
1108  expected.push_back(IntArgs(4, 0,1,1,2));
1109  expected.push_back(IntArgs(4, 0,1,2,2)); // This solution is symmetric to the previous one.
1110  expected.push_back(IntArgs(4, 0,1,2,3));
1111  return expected;
1112  }
1113  };
1114 
1116  class LDSBLatin : public Base {
1117  public:
1119  class Latin : public Space {
1120  public:
1122  Latin(int n = 4) : xs(*this, n*n, 1, n)
1123  {
1124  Matrix<IntVarArray> m(xs, n, n);
1125  for (int i = 0 ; i < n ; i++) {
1126  distinct(*this, m.col(i));
1127  distinct(*this, m.row(i));
1128  }
1129  Symmetries s;
1130  s << rows_interchange(m);
1131  s << columns_interchange(m);
1132  s << ValueSymmetry(IntSet(1,n));
1133  branch(*this, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1134  }
1135  // Search support.
1136  Latin(bool share, Latin& s) : Space(share, s)
1137  { xs.update(*this, share, s.xs); }
1138  virtual Space* copy(bool share)
1139  { return new Latin(share,*this); }
1141  IntArgs a(xs.size());
1142  for (int i = 0 ; i < a.size() ; ++i)
1143  a[i] = xs[i].val();
1144  return a;
1145  }
1146 
1148  static std::vector<IntArgs> expectedSolutions(void) {
1149  static std::vector<IntArgs> expected;
1150  expected.clear();
1151  expected.push_back(IntArgs(16, 1,2,3,4, 2,1,4,3, 3,4,1,2, 4,3,2,1));
1152  expected.push_back(IntArgs(16, 1,2,3,4, 2,1,4,3, 3,4,2,1, 4,3,1,2));
1153  expected.push_back(IntArgs(16, 1,2,3,4, 2,3,4,1, 3,4,1,2, 4,1,2,3));
1154  expected.push_back(IntArgs(16, 1,2,3,4, 2,4,1,3, 3,1,4,2, 4,3,2,1));
1155  return expected;
1156  }
1157  };
1159  LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {}
1161  bool run(void) {
1162  Latin *s = new Latin();
1163  DFS<Latin> e(s);
1164  bool r = check(e, Latin::expectedSolutions());
1165  delete s;
1166  return r;
1167  }
1168  };
1169 
1170  /* This test should fail if the recomputation-handling does not work
1171  * properly.
1172  *
1173  * Why recomputation can be a problem
1174  * ==================================
1175  *
1176  * Every branch point in LDSB is binary, with a left and a right
1177  * branch. Whenever backtracking happens -- when a right branch is
1178  * explored -- LDSB computes a set of symmetric literals to
1179  * exclude.
1180  *
1181  * !!! This calculation may depend on the current domains of the
1182  * !!! variables.
1183  *
1184  * During recomputation, parts of the search tree are replayed. To
1185  * be specific, the branching constraints are posted, but no
1186  * propagation happens. This means that at a given branch point,
1187  * the domains during recomputation may be different (weaker) than
1188  * they were the first time during search.
1189  *
1190  * !!! This *cannot* cause solutions to be missed --- LDSB will not
1191  * !!! be incorrect --- but it *does* change what will be pruned.
1192  *
1193  * If recomputation is not handled properly, the difference in
1194  * domains will cause extra solutions to be found. This is a result
1195  * of symmetries failing to be broken.
1196  *
1197  */
1198 
1201  public:
1203  static const int n = 4;
1205  static const int l = 0;
1207  static const int u = 1;
1209  static void setup(Home h, IntVarArray& xs) {
1210  TupleSet t;
1211  t.add(IntArgs(2, 0,0));
1212  t.add(IntArgs(2, 1,1));
1213  t.finalize();
1214  IntVarArgs va;
1215  va << xs[0] << xs[2];
1216  extensional(h, va, t);
1217  Symmetries syms;
1218  syms << VariableSequenceSymmetry(xs, 2);
1219  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
1220  }
1222  static std::vector<IntArgs> expectedSolutions(void) {
1223  static std::vector<IntArgs> expected;
1224  expected.clear();
1225  expected.push_back(IntArgs(4, 0,0,0,0));
1226  expected.push_back(IntArgs(4, 0,0,0,1));
1227 
1228  // This is the solution that will be found if recomputation is
1229  // not handled. After branching on x[0]=0, we try x[1]=0. When
1230  // x[1]=0 backtracks, the symmetry [x[0],x[1]] <-> [x[2],x[3]]
1231  // is active --- but only after propagation! (Without
1232  // propagation, we do not have x[2]=0.) If propagation happens,
1233  // we know that symmetry is active and we can post x[3]!=0. If
1234  // it doesn't, we don't use the symmetry and we find a solution
1235  // where x[3]=0.
1236 
1237  // expected.push_back(IntArgs(4, 0,1,0,0));
1238 
1239  expected.push_back(IntArgs(4, 0,1,0,1));
1240 
1241  expected.push_back(IntArgs(4, 1,0,1,0));
1242  expected.push_back(IntArgs(4, 1,0,1,1));
1243  expected.push_back(IntArgs(4, 1,1,1,1));
1244  return expected;
1245  }
1246  };
1247 
1248  double position(const Space& home, IntVar x, int i) {
1249  (void) home;
1250  (void) x;
1251  return i;
1252  }
1253 
1255  class TieBreak {
1256  public:
1258  static const int n = 4;
1260  static const int l = 0;
1262  static const int u = 3;
1264  static void setup(Home h, IntVarArray& xs) {
1265  Symmetries syms;
1266  IntArgs indices(4, 0,1,2,3);
1267  syms << VariableSymmetry(xs, indices);
1268  distinct(h, xs);
1269  // This redundant constraint is to trick the variable
1270  // heuristic.
1271  rel(h, xs[1] != xs[2]);
1272  // xs[1] and xs[2] have higher degree than the others, so they
1273  // are considered first. xs[2] is higher than x[1] by the merit
1274  // function, so it is assigned first. Now all remaining
1275  // variables have the same degree, so they are searched in
1276  // reverse order (according to the merit function). So, the
1277  // solution found is {3, 2, 0, 1}.
1279  }
1281  static std::vector<IntArgs> expectedSolutions(void) {
1282  static std::vector<IntArgs> expected;
1283  expected.clear();
1284  expected.push_back(IntArgs(4, 3,2,0,1));
1285  return expected;
1286  }
1287  };
1288 
1289 #ifdef GECODE_HAS_SET_VARS
1290 
1291  IntSetArgs ISA(int n, ...) {
1292  IntSetArgs sets;
1293  va_list args;
1294  va_start(args, n);
1295  int i = 0;
1296  IntArgs a;
1297  while (i < n) {
1298  int x = va_arg(args,int);
1299  if (x == -1) {
1300  i++;
1301  sets << IntSet(a);
1302  a = IntArgs();
1303  } else {
1304  a << x;
1305  }
1306  }
1307  va_end(args);
1308  return sets;
1309  }
1310 
1312  class SetVarSym1 {
1313  public:
1315  static const int n = 2;
1317  static const int l = 0;
1319  static const int u = 1;
1321  static void setup(Home h, SetVarArray& xs) {
1322  Symmetries syms;
1323  syms << VariableSymmetry(xs);
1324  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1325  }
1327  static std::vector<IntSetArgs> expectedSolutions(void) {
1328  static std::vector<IntSetArgs> expected;
1329  expected.clear();
1330  expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
1331  expected.push_back(ISA(2, 0,1,-1, 0, -1));
1332  expected.push_back(ISA(2, 0,1,-1, 1,-1));
1333  expected.push_back(ISA(2, 0,1,-1, -1));
1334  expected.push_back(ISA(2, 0, -1, 0,1,-1));
1335  expected.push_back(ISA(2, 0, -1, 0, -1));
1336  expected.push_back(ISA(2, 0, -1, 1,-1));
1337  expected.push_back(ISA(2, 0, -1, -1));
1338  // expected.push_back(ISA(2, 1,-1, 0,1,-1));
1339  // expected.push_back(ISA(2, 1,-1, 0, -1));
1340  expected.push_back(ISA(2, 1,-1, 1,-1));
1341  expected.push_back(ISA(2, 1,-1, -1));
1342  // expected.push_back(ISA(2, -1, 0,1,-1));
1343  // expected.push_back(ISA(2, -1, 0, -1));
1344  // expected.push_back(ISA(2, -1, 1,-1));
1345  expected.push_back(ISA(2, -1, -1));
1346  return expected;
1347  }
1348  };
1349 
1350  /*
1351  * This tests the special handling of value symmetries on set
1352  * values. Look at the third solution (commented out) below. The
1353  * first variable has been assigned to {0,1}. If the value symmetry
1354  * is not handled specially, then we will consider the value
1355  * symmetry broken because the search has touched each value.
1356  * However, because both values have been assigned to the same
1357  * variable, 0 and 1 are still symmetric. Therefore, the third
1358  * solution is symmetric to the second one and should be excluded.
1359  */
1360 
1362  class SetValSym1 {
1363  public:
1365  static const int n = 2;
1367  static const int l = 0;
1369  static const int u = 1;
1371  static void setup(Home h, SetVarArray& xs) {
1372  Symmetries syms;
1373  syms << ValueSymmetry(IntArgs(2, 0,1));
1374  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1375  }
1377  static std::vector<IntSetArgs> expectedSolutions(void) {
1378  static std::vector<IntSetArgs> expected;
1379  expected.clear();
1380  expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
1381  expected.push_back(ISA(2, 0,1,-1, 0, -1));
1382  // expected.push_back(ISA(2, 0,1,-1, 1,-1)); // XXXXX bad solution
1383  expected.push_back(ISA(2, 0,1,-1, -1));
1384  expected.push_back(ISA(2, 0, -1, 0,1,-1));
1385  expected.push_back(ISA(2, 0, -1, 0, -1));
1386  expected.push_back(ISA(2, 0, -1, 1,-1));
1387  expected.push_back(ISA(2, 0, -1, -1));
1388  // expected.push_back(ISA(2, 1,-1, 0,1,-1));
1389  // expected.push_back(ISA(2, 1,-1, 0, -1));
1390  // expected.push_back(ISA(2, 1,-1, 1,-1));
1391  // expected.push_back(ISA(2, 1,-1, -1));
1392  expected.push_back(ISA(2, -1, 0,1,-1));
1393  expected.push_back(ISA(2, -1, 0, -1));
1394  // expected.push_back(ISA(2, -1, 1,-1));
1395  expected.push_back(ISA(2, -1, -1));
1396  return expected;
1397  }
1398  };
1399 
1401  class SetValSym2 {
1402  public:
1404  static const int n = 3;
1406  static const int l = 1;
1408  static const int u = 4;
1410  static void setup(Home h, SetVarArray& xs) {
1411  Symmetries syms;
1412  syms << ValueSymmetry(IntArgs(4, 1,2,3,4));
1413  for (int i = 0 ; i < 3 ; i++)
1414  cardinality(h, xs[i], 1, 1);
1415  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1416  }
1418  static std::vector<IntSetArgs> expectedSolutions(void) {
1419  static std::vector<IntSetArgs> expected;
1420  expected.clear();
1421  expected.push_back(ISA(3, 1,-1, 1,-1, 1,-1));
1422  expected.push_back(ISA(3, 1,-1, 1,-1, 2,-1));
1423  expected.push_back(ISA(3, 1,-1, 2,-1, 1,-1));
1424  expected.push_back(ISA(3, 1,-1, 2,-1, 2,-1));
1425  expected.push_back(ISA(3, 1,-1, 2,-1, 3,-1));
1426  return expected;
1427  }
1428  };
1429 
1432  public:
1434  static const int n = 4;
1436  static const int l = 0;
1438  static const int u = 1;
1440  static void setup(Home h, SetVarArray& xs) {
1441  Symmetries syms;
1442  syms << VariableSequenceSymmetry(xs,2);
1443  rel(h, xs[0], SOT_INTER, xs[1], SRT_EQ, IntSet::empty);
1444  rel(h, xs[2], SOT_INTER, xs[3], SRT_EQ, IntSet::empty);
1445  for (int i = 0 ; i < 4 ; i++)
1446  cardinality(h, xs[i], 1, 1);
1447  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1448  }
1450  static std::vector<IntSetArgs> expectedSolutions(void) {
1451  static std::vector<IntSetArgs> expected;
1452  expected.clear();
1453  expected.push_back(ISA(4, 0,-1, 1,-1, 0,-1, 1,-1));
1454  expected.push_back(ISA(4, 0,-1, 1,-1, 1,-1, 0,-1));
1455  // expected.push_back(ISA(4, 1,-1, 0,-1, 0,-1, 1,-1));
1456  expected.push_back(ISA(4, 1,-1, 0,-1, 1,-1, 0,-1));
1457  return expected;
1458  }
1459  };
1460 
1463  public:
1465  static const int n = 4;
1467  static const int l = 0;
1469  static const int u = 0;
1471  static void setup(Home h, SetVarArray& xs) {
1472  Symmetries syms;
1473  syms << VariableSequenceSymmetry(xs,2);
1474  rel(h, xs[0], SRT_EQ, xs[2]);
1475  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1476  }
1478  static std::vector<IntSetArgs> expectedSolutions(void) {
1479  static std::vector<IntSetArgs> expected;
1480  expected.clear();
1481 
1482  // Symmetric solutions are commented out.
1483  expected.push_back(ISA(4, 0, -1,0,-1,0,-1,0,-1));
1484  expected.push_back(ISA(4, 0, -1,0,-1,0,-1, -1));
1485  // expected.push_back(ISA(4, 0, -1,0,-1, -1,0,-1));
1486  // expected.push_back(ISA(4, 0, -1,0,-1, -1, -1));
1487  // expected.push_back(ISA(4, 0, -1, -1,0,-1,0,-1));
1488  expected.push_back(ISA(4, 0, -1, -1,0,-1, -1));
1489  // expected.push_back(ISA(4, 0, -1, -1, -1,0,-1));
1490  // expected.push_back(ISA(4, 0, -1, -1, -1, -1));
1491  // expected.push_back(ISA(4, -1,0,-1,0,-1,0,-1));
1492  // expected.push_back(ISA(4, -1,0,-1,0,-1, -1));
1493  expected.push_back(ISA(4, -1,0,-1, -1,0,-1));
1494  expected.push_back(ISA(4, -1,0,-1, -1, -1));
1495  // expected.push_back(ISA(4, -1, -1,0,-1,0,-1));
1496  // expected.push_back(ISA(4, -1, -1,0,-1, -1));
1497  // expected.push_back(ISA(4, -1, -1, -1,0,-1));
1498  expected.push_back(ISA(4, -1, -1, -1, -1));
1499 
1500  return expected;
1501  }
1502  };
1503 
1504 
1505 #endif
1506 
1507  LDSB<VarSym1> varsym1("VarSym1");
1508  LDSB<VarSym1b> varsym1b("VarSym1b");
1509  LDSB<VarSym2> varsym2("VarSym2");
1510  LDSB<VarSym3> varsym3("VarSym3");
1511  LDSB<VarSym4> varsym4("VarSym4");
1512  LDSB<VarSym5> varsym5("VarSym5");
1513  LDSB<MatSym1> matsym1("MatSym1");
1514  LDSB<MatSym2> matsym2("MatSym2");
1515  LDSB<MatSym3> matsym3("MatSym3");
1516  LDSB<MatSym4> matsym4("MatSym4");
1517  LDSB<SimIntVarSym1> simintvarsym1("SimIntVarSym1");
1518  LDSB<SimIntVarSym2> simintvarsym2("SimIntVarSym2");
1519  LDSB<SimIntValSym1> simintvalsym1("SimIntValSym1");
1520  LDSB<SimIntValSym2> simintvalsym2("SimIntValSym2");
1521  LDSB<ValSym1> valsym1("ValSym1");
1522  LDSB<ValSym1b> valsym1b("ValSym1b");
1523  LDSB<ValSym1c> valsym1c("ValSym1c");
1524  LDSB<ValSym2> valsym2("ValSym2");
1525  LDSB<ValSym2b> valsym2b("ValSym2b");
1526  LDSB<ValSym3> valsym3("ValSym3");
1527  LDSB<ValSym4> valsym4("ValSym4");
1528  LDSB<ValSym5> valsym5("ValSym5");
1529  LDSB<VarValSym1> varvalsym1("VarValSym1");
1530  LDSBLatin latin("Latin");
1531  LDSB<Recomputation> recomp("Recomputation", 999,999);
1532  LDSB<TieBreak> tiebreak("TieBreak");
1533 
1534 #ifdef GECODE_HAS_SET_VARS
1535  LDSBSet<SetVarSym1> setvarsym1("SetVarSym1");
1536  LDSBSet<SetValSym1> setvalsym1("SetValSym1");
1537  LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1);
1538  LDSBSet<SetVarSeqSym1> setvarseqsym1("SetVarSeqSym1");
1539  LDSBSet<SetVarSeqSym2> setvarseqsym2("SetVarSeqSym2");
1540 #endif
1541 }}
1542 
1543 // STATISTICS: test-core