Generated on Fri Oct 19 11:25:06 2018 for Gecode by doxygen 1.6.3

ldsb.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christopher Mears <chris.mears@monash.edu>
00005  *
00006  *  Copyright:
00007  *     Christopher Mears, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/kernel.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/int/branch.hh>
00037 
00038 #ifdef GECODE_HAS_SET_VARS
00039 #include <gecode/set.hh>
00040 #include <gecode/set/branch.hh>
00041 #include <stdarg.h>
00042 #endif
00043 
00044 #include <gecode/minimodel.hh>
00045 
00046 #include "test/test.hh"
00047 
00048 #include <vector>
00049 
00054 namespace Test { namespace LDSB {
00055 
00056   using namespace Gecode;
00057 
00060   bool
00061   equal(const IntArgs& a, const IntArgs& b) {
00062     if (a.size() != b.size()) return false;
00063     for (int i = 0 ; i < a.size() ; ++i)
00064       if (a[i] != b[i])
00065         return false;
00066     return true;
00067   }
00068 
00069 #ifdef GECODE_HAS_SET_VARS
00070 
00071 
00072   bool
00073   equal(const IntSetArgs& a, const IntSetArgs& b) {
00074     if (a.size() != b.size()) return false;
00075     for (int i = 0 ; i < a.size() ; ++i) {
00076       // Compare the two sets a[i] and b[i].
00077       // Perhaps TODO: use Iter::Ranges::equal instead.
00078       if (a[i].size() != b[i].size()) return false;
00079       IntSetValues x(a[i]);
00080       IntSetValues y(b[i]);
00081       while (x() && y()) {
00082         if (x.val() != y.val()) return false;
00083         ++x;
00084         ++y;
00085       }
00086     }
00087     return true;
00088   }
00089 #endif
00090 
00100   template <class T, class VarArgsType>
00101   bool
00102   check(DFS<T>& e, std::vector<VarArgsType> expected) {
00103     int nexpected = expected.size();
00104     for (int i = 0 ; i < nexpected ; ++i) {
00105       T* s = e.next();
00106       if (s == NULL) {
00107         if (opt.log) {
00108           olog << "Expected a solution but there are no more solutions." << std::endl;
00109           olog << "(Expected " << nexpected << " but only found " << i << ")" << std::endl;
00110           olog << "Expected: " << expected[i] << std::endl;
00111         }
00112         return false;
00113       }
00114       if (!equal(s->solution(), expected[i])) {
00115         if (opt.log) {
00116           olog << "Solution does not match expected." << std::endl;
00117           olog << "Solution: " << s->solution() << std::endl;
00118           olog << "Expected: " << expected[i] << std::endl;
00119         }
00120         return false;
00121       }
00122       delete s;
00123     }
00124     T* s = e.next();
00125     if (s != NULL) {
00126       if (opt.log) {
00127         olog << "More solutions than expected:" << std::endl;
00128         olog << "(Expected only " << nexpected << ")" << std::endl;
00129         olog << s->solution() << std::endl;
00130       }
00131       return false;
00132     }
00133 
00134     // Nothing went wrong.
00135     return true;
00136   }
00137 
00138 
00140   class OneArray : public Space {
00141   public:
00143     IntVarArray xs;
00145     OneArray(int n, int l, int u) : xs(*this,n,l,u) {
00146     }
00148     OneArray(OneArray& s) : Space(s) {
00149       xs.update(*this,s.xs);
00150     }
00152     virtual Space* copy(void) {
00153       return new OneArray(*this);
00154     }
00156     IntArgs solution(void) {
00157       IntArgs a(xs.size());
00158       for (int i = 0 ; i < a.size() ; ++i)
00159         a[i] = xs[i].val();
00160       return a;
00161     }
00163     virtual IntArgs* expectedSolutions(void) { return NULL; }
00164   };
00165 
00166 #ifdef GECODE_HAS_SET_VARS
00167 
00168   class OneArraySet : public Space {
00169   public:
00171     SetVarArray xs;
00173     OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) {
00174     }
00176     OneArraySet(OneArraySet& s) : Space(s) {
00177       xs.update(*this,s.xs);
00178     }
00180     virtual Space* copy(void) {
00181       return new OneArraySet(*this);
00182     }
00184     IntSetArgs solution(void) {
00185       IntSetArgs a(xs.size());
00186       for (int i = 0 ; i < a.size() ; ++i) {
00187         SetVarGlbRanges glbranges(xs[i]);
00188         a[i] = IntSet(glbranges);
00189       }
00190       return a;
00191     }
00193     virtual IntSetArgs* expectedSolutions(void) { return NULL; }
00194   };
00195 #endif
00196 
00198   template <class T>
00199   class LDSB : public Base {
00200   public:
00202     unsigned int c_d;
00204     unsigned int a_d;
00206     LDSB(std::string label, unsigned int c=0, unsigned int a=0)
00207       : Test::Base("LDSB::" + label),
00208         c_d(c), a_d(a) {}
00210     bool run(void) {
00211       OneArray *s = new OneArray(T::n, T::l, T::u);
00212       T::setup(*s, s->xs);
00213       Search::Options o = Search::Options::def;
00214       if (c_d != 0) o.c_d = c_d;
00215       if (a_d != 0) o.a_d = a_d;
00216       DFS<OneArray> e(s,o);
00217       bool r = check(e, T::expectedSolutions());
00218       delete s;
00219       return r;
00220     }
00221   };
00222 
00223 #ifdef GECODE_HAS_SET_VARS
00224 
00225   template <class T>
00226   class LDSBSet : public Base {
00227   public:
00229     unsigned int c_d;
00231     unsigned int a_d;
00233     LDSBSet(std::string label, unsigned int c=0, unsigned int a=0)
00234       : Test::Base("LDSB::" + label),
00235         c_d(c), a_d(a) {}
00237     bool run(void) {
00238       OneArraySet *s = new OneArraySet(T::n, T::l, T::u);
00239       T::setup(*s, s->xs);
00240       Search::Options o = Search::Options::def;
00241       if (c_d != 0) o.c_d = c_d;
00242       if (a_d != 0) o.a_d = a_d;
00243       DFS<OneArraySet> e(s,o);
00244       bool r = check(e, T::expectedSolutions());
00245       delete s;
00246       return r;
00247     }
00248   };
00249 #endif
00250 
00251   // Test cases
00252 
00254   class VarSym1 {
00255   public:
00257     static const int n = 4;
00259     static const int l = 0;
00261     static const int u = 3;
00263     static void setup(Home home, IntVarArray& xs) {
00264       Symmetries syms;
00265       IntArgs indices({0,1,2,3});
00266       syms << VariableSymmetry(xs, indices);
00267       distinct(home, xs);
00268       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00269     }
00271     static std::vector<IntArgs> expectedSolutions(void) {
00272       static std::vector<IntArgs> expected;
00273       expected.clear();
00274       expected.push_back(IntArgs({0,1,2,3}));
00275       return expected;
00276     }
00277   };
00278 
00280   class VarSym1b {
00281   public:
00283     static const int n = 4;
00285     static const int l = 0;
00287     static const int u = 3;
00289     static void setup(Home home, IntVarArray& xs) {
00290       distinct(home, xs);
00291       Symmetries syms;
00292       syms << VariableSymmetry(xs);
00293       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00294     }
00296     static std::vector<IntArgs> expectedSolutions(void) {
00297       static std::vector<IntArgs> expected;
00298       expected.clear();
00299       expected.push_back(IntArgs({0,1,2,3}));
00300       return expected;
00301     }
00302   };
00303 
00305   class VarSym2 {
00306   public:
00308     static const int n = 4;
00310     static const int l = 0;
00312     static const int u = 3;
00314     static void setup(Home home, IntVarArray& xs) {
00315       Symmetries syms;
00316       IntArgs indices({0,1,2,3});
00317       syms << VariableSymmetry(xs);
00318       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00319     }
00321     static std::vector<IntArgs> expectedSolutions(void) {
00322       static std::vector<IntArgs> expected;
00323       expected.clear();
00324       expected.push_back(IntArgs({0,0,0,0}));
00325       expected.push_back(IntArgs({0,0,0,1}));
00326       expected.push_back(IntArgs({0,0,0,2}));
00327       expected.push_back(IntArgs({0,0,0,3}));
00328       expected.push_back(IntArgs({0,0,1,1}));
00329       expected.push_back(IntArgs({0,0,1,2}));
00330       expected.push_back(IntArgs({0,0,1,3}));
00331       expected.push_back(IntArgs({0,0,2,2}));
00332       expected.push_back(IntArgs({0,0,2,3}));
00333       expected.push_back(IntArgs({0,0,3,3}));
00334       expected.push_back(IntArgs({0,1,1,1}));
00335       expected.push_back(IntArgs({0,1,1,2}));
00336       expected.push_back(IntArgs({0,1,1,3}));
00337       expected.push_back(IntArgs({0,1,2,2}));
00338       expected.push_back(IntArgs({0,1,2,3}));
00339       expected.push_back(IntArgs({0,1,3,3}));
00340       expected.push_back(IntArgs({0,2,2,2}));
00341       expected.push_back(IntArgs({0,2,2,3}));
00342       expected.push_back(IntArgs({0,2,3,3}));
00343       expected.push_back(IntArgs({0,3,3,3}));
00344       expected.push_back(IntArgs({1,1,1,1}));
00345       expected.push_back(IntArgs({1,1,1,2}));
00346       expected.push_back(IntArgs({1,1,1,3}));
00347       expected.push_back(IntArgs({1,1,2,2}));
00348       expected.push_back(IntArgs({1,1,2,3}));
00349       expected.push_back(IntArgs({1,1,3,3}));
00350       expected.push_back(IntArgs({1,2,2,2}));
00351       expected.push_back(IntArgs({1,2,2,3}));
00352       expected.push_back(IntArgs({1,2,3,3}));
00353       expected.push_back(IntArgs({1,3,3,3}));
00354       expected.push_back(IntArgs({2,2,2,2}));
00355       expected.push_back(IntArgs({2,2,2,3}));
00356       expected.push_back(IntArgs({2,2,3,3}));
00357       expected.push_back(IntArgs({2,3,3,3}));
00358       expected.push_back(IntArgs({3,3,3,3}));
00359       return expected;
00360     }
00361   };
00362 
00364   class VarSym3 {
00365   public:
00367     static const int n = 4;
00369     static const int l = 0;
00371     static const int u = 3;
00373     static void setup(Home home, IntVarArray& xs) {
00374       Symmetries syms;
00375       distinct(home, xs);
00376       syms << VariableSymmetry(IntVarArgs() << xs[0] << xs[1]);
00377       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00378     }
00380     static std::vector<IntArgs> expectedSolutions(void) {
00381       static std::vector<IntArgs> expected;
00382       expected.clear();
00383       expected.push_back(IntArgs({0,1,2,3}));
00384       expected.push_back(IntArgs({0,1,3,2}));
00385       expected.push_back(IntArgs({0,2,1,3}));
00386       expected.push_back(IntArgs({0,2,3,1}));
00387       expected.push_back(IntArgs({0,3,1,2}));
00388       expected.push_back(IntArgs({0,3,2,1}));
00389       expected.push_back(IntArgs({1,2,0,3}));
00390       expected.push_back(IntArgs({1,2,3,0}));
00391       expected.push_back(IntArgs({1,3,0,2}));
00392       expected.push_back(IntArgs({1,3,2,0}));
00393       expected.push_back(IntArgs({2,3,0,1}));
00394       expected.push_back(IntArgs({2,3,1,0}));
00395       return expected;
00396     }
00397   };
00398 
00400   class VarSym4 {
00401   public:
00403     static const int n = 3;
00405     static const int l = 0;
00407     static const int u = 2;
00409     static void setup(Home home, IntVarArray& xs) {
00410       distinct(home, xs);
00411       Symmetries s;
00412       IntVarArgs symvars;
00413       symvars << xs[0];
00414       s << VariableSymmetry(symvars);
00415       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00416     }
00418     static std::vector<IntArgs> expectedSolutions(void) {
00419       static std::vector<IntArgs> expected;
00420       expected.clear();
00421       expected.push_back(IntArgs({0,1,2}));
00422       expected.push_back(IntArgs({0,2,1}));
00423       expected.push_back(IntArgs({1,0,2}));
00424       expected.push_back(IntArgs({1,2,0}));
00425       expected.push_back(IntArgs({2,0,1}));
00426       expected.push_back(IntArgs({2,1,0}));
00427       return expected;
00428     }
00429   };
00430 
00432   class VarSym5 {
00433   public:
00435     static const int n = 4;
00437     static const int l = 0;
00439     static const int u = 3;
00441     static void setup(Home home, IntVarArray& xs) {
00442       distinct(home, xs);
00443       Matrix<IntVarArray> m(xs, 4, 1);
00444       Symmetries s;
00445       s << VariableSymmetry(m.slice(0,2, 0,1));
00446       s << VariableSymmetry(m.slice(2,4, 0,1));
00447       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00448     }
00450     static std::vector<IntArgs> expectedSolutions(void) {
00451       static std::vector<IntArgs> expected;
00452       expected.clear();
00453       expected.push_back(IntArgs({0,1,2,3}));
00454       expected.push_back(IntArgs({0,2,1,3}));
00455       expected.push_back(IntArgs({0,3,1,2}));
00456       expected.push_back(IntArgs({1,2,0,3}));
00457       expected.push_back(IntArgs({1,3,0,2}));
00458       expected.push_back(IntArgs({2,3,0,1}));
00459       return expected;
00460     }
00461   };
00462 
00464   class MatSym1 {
00465   public:
00467     static const int n = 6;
00469     static const int l = 0;
00471     static const int u = 1;
00473     static void setup(Home home, IntVarArray& xs) {
00474       Matrix<IntVarArray> m(xs, 2, 3);
00475       Symmetries s;
00476       s << rows_interchange(m);
00477       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00478     }
00480     static std::vector<IntArgs> expectedSolutions(void) {
00481       static std::vector<IntArgs> expected;
00482       expected.clear();
00483       expected.push_back(IntArgs({0,0, 0,0, 0,0}));
00484       expected.push_back(IntArgs({0,0, 0,0, 0,1}));
00485       expected.push_back(IntArgs({0,0, 0,0, 1,0}));
00486       expected.push_back(IntArgs({0,0, 0,0, 1,1}));
00487       expected.push_back(IntArgs({0,0, 0,1, 0,0}));
00488       expected.push_back(IntArgs({0,0, 0,1, 0,1}));
00489       expected.push_back(IntArgs({0,0, 0,1, 1,0}));
00490       expected.push_back(IntArgs({0,0, 0,1, 1,1}));
00491       expected.push_back(IntArgs({0,0, 1,0, 1,0}));
00492       expected.push_back(IntArgs({0,0, 1,0, 1,1}));
00493       expected.push_back(IntArgs({0,0, 1,1, 1,1}));
00494       expected.push_back(IntArgs({0,1, 0,0, 0,0}));
00495       expected.push_back(IntArgs({0,1, 0,0, 0,1}));
00496       expected.push_back(IntArgs({0,1, 0,0, 1,0}));
00497       expected.push_back(IntArgs({0,1, 0,0, 1,1}));
00498       expected.push_back(IntArgs({0,1, 0,1, 0,0}));
00499       expected.push_back(IntArgs({0,1, 0,1, 0,1}));
00500       expected.push_back(IntArgs({0,1, 0,1, 1,0}));
00501       expected.push_back(IntArgs({0,1, 0,1, 1,1}));
00502       expected.push_back(IntArgs({0,1, 1,0, 1,0}));
00503       expected.push_back(IntArgs({0,1, 1,0, 1,1}));
00504       expected.push_back(IntArgs({0,1, 1,1, 1,1}));
00505       expected.push_back(IntArgs({1,0, 1,0, 1,0}));
00506       expected.push_back(IntArgs({1,0, 1,0, 1,1}));
00507       expected.push_back(IntArgs({1,0, 1,1, 1,1}));
00508       expected.push_back(IntArgs({1,1, 1,1, 1,1}));
00509       return expected;
00510     }
00511   };
00512 
00514   class MatSym2 {
00515   public:
00517     static const int n = 6;
00519     static const int l = 0;
00521     static const int u = 1;
00523     static void setup(Home home, IntVarArray& xs) {
00524       Matrix<IntVarArray> m(xs, 2, 3);
00525       Symmetries s;
00526       s << columns_interchange(m);
00527       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00528     }
00530     static std::vector<IntArgs> expectedSolutions(void) {
00531       static std::vector<IntArgs> expected;
00532       expected.clear();
00533       expected.push_back(IntArgs({0,0, 0,0, 0,0}));
00534       expected.push_back(IntArgs({0,0, 0,0, 0,1}));
00535       expected.push_back(IntArgs({0,0, 0,0, 1,1}));
00536       expected.push_back(IntArgs({0,0, 0,1, 0,0}));
00537       expected.push_back(IntArgs({0,0, 0,1, 0,1}));
00538       expected.push_back(IntArgs({0,0, 0,1, 1,0}));
00539       expected.push_back(IntArgs({0,0, 0,1, 1,1}));
00540       expected.push_back(IntArgs({0,0, 1,1, 0,0}));
00541       expected.push_back(IntArgs({0,0, 1,1, 0,1}));
00542       expected.push_back(IntArgs({0,0, 1,1, 1,1}));
00543       expected.push_back(IntArgs({0,1, 0,0, 0,0}));
00544       expected.push_back(IntArgs({0,1, 0,0, 0,1}));
00545       expected.push_back(IntArgs({0,1, 0,0, 1,0}));
00546       expected.push_back(IntArgs({0,1, 0,0, 1,1}));
00547       expected.push_back(IntArgs({0,1, 0,1, 0,0}));
00548       expected.push_back(IntArgs({0,1, 0,1, 0,1}));
00549       expected.push_back(IntArgs({0,1, 0,1, 1,0}));
00550       expected.push_back(IntArgs({0,1, 0,1, 1,1}));
00551       expected.push_back(IntArgs({0,1, 1,0, 0,0}));
00552       expected.push_back(IntArgs({0,1, 1,0, 0,1}));
00553       expected.push_back(IntArgs({0,1, 1,0, 1,0}));
00554       expected.push_back(IntArgs({0,1, 1,0, 1,1}));
00555       expected.push_back(IntArgs({0,1, 1,1, 0,0}));
00556       expected.push_back(IntArgs({0,1, 1,1, 0,1}));
00557       expected.push_back(IntArgs({0,1, 1,1, 1,0}));
00558       expected.push_back(IntArgs({0,1, 1,1, 1,1}));
00559       expected.push_back(IntArgs({1,1, 0,0, 0,0}));
00560       expected.push_back(IntArgs({1,1, 0,0, 0,1}));
00561       expected.push_back(IntArgs({1,1, 0,0, 1,1}));
00562       expected.push_back(IntArgs({1,1, 0,1, 0,0}));
00563       expected.push_back(IntArgs({1,1, 0,1, 0,1}));
00564       expected.push_back(IntArgs({1,1, 0,1, 1,0}));
00565       expected.push_back(IntArgs({1,1, 0,1, 1,1}));
00566       expected.push_back(IntArgs({1,1, 1,1, 0,0}));
00567       expected.push_back(IntArgs({1,1, 1,1, 0,1}));
00568       expected.push_back(IntArgs({1,1, 1,1, 1,1}));
00569       return expected;
00570     }
00571   };
00572 
00574   class MatSym3 {
00575   public:
00577     static const int n = 6;
00579     static const int l = 0;
00581     static const int u = 1;
00583     static void setup(Home home, IntVarArray& xs) {
00584       Matrix<IntVarArray> m(xs, 2, 3);
00585       Symmetries s;
00586       s << rows_interchange(m);
00587       s << columns_interchange(m);
00588       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00589     }
00591     static std::vector<IntArgs> expectedSolutions(void) {
00592       static std::vector<IntArgs> expected;
00593       expected.clear();
00594       expected.push_back(IntArgs({0,0, 0,0, 0,0}));
00595       expected.push_back(IntArgs({0,0, 0,0, 0,1}));
00596       expected.push_back(IntArgs({0,0, 0,0, 1,1}));
00597       expected.push_back(IntArgs({0,0, 0,1, 0,0}));
00598       expected.push_back(IntArgs({0,0, 0,1, 0,1}));
00599       expected.push_back(IntArgs({0,0, 0,1, 1,0}));
00600       expected.push_back(IntArgs({0,0, 0,1, 1,1}));
00601       expected.push_back(IntArgs({0,0, 1,1, 1,1}));
00602       expected.push_back(IntArgs({0,1, 0,0, 0,0}));
00603       expected.push_back(IntArgs({0,1, 0,0, 0,1}));
00604       expected.push_back(IntArgs({0,1, 0,0, 1,0}));
00605       expected.push_back(IntArgs({0,1, 0,0, 1,1}));
00606       expected.push_back(IntArgs({0,1, 0,1, 0,0}));
00607       expected.push_back(IntArgs({0,1, 0,1, 0,1}));
00608       expected.push_back(IntArgs({0,1, 0,1, 1,0}));
00609       expected.push_back(IntArgs({0,1, 0,1, 1,1}));
00610       expected.push_back(IntArgs({0,1, 1,0, 1,0}));
00611       expected.push_back(IntArgs({0,1, 1,0, 1,1}));
00612       expected.push_back(IntArgs({0,1, 1,1, 1,1}));
00613       expected.push_back(IntArgs({1,1, 1,1, 1,1}));
00614       return expected;
00615     }
00616   };
00617 
00619   class MatSym4 {
00620   public:
00622     static const int n = 4;
00624     static const int l = 0;
00626     static const int u = 1;
00628     static void setup(Home home, IntVarArray& xs) {
00629       Matrix<IntVarArray> m(xs, 1, 4);
00630       Symmetries s;
00631       s << rows_reflect(m);
00632       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00633     }
00635     static std::vector<IntArgs> expectedSolutions(void) {
00636       static std::vector<IntArgs> expected;
00637       expected.clear();
00638       expected.push_back(IntArgs({0, 0, 0, 0}));
00639       expected.push_back(IntArgs({0, 0, 0, 1}));
00640       expected.push_back(IntArgs({0, 0, 1, 0}));
00641       expected.push_back(IntArgs({0, 0, 1, 1}));
00642       expected.push_back(IntArgs({0, 1, 0, 0}));
00643       expected.push_back(IntArgs({0, 1, 0, 1}));
00644       expected.push_back(IntArgs({0, 1, 1, 0}));
00645       expected.push_back(IntArgs({0, 1, 1, 1}));
00646       expected.push_back(IntArgs({1, 0, 0, 1}));
00647       expected.push_back(IntArgs({1, 0, 1, 1}));
00648       expected.push_back(IntArgs({1, 1, 1, 1}));
00649       return expected;
00650     }
00651   };
00652 
00654   class SimIntVarSym1 {
00655   public:
00657     static const int n = 12;
00659     static const int l = 0;
00661     static const int u = 3;
00663     static void setup(Home home, IntVarArray& xs) {
00664       Matrix<IntVarArray> m(xs, 3, 4);
00665       // The values in the first column are distinct.
00666       distinct(home, m.col(0));
00667       // Each row sums to 3.
00668       for (int i = 0 ; i < 4 ; ++i)
00669         linear(home, m.row(i), IRT_EQ, 3);
00670 
00671       // Rows are interchangeable.
00672       Symmetries s;
00673       s << VariableSequenceSymmetry(xs, 3);
00674       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00675     }
00677     static std::vector<IntArgs> expectedSolutions(void) {
00678       static std::vector<IntArgs> expected;
00679       expected.clear();
00680       expected.push_back(IntArgs({0,0,3, 1,0,2, 2,0,1, 3,0,0}));
00681       expected.push_back(IntArgs({0,0,3, 1,0,2, 2,1,0, 3,0,0}));
00682       expected.push_back(IntArgs({0,0,3, 1,1,1, 2,0,1, 3,0,0}));
00683       expected.push_back(IntArgs({0,0,3, 1,1,1, 2,1,0, 3,0,0}));
00684       expected.push_back(IntArgs({0,0,3, 1,2,0, 2,0,1, 3,0,0}));
00685       expected.push_back(IntArgs({0,0,3, 1,2,0, 2,1,0, 3,0,0}));
00686       expected.push_back(IntArgs({0,1,2, 1,0,2, 2,0,1, 3,0,0}));
00687       expected.push_back(IntArgs({0,1,2, 1,0,2, 2,1,0, 3,0,0}));
00688       expected.push_back(IntArgs({0,1,2, 1,1,1, 2,0,1, 3,0,0}));
00689       expected.push_back(IntArgs({0,1,2, 1,1,1, 2,1,0, 3,0,0}));
00690       expected.push_back(IntArgs({0,1,2, 1,2,0, 2,0,1, 3,0,0}));
00691       expected.push_back(IntArgs({0,1,2, 1,2,0, 2,1,0, 3,0,0}));
00692       expected.push_back(IntArgs({0,2,1, 1,0,2, 2,0,1, 3,0,0}));
00693       expected.push_back(IntArgs({0,2,1, 1,0,2, 2,1,0, 3,0,0}));
00694       expected.push_back(IntArgs({0,2,1, 1,1,1, 2,0,1, 3,0,0}));
00695       expected.push_back(IntArgs({0,2,1, 1,1,1, 2,1,0, 3,0,0}));
00696       expected.push_back(IntArgs({0,2,1, 1,2,0, 2,0,1, 3,0,0}));
00697       expected.push_back(IntArgs({0,2,1, 1,2,0, 2,1,0, 3,0,0}));
00698       expected.push_back(IntArgs({0,3,0, 1,0,2, 2,0,1, 3,0,0}));
00699       expected.push_back(IntArgs({0,3,0, 1,0,2, 2,1,0, 3,0,0}));
00700       expected.push_back(IntArgs({0,3,0, 1,1,1, 2,0,1, 3,0,0}));
00701       expected.push_back(IntArgs({0,3,0, 1,1,1, 2,1,0, 3,0,0}));
00702       expected.push_back(IntArgs({0,3,0, 1,2,0, 2,0,1, 3,0,0}));
00703       expected.push_back(IntArgs({0,3,0, 1,2,0, 2,1,0, 3,0,0}));
00704       return expected;
00705     }
00706   };
00707 
00709   class SimIntVarSym2 {
00711     static const int nrows = 4;
00713     static const int ncols = 3;
00714   public:
00716     static const int n = nrows*ncols;
00718     static const int l = 0;
00720     static const int u = 3;
00722     static void setup(Home home, IntVarArray& xs) {
00723       Matrix<IntVarArray> m(xs, 3, 4);
00724       // The values in the first column are distinct.
00725       distinct(home, m.col(0));
00726       // Each row sums to 3.
00727       for (int i = 0 ; i < nrows ; ++i)
00728         linear(home, m.row(i), IRT_EQ, 3);
00729 
00730       Symmetries s;
00731 
00732       IntArgs a = IntArgs::create(n, 0);
00733       // Rows are interchangeable.
00734       s << VariableSequenceSymmetry(xs, 3);
00735       // Elements (i,1) and (i,2) in row i are interchangeable,
00736       // separately for each row.
00737       for (int i = 0 ; i < nrows ; i++) {
00738         IntVarArgs symvars;
00739         symvars << m(1,i) << m(2,i);
00740         s << VariableSymmetry(symvars);
00741       }
00742       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00743     }
00745     static std::vector<IntArgs> expectedSolutions(void) {
00746       static std::vector<IntArgs> expected;
00747       expected.clear();
00748       expected.push_back(IntArgs({0,0,3, 1,0,2, 2,0,1, 3,0,0}));
00749       expected.push_back(IntArgs({0,0,3, 1,1,1, 2,0,1, 3,0,0}));
00750       expected.push_back(IntArgs({0,1,2, 1,0,2, 2,0,1, 3,0,0}));
00751       expected.push_back(IntArgs({0,1,2, 1,1,1, 2,0,1, 3,0,0}));
00752       return expected;
00753     }
00754   };
00755 
00757   class SimIntValSym1 {
00758   public:
00760     static const int n = 2;
00762     static const int l = 0;
00764     static const int u = 6;
00766     static void setup(Home home, IntVarArray& xs) {
00767       rel(home, xs[0] + xs[1] == 6);
00768       // Values 0,1,2 are symmetric with 6,5,4.
00769       IntArgs values({0,1,2, 6,5,4});
00770       Symmetries s;
00771       s << ValueSequenceSymmetry(values, 3);
00772       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00773     }
00775     static std::vector<IntArgs> expectedSolutions(void) {
00776       static std::vector<IntArgs> expected;
00777       expected.clear();
00778       expected.push_back(IntArgs({0,6}));
00779       expected.push_back(IntArgs({1,5}));
00780       expected.push_back(IntArgs({2,4}));
00781       expected.push_back(IntArgs({3,3}));
00782       return expected;
00783     }
00784   };
00785 
00787   class SimIntValSym2 {
00788   public:
00790     static const int n = 3;
00792     static const int l = 0;
00794     static const int u = 8;
00796     static void setup(Home home, IntVarArray& xs) {
00797       TupleSet tuples(3);
00798       tuples.add({1,1,1}).add({4,4,4}).add({7,7,7})
00799         .add({0,1,5}).add({0,1,8}).add({3,4,2})
00800         .add({3,4,8}).add({6,7,2}).add({6,7,5})
00801         .finalize();
00802       extensional(home, xs, tuples);
00803 
00804       // Values 0,1,2 are symmetric with 3,4,5, and with 6,7,8.
00805       IntArgs values({0,1,2, 3,4,5, 6,7,8});
00806       Symmetries s;
00807       s << ValueSequenceSymmetry(values, 3);
00808       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00809     }
00811     static std::vector<IntArgs> expectedSolutions(void) {
00812       static std::vector<IntArgs> expected;
00813       expected.clear();
00814       expected.push_back(IntArgs({0,1,5}));
00815       expected.push_back(IntArgs({1,1,1}));
00816       return expected;
00817     }
00818   };
00819 
00821   class SimIntValSym3 {
00822   public:
00824     static const int n = 2;
00826     static const int l = 0;
00828     static const int u = 6;
00830     static void setup(Home home, IntVarArray& xs) {
00831       rel(home, xs[0] + xs[1] == 6);
00832       Symmetries s;
00833       // Values 0,1,2 are symmetric with 6,5,4.
00834       s << values_reflect(0,6);
00835       branch(home, xs, INT_VAR_NONE(), INT_VAL_MED(), s);
00836     }
00838     static std::vector<IntArgs> expectedSolutions(void) {
00839       static std::vector<IntArgs> expected;
00840       expected.clear();
00841       expected.push_back(IntArgs({3,3}));
00842       expected.push_back(IntArgs({2,4}));
00843       expected.push_back(IntArgs({1,5}));
00844       expected.push_back(IntArgs({0,6}));
00845       return expected;
00846     }
00847   };
00848 
00850   class ValSym1 {
00851   public:
00853     static const int n = 4;
00855     static const int l = 0;
00857     static const int u = 3;
00859     static void setup(Home home, IntVarArray& xs) {
00860       distinct(home, xs);
00861       Symmetries s;
00862       IntArgs indices({0,1,2,3});
00863       s << ValueSymmetry(indices);
00864       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00865     }
00867     static std::vector<IntArgs> expectedSolutions(void) {
00868       static std::vector<IntArgs> expected;
00869       expected.clear();
00870       expected.push_back(IntArgs({0,1,2,3}));
00871       return expected;
00872     }
00873   };
00874 
00876   class ValSym1b {
00877   public:
00879     static const int n = 4;
00881     static const int l = 0;
00883     static const int u = 3;
00885     static void setup(Home home, IntVarArray& xs) {
00886       distinct(home, xs);
00887       Symmetries s;
00888       s << ValueSymmetry(xs[0]);
00889       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00890     }
00892     static std::vector<IntArgs> expectedSolutions(void) {
00893       static std::vector<IntArgs> expected;
00894       expected.clear();
00895       expected.push_back(IntArgs({0,1,2,3}));
00896       return expected;
00897     }
00898   };
00899 
00901   class ValSym1c {
00902   public:
00904     static const int n = 4;
00906     static const int l = 0;
00908     static const int u = 3;
00910     static void setup(Home home, IntVarArray& xs) {
00911       distinct(home, xs);
00912       Symmetries s;
00913       s << ValueSymmetry(xs[0]);
00914       branch(home, xs, INT_VAR_NONE(), INT_VAL_MAX(), s);
00915     }
00917     static std::vector<IntArgs> expectedSolutions(void) {
00918       static std::vector<IntArgs> expected;
00919       expected.clear();
00920       expected.push_back(IntArgs({3,2,1,0}));
00921       return expected;
00922     }
00923   };
00924 
00926   class ValSym2 {
00927   public:
00929     static const int n = 4;
00931     static const int l = 0;
00933     static const int u = 3;
00935     static void setup(Home home, IntVarArray& xs) {
00936       Symmetries s;
00937       IntArgs indices({0,1,2,3});
00938       s << ValueSymmetry(indices);
00939       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00940     }
00942     static std::vector<IntArgs> expectedSolutions(void) {
00943       static std::vector<IntArgs> expected;
00944       expected.clear();
00945       expected.push_back(IntArgs({0,0,0,0}));
00946       expected.push_back(IntArgs({0,0,0,1}));
00947       expected.push_back(IntArgs({0,0,1,0}));
00948       expected.push_back(IntArgs({0,0,1,1}));
00949       expected.push_back(IntArgs({0,0,1,2}));
00950       expected.push_back(IntArgs({0,1,0,0}));
00951       expected.push_back(IntArgs({0,1,0,1}));
00952       expected.push_back(IntArgs({0,1,0,2}));
00953       expected.push_back(IntArgs({0,1,1,0}));
00954       expected.push_back(IntArgs({0,1,1,1}));
00955       expected.push_back(IntArgs({0,1,1,2}));
00956       expected.push_back(IntArgs({0,1,2,0}));
00957       expected.push_back(IntArgs({0,1,2,1}));
00958       expected.push_back(IntArgs({0,1,2,2}));
00959       expected.push_back(IntArgs({0,1,2,3}));
00960       return expected;
00961     }
00962   };
00963 
00965   class ValSym2b {
00966   public:
00968     static const int n = 4;
00970     static const int l = 0;
00972     static const int u = 3;
00974     static void setup(Home home, IntVarArray& xs) {
00975       Symmetries s;
00976       s << ValueSymmetry(xs[0]);
00977       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00978     }
00980     static std::vector<IntArgs> expectedSolutions(void) {
00981       static std::vector<IntArgs> expected;
00982       expected.clear();
00983       expected.push_back(IntArgs({0,0,0,0}));
00984       expected.push_back(IntArgs({0,0,0,1}));
00985       expected.push_back(IntArgs({0,0,1,0}));
00986       expected.push_back(IntArgs({0,0,1,1}));
00987       expected.push_back(IntArgs({0,0,1,2}));
00988       expected.push_back(IntArgs({0,1,0,0}));
00989       expected.push_back(IntArgs({0,1,0,1}));
00990       expected.push_back(IntArgs({0,1,0,2}));
00991       expected.push_back(IntArgs({0,1,1,0}));
00992       expected.push_back(IntArgs({0,1,1,1}));
00993       expected.push_back(IntArgs({0,1,1,2}));
00994       expected.push_back(IntArgs({0,1,2,0}));
00995       expected.push_back(IntArgs({0,1,2,1}));
00996       expected.push_back(IntArgs({0,1,2,2}));
00997       expected.push_back(IntArgs({0,1,2,3}));
00998       return expected;
00999     }
01000   };
01001 
01003   class ValSym3 {
01004   public:
01006     static const int n = 4;
01008     static const int l = 0;
01010     static const int u = 3;
01012     static void setup(Home home, IntVarArray& xs) {
01013       distinct(home, xs);
01014       Symmetries s;
01015       IntArgs indices({0,1});
01016       s << ValueSymmetry(indices);
01017       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01018     }
01020     static std::vector<IntArgs> expectedSolutions(void) {
01021       static std::vector<IntArgs> expected;
01022       expected.clear();
01023       expected.push_back(IntArgs({0,1,2,3}));
01024       expected.push_back(IntArgs({0,1,3,2}));
01025       expected.push_back(IntArgs({0,2,1,3}));
01026       expected.push_back(IntArgs({0,2,3,1}));
01027       expected.push_back(IntArgs({0,3,1,2}));
01028       expected.push_back(IntArgs({0,3,2,1}));
01029       expected.push_back(IntArgs({2,0,1,3}));
01030       expected.push_back(IntArgs({2,0,3,1}));
01031       expected.push_back(IntArgs({2,3,0,1}));
01032       expected.push_back(IntArgs({3,0,1,2}));
01033       expected.push_back(IntArgs({3,0,2,1}));
01034       expected.push_back(IntArgs({3,2,0,1}));
01035       return expected;
01036     }
01037   };
01038 
01040   class ValSym4 {
01041   public:
01043     static const int n = 3;
01045     static const int l = 0;
01047     static const int u = 2;
01049     static void setup(Home home, IntVarArray& xs) {
01050       distinct(home, xs);
01051       Symmetries s;
01052       IntArgs indices({0});
01053       s << ValueSymmetry(indices);
01054       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01055     }
01057     static std::vector<IntArgs> expectedSolutions(void) {
01058       static std::vector<IntArgs> expected;
01059       expected.clear();
01060       expected.push_back(IntArgs({0,1,2}));
01061       expected.push_back(IntArgs({0,2,1}));
01062       expected.push_back(IntArgs({1,0,2}));
01063       expected.push_back(IntArgs({1,2,0}));
01064       expected.push_back(IntArgs({2,0,1}));
01065       expected.push_back(IntArgs({2,1,0}));
01066       return expected;
01067     }
01068   };
01069 
01071   class ValSym5 {
01072   public:
01074     static const int n = 4;
01076     static const int l = 0;
01078     static const int u = 3;
01080     static void setup(Home home, IntVarArray& xs) {
01081       distinct(home, xs);
01082       Symmetries s;
01083       IntArgs indices0({0,1});
01084       IntArgs indices1({2,3});
01085       s << ValueSymmetry(indices0);
01086       s << ValueSymmetry(indices1);
01087       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01088     }
01090     static std::vector<IntArgs> expectedSolutions(void) {
01091       static std::vector<IntArgs> expected;
01092       expected.clear();
01093       expected.push_back(IntArgs({0,1,2,3}));
01094       expected.push_back(IntArgs({0,2,1,3}));
01095       expected.push_back(IntArgs({0,2,3,1}));
01096       expected.push_back(IntArgs({2,0,1,3}));
01097       expected.push_back(IntArgs({2,0,3,1}));
01098       expected.push_back(IntArgs({2,3,0,1}));
01099       return expected;
01100     }
01101   };
01102 
01104   class VarValSym1 {
01105   public:
01107     static const int n = 4;
01109     static const int l = 0;
01111     static const int u = 3;
01113     static void setup(Home home, IntVarArray& xs) {
01114       Symmetries s;
01115       s << VariableSymmetry(xs);
01116       s << ValueSymmetry(IntArgs::create(4,0));
01117       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01118     }
01120     static std::vector<IntArgs> expectedSolutions(void) {
01121       static std::vector<IntArgs> expected;
01122       expected.clear();
01123       expected.push_back(IntArgs({0,0,0,0}));
01124       expected.push_back(IntArgs({0,0,0,1}));
01125       expected.push_back(IntArgs({0,0,1,1}));
01126       expected.push_back(IntArgs({0,0,1,2}));
01127       expected.push_back(IntArgs({0,1,1,1}));
01128       expected.push_back(IntArgs({0,1,1,2}));
01129       expected.push_back(IntArgs({0,1,2,2}));  // This solution is symmetric to the previous one.
01130       expected.push_back(IntArgs({0,1,2,3}));
01131       return expected;
01132     }
01133   };
01134 
01136   class LDSBLatin : public Base {
01137   public:
01139     class Latin : public Space {
01140     public:
01141       IntVarArray xs;
01142       Latin(int n = 4) : xs(*this, n*n, 1, n)
01143       {
01144         Matrix<IntVarArray> m(xs, n, n);
01145         for (int i = 0 ; i < n ; i++) {
01146           distinct(*this, m.col(i));
01147           distinct(*this, m.row(i));
01148         }
01149         Symmetries s;
01150         s << rows_interchange(m);
01151         s << columns_interchange(m);
01152         s << ValueSymmetry(IntSet(1,n));
01153         branch(*this, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01154       }
01155       // Search support.
01156       Latin(Latin& s) : Space(s)
01157       { xs.update(*this, s.xs); }
01158       virtual Space* copy(void)
01159       { return new Latin(*this); }
01160       IntArgs solution(void) {
01161         IntArgs a(xs.size());
01162         for (int i = 0 ; i < a.size() ; ++i)
01163           a[i] = xs[i].val();
01164         return a;
01165       }
01166 
01168       static std::vector<IntArgs> expectedSolutions(void) {
01169         static std::vector<IntArgs> expected;
01170         expected.clear();
01171         expected.push_back(IntArgs({1,2,3,4, 2,1,4,3, 3,4,1,2, 4,3,2,1}));
01172         expected.push_back(IntArgs({1,2,3,4, 2,1,4,3, 3,4,2,1, 4,3,1,2}));
01173         expected.push_back(IntArgs({1,2,3,4, 2,3,4,1, 3,4,1,2, 4,1,2,3}));
01174         expected.push_back(IntArgs({1,2,3,4, 2,4,1,3, 3,1,4,2, 4,3,2,1}));
01175         return expected;
01176       }
01177     };
01179     LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {}
01181     bool run(void) {
01182       Latin *s = new Latin();
01183       DFS<Latin> e(s);
01184       bool r = check(e, Latin::expectedSolutions());
01185       delete s;
01186       return r;
01187     }
01188   };
01189 
01190   /* This test should fail if the recomputation-handling does not work
01191    * properly.
01192    *
01193    * Why recomputation can be a problem
01194    * ==================================
01195    *
01196    * Every branch point in LDSB is binary, with a left and a right
01197    * branch.  Whenever backtracking happens -- when a right branch is
01198    * explored -- LDSB computes a set of symmetric literals to
01199    * exclude.
01200    *
01201    * !!! This calculation may depend on the current domains of the
01202    * !!! variables.
01203    *
01204    * During recomputation, parts of the search tree are replayed.  To
01205    * be specific, the branching constraints are posted, but no
01206    * propagation happens.  This means that at a given branch point,
01207    * the domains during recomputation may be different (weaker) than
01208    * they were the first time during search.
01209    *
01210    * !!! This *cannot* cause solutions to be missed --- LDSB will not
01211    * !!! be incorrect --- but it *does* change what will be pruned.
01212    *
01213    * If recomputation is not handled properly, the difference in
01214    * domains will cause extra solutions to be found.  This is a result
01215    * of symmetries failing to be broken.
01216    *
01217    */
01218 
01220   class Recomputation {
01221   public:
01223     static const int n = 4;
01225     static const int l = 0;
01227     static const int u = 1;
01229     static void setup(Home home, IntVarArray& xs) {
01230       TupleSet t(2);
01231       t.add({0,0}).add({1,1}).finalize();
01232       IntVarArgs va;
01233       va << xs[0] << xs[2];
01234       extensional(home, va, t);
01235       Symmetries syms;
01236       syms << VariableSequenceSymmetry(xs, 2);
01237       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
01238     }
01240     static std::vector<IntArgs> expectedSolutions(void) {
01241       static std::vector<IntArgs> expected;
01242       expected.clear();
01243       expected.push_back(IntArgs({0,0,0,0}));
01244       expected.push_back(IntArgs({0,0,0,1}));
01245 
01246       // This is the solution that will be found if recomputation is
01247       // not handled.  After branching on x[0]=0, we try x[1]=0.  When
01248       // x[1]=0 backtracks, the symmetry [x[0],x[1]] <-> [x[2],x[3]]
01249       // is active --- but only after propagation!  (Without
01250       // propagation, we do not have x[2]=0.)  If propagation happens,
01251       // we know that symmetry is active and we can post x[3]!=0.  If
01252       // it doesn't, we don't use the symmetry and we find a solution
01253       // where x[3]=0.
01254 
01255       // expected.push_back(IntArgs({0,1,0,0}));
01256 
01257       expected.push_back(IntArgs({0,1,0,1}));
01258 
01259       expected.push_back(IntArgs({1,0,1,0}));
01260       expected.push_back(IntArgs({1,0,1,1}));
01261       expected.push_back(IntArgs({1,1,1,1}));
01262       return expected;
01263     }
01264   };
01265 
01266   double position(const Space& home, IntVar x, int i) {
01267     (void) home;
01268     (void) x;
01269     return i;
01270   }
01271 
01273   class TieBreak {
01274   public:
01276     static const int n = 4;
01278     static const int l = 0;
01280     static const int u = 3;
01282     static void setup(Home home, IntVarArray& xs) {
01283       Symmetries syms;
01284       IntArgs indices({0,1,2,3});
01285       syms << VariableSymmetry(xs, indices);
01286       distinct(home, xs);
01287       // This redundant constraint is to trick the variable
01288       // heuristic.
01289       rel(home, xs[1] != xs[2]);
01290       // xs[1] and xs[2] have higher degree than the others, so they
01291       // are considered first.  xs[2] is higher than x[1] by the merit
01292       // function, so it is assigned first.  Now all remaining
01293       // variables have the same degree, so they are searched in
01294       // reverse order (according to the merit function).  So, the
01295       // solution found is {3, 2, 0, 1}.
01296       branch(home, xs, tiebreak(INT_VAR_DEGREE_MAX(), INT_VAR_MERIT_MAX(position)), INT_VAL_MIN(), syms);
01297     }
01299     static std::vector<IntArgs> expectedSolutions(void) {
01300       static std::vector<IntArgs> expected;
01301       expected.clear();
01302       expected.push_back(IntArgs({3,2,0,1}));
01303       return expected;
01304     }
01305   };
01306 
01307 #ifdef GECODE_HAS_SET_VARS
01308 
01309   IntSetArgs ISA(int n, ...) {
01310     IntSetArgs sets;
01311     va_list args;
01312     va_start(args, n);
01313     int i = 0;
01314     IntArgs a;
01315     while (i < n) {
01316       int x = va_arg(args,int);
01317       if (x == -1) {
01318         i++;
01319         sets << IntSet(a);
01320         a = IntArgs();
01321       } else {
01322         a << x;
01323       }
01324     }
01325     va_end(args);
01326     return sets;
01327   }
01328 
01330   class SetVarSym1 {
01331   public:
01333     static const int n = 2;
01335     static const int l = 0;
01337     static const int u = 1;
01339     static void setup(Home home, SetVarArray& xs) {
01340       Symmetries syms;
01341       syms << VariableSymmetry(xs);
01342       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01343     }
01345     static std::vector<IntSetArgs> expectedSolutions(void) {
01346       static std::vector<IntSetArgs> expected;
01347       expected.clear();
01348       expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
01349       expected.push_back(ISA(2, 0,1,-1, 0,  -1));
01350       expected.push_back(ISA(2, 0,1,-1,   1,-1));
01351       expected.push_back(ISA(2, 0,1,-1,     -1));
01352       expected.push_back(ISA(2, 0,  -1, 0,1,-1));
01353       expected.push_back(ISA(2, 0,  -1, 0,  -1));
01354       expected.push_back(ISA(2, 0,  -1,   1,-1));
01355       expected.push_back(ISA(2, 0,  -1,     -1));
01356       // expected.push_back(ISA(2,   1,-1, 0,1,-1));
01357       // expected.push_back(ISA(2,   1,-1, 0,  -1));
01358       expected.push_back(ISA(2,   1,-1,   1,-1));
01359       expected.push_back(ISA(2,   1,-1,     -1));
01360       // expected.push_back(ISA(2,     -1, 0,1,-1));
01361       // expected.push_back(ISA(2,     -1, 0,  -1));
01362       // expected.push_back(ISA(2,     -1,   1,-1));
01363       expected.push_back(ISA(2,     -1,     -1));
01364       return expected;
01365     }
01366   };
01367 
01368   /*
01369    * This tests the special handling of value symmetries on set
01370    * values.  Look at the third solution (commented out) below.  The
01371    * first variable has been assigned to {0,1}.  If the value symmetry
01372    * is not handled specially, then we will consider the value
01373    * symmetry broken because the search has touched each value.
01374    * However, because both values have been assigned to the same
01375    * variable, 0 and 1 are still symmetric.  Therefore, the third
01376    * solution is symmetric to the second one and should be excluded.
01377    */
01378 
01380   class SetValSym1 {
01381   public:
01383     static const int n = 2;
01385     static const int l = 0;
01387     static const int u = 1;
01389     static void setup(Home home, SetVarArray& xs) {
01390       Symmetries syms;
01391       syms << ValueSymmetry(IntArgs({0,1}));
01392       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01393     }
01395     static std::vector<IntSetArgs> expectedSolutions(void) {
01396       static std::vector<IntSetArgs> expected;
01397       expected.clear();
01398       expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
01399       expected.push_back(ISA(2, 0,1,-1, 0,  -1));
01400       // expected.push_back(ISA(2, 0,1,-1,   1,-1)); // XXXXX bad solution
01401       expected.push_back(ISA(2, 0,1,-1,     -1));
01402       expected.push_back(ISA(2, 0,  -1, 0,1,-1));
01403       expected.push_back(ISA(2, 0,  -1, 0,  -1));
01404       expected.push_back(ISA(2, 0,  -1,   1,-1));
01405       expected.push_back(ISA(2, 0,  -1,     -1));
01406       // expected.push_back(ISA(2,   1,-1, 0,1,-1));
01407       // expected.push_back(ISA(2,   1,-1, 0,  -1));
01408       // expected.push_back(ISA(2,   1,-1,   1,-1));
01409       // expected.push_back(ISA(2,   1,-1,     -1));
01410       expected.push_back(ISA(2,     -1, 0,1,-1));
01411       expected.push_back(ISA(2,     -1, 0,  -1));
01412       // expected.push_back(ISA(2,     -1,   1,-1));
01413       expected.push_back(ISA(2,     -1,     -1));
01414       return expected;
01415     }
01416   };
01417 
01419   class SetValSym2 {
01420   public:
01422     static const int n = 3;
01424     static const int l = 1;
01426     static const int u = 4;
01428     static void setup(Home home, SetVarArray& xs) {
01429       Symmetries syms;
01430       syms << ValueSymmetry(IntArgs({1,2,3,4}));
01431       for (int i = 0 ; i < 3 ; i++)
01432         cardinality(home, xs[i], 1, 1);
01433       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01434     }
01436     static std::vector<IntSetArgs> expectedSolutions(void) {
01437       static std::vector<IntSetArgs> expected;
01438       expected.clear();
01439       expected.push_back(ISA(3, 1,-1, 1,-1, 1,-1));
01440       expected.push_back(ISA(3, 1,-1, 1,-1, 2,-1));
01441       expected.push_back(ISA(3, 1,-1, 2,-1, 1,-1));
01442       expected.push_back(ISA(3, 1,-1, 2,-1, 2,-1));
01443       expected.push_back(ISA(3, 1,-1, 2,-1, 3,-1));
01444       return expected;
01445     }
01446   };
01447 
01449   class SetVarSeqSym1 {
01450   public:
01452     static const int n = 4;
01454     static const int l = 0;
01456     static const int u = 1;
01458     static void setup(Home home, SetVarArray& xs) {
01459       Symmetries syms;
01460       syms << VariableSequenceSymmetry(xs,2);
01461       rel(home, xs[0], SOT_INTER, xs[1], SRT_EQ, IntSet::empty);
01462       rel(home, xs[2], SOT_INTER, xs[3], SRT_EQ, IntSet::empty);
01463       for (int i = 0 ; i < 4 ; i++)
01464         cardinality(home, xs[i], 1, 1);
01465       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01466     }
01468     static std::vector<IntSetArgs> expectedSolutions(void) {
01469       static std::vector<IntSetArgs> expected;
01470       expected.clear();
01471       expected.push_back(ISA(4, 0,-1, 1,-1, 0,-1, 1,-1));
01472       expected.push_back(ISA(4, 0,-1, 1,-1, 1,-1, 0,-1));
01473       //      expected.push_back(ISA(4, 1,-1, 0,-1, 0,-1, 1,-1));
01474       expected.push_back(ISA(4, 1,-1, 0,-1, 1,-1, 0,-1));
01475       return expected;
01476     }
01477   };
01478 
01480   class SetVarSeqSym2 {
01481   public:
01483     static const int n = 4;
01485     static const int l = 0;
01487     static const int u = 0;
01489     static void setup(Home home, SetVarArray& xs) {
01490       Symmetries syms;
01491       syms << VariableSequenceSymmetry(xs,2);
01492       rel(home, xs[0], SRT_EQ, xs[2]);
01493       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01494     }
01496     static std::vector<IntSetArgs> expectedSolutions(void) {
01497       static std::vector<IntSetArgs> expected;
01498       expected.clear();
01499 
01500       // Symmetric solutions are commented out.
01501       expected.push_back(ISA(4, 0, -1,0,-1,0,-1,0,-1));
01502       expected.push_back(ISA(4, 0, -1,0,-1,0,-1,  -1));
01503       // expected.push_back(ISA(4, 0, -1,0,-1,  -1,0,-1));
01504       // expected.push_back(ISA(4, 0, -1,0,-1,  -1,  -1));
01505       // expected.push_back(ISA(4, 0, -1,  -1,0,-1,0,-1));
01506       expected.push_back(ISA(4, 0, -1,  -1,0,-1,  -1));
01507       // expected.push_back(ISA(4, 0, -1,  -1,  -1,0,-1));
01508       // expected.push_back(ISA(4, 0, -1,  -1,  -1,  -1));
01509       // expected.push_back(ISA(4,    -1,0,-1,0,-1,0,-1));
01510       // expected.push_back(ISA(4,    -1,0,-1,0,-1,  -1));
01511       expected.push_back(ISA(4,    -1,0,-1,  -1,0,-1));
01512       expected.push_back(ISA(4,    -1,0,-1,  -1,  -1));
01513       // expected.push_back(ISA(4,    -1,  -1,0,-1,0,-1));
01514       // expected.push_back(ISA(4,    -1,  -1,0,-1,  -1));
01515       // expected.push_back(ISA(4,    -1,  -1,  -1,0,-1));
01516       expected.push_back(ISA(4,    -1,  -1,  -1,  -1));
01517 
01518       return expected;
01519     }
01520   };
01521 
01523   class ReflectSym1 {
01524   public:
01526     static const int n = 6;
01528     static const int l = 0;
01530     static const int u = 6;
01532     static void setup(Home home, IntVarArray& xs) {
01533       Matrix<IntVarArray> m(xs, 3, 2);
01534 
01535       distinct(home, xs);
01536       rel(home, abs(m(0,0)-m(1,0))==1);
01537       rel(home, abs(m(0,1)-m(1,1))==1);
01538       rel(home, abs(m(1,0)-m(2,0))==1);
01539       rel(home, abs(m(1,1)-m(2,1))==1);
01540 
01541       Symmetries s;
01542       s << values_reflect(l, u);
01543       s << rows_interchange(m);
01544       s << columns_reflect(m);
01545       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01546     }
01548     static std::vector<IntArgs> expectedSolutions(void) {
01549       static std::vector<IntArgs> expected;
01550       expected.clear();
01551       expected.push_back(IntArgs({0,1,2,3,4,5}));
01552       expected.push_back(IntArgs({0,1,2,4,5,6}));
01553       expected.push_back(IntArgs({0,1,2,5,4,3}));
01554       expected.push_back(IntArgs({0,1,2,6,5,4}));
01555       return expected;
01556     }
01557   };
01558 
01560   class ReflectSym2 {
01561   public:
01563     static const int n = 2;
01565     static const int l = 0;
01567     static const int u = 3;
01569     static void setup(Home home, IntVarArray& xs) {
01570       Symmetries s;
01571       s << values_reflect(l, u);
01572       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01573     }
01575     static std::vector<IntArgs> expectedSolutions(void) {
01576       static std::vector<IntArgs> expected;
01577       expected.clear();
01578       expected.push_back(IntArgs({0,0}));
01579       expected.push_back(IntArgs({0,1}));
01580       expected.push_back(IntArgs({0,2}));
01581       expected.push_back(IntArgs({0,3}));
01582       expected.push_back(IntArgs({1,0}));
01583       expected.push_back(IntArgs({1,1}));
01584       expected.push_back(IntArgs({1,2}));
01585       expected.push_back(IntArgs({1,3}));
01586       return expected;
01587     }
01588   };
01589 
01591   class Action1 {
01592   public:
01594     static const int n = 4;
01596     static const int l = 0;
01598     static const int u = 3;
01600     static void setup(Home home, IntVarArray& xs) {
01601       distinct(home, xs);
01602       Symmetries s;
01603       s << VariableSymmetry(xs);
01604       s << ValueSymmetry(IntArgs::create(4,0));
01605       branch(home, xs, INT_VAR_ACTION_MIN(0.8), INT_VAL_MIN(), s);
01606     }
01608     static std::vector<IntArgs> expectedSolutions(void) {
01609       static std::vector<IntArgs> expected;
01610       expected.clear();
01611       expected.push_back(IntArgs({0,1,2,3}));
01612       return expected;
01613     }
01614   };
01615 
01616 #endif
01617 
01618   LDSB<VarSym1> varsym1("VarSym1");
01619   LDSB<VarSym1b> varsym1b("VarSym1b");
01620   LDSB<VarSym2> varsym2("VarSym2");
01621   LDSB<VarSym3> varsym3("VarSym3");
01622   LDSB<VarSym4> varsym4("VarSym4");
01623   LDSB<VarSym5> varsym5("VarSym5");
01624   LDSB<MatSym1> matsym1("MatSym1");
01625   LDSB<MatSym2> matsym2("MatSym2");
01626   LDSB<MatSym3> matsym3("MatSym3");
01627   LDSB<MatSym4> matsym4("MatSym4");
01628   LDSB<SimIntVarSym1> simintvarsym1("SimIntVarSym1");
01629   LDSB<SimIntVarSym2> simintvarsym2("SimIntVarSym2");
01630   LDSB<SimIntValSym1> simintvalsym1("SimIntValSym1");
01631   LDSB<SimIntValSym2> simintvalsym2("SimIntValSym2");
01632   LDSB<SimIntValSym3> simintvalsym3("SimIntValSym3");
01633   LDSB<ValSym1> valsym1("ValSym1");
01634   LDSB<ValSym1b> valsym1b("ValSym1b");
01635   LDSB<ValSym1c> valsym1c("ValSym1c");
01636   LDSB<ValSym2> valsym2("ValSym2");
01637   LDSB<ValSym2b> valsym2b("ValSym2b");
01638   LDSB<ValSym3> valsym3("ValSym3");
01639   LDSB<ValSym4> valsym4("ValSym4");
01640   LDSB<ValSym5> valsym5("ValSym5");
01641   LDSB<VarValSym1> varvalsym1("VarValSym1");
01642   LDSBLatin latin("Latin");
01643   LDSB<Recomputation> recomp("Recomputation", 999,999);
01644   LDSB<TieBreak> tiebreak("TieBreak");
01645 
01646 #ifdef GECODE_HAS_SET_VARS
01647   LDSB<ReflectSym1> reflectsym1("ReflectSym1");
01648   LDSB<ReflectSym2> reflectsym2("ReflectSym2");
01649   LDSB<Action1> action1("Action1");
01650 
01651   LDSBSet<SetVarSym1> setvarsym1("SetVarSym1");
01652   LDSBSet<SetValSym1> setvalsym1("SetValSym1");
01653   LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1);
01654   LDSBSet<SetVarSeqSym1> setvarseqsym1("SetVarSeqSym1");
01655   LDSBSet<SetVarSeqSym2> setvarseqsym2("SetVarSeqSym2");
01656 #endif
01657 }}
01658 
01659 // STATISTICS: test-core