Generated on Tue May 22 09:40:01 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 #endif
00042 
00043 #include <gecode/minimodel.hh>
00044 
00045 #include "test/test.hh"
00046 
00047 #include <vector>
00048 
00053 namespace Test { namespace LDSB {
00054 
00055   using namespace Gecode;
00056 
00059   bool
00060   equal(const IntArgs& a, const IntArgs& b) {
00061     if (a.size() != b.size()) return false;
00062     for (int i = 0 ; i < a.size() ; ++i)
00063       if (a[i] != b[i])
00064         return false;
00065     return true;
00066   }
00067 
00068 #ifdef GECODE_HAS_SET_VARS
00069 
00070 
00071   bool
00072   equal(const IntSetArgs& a, const IntSetArgs& b) {
00073     if (a.size() != b.size()) return false;
00074     for (int i = 0 ; i < a.size() ; ++i) {
00075       // Compare the two sets a[i] and b[i].
00076       // Perhaps TODO: use Iter::Ranges::equal instead.
00077       if (a[i].size() != b[i].size()) return false;
00078       IntSetValues x(a[i]);
00079       IntSetValues y(b[i]);
00080       while (x() && y()) {
00081         if (x.val() != y.val()) return false;
00082         ++x;
00083         ++y;
00084       }
00085     }
00086     return true;
00087   }
00088 #endif
00089 
00099   template <class T, class VarArgsType>
00100   bool
00101   check(DFS<T>& e, std::vector<VarArgsType> expected) {
00102     int nexpected = expected.size();
00103     for (int i = 0 ; i < nexpected ; ++i) {
00104       T* s = e.next();
00105       if (s == NULL) {
00106         if (opt.log) {
00107           olog << "Expected a solution but there are no more solutions." << std::endl;
00108           olog << "(Expected " << nexpected << " but only found " << i << ")" << std::endl;
00109           olog << "Expected: " << expected[i] << std::endl;
00110         }
00111         return false;
00112       }
00113       if (!equal(s->solution(), expected[i])) {
00114         if (opt.log) {
00115           olog << "Solution does not match expected." << std::endl;
00116           olog << "Solution: " << s->solution() << std::endl;
00117           olog << "Expected: " << expected[i] << std::endl;
00118         }
00119         return false;
00120       }
00121       delete s;
00122     }
00123     T* s = e.next();
00124     if (s != NULL) {
00125       if (opt.log) {
00126         olog << "More solutions than expected:" << std::endl;
00127         olog << "(Expected only " << nexpected << ")" << std::endl;
00128         olog << s->solution() << std::endl;
00129       }
00130       return false;
00131     }
00132 
00133     // Nothing went wrong.
00134     return true;
00135   }
00136 
00137 
00139   class OneArray : public Space {
00140   public:
00142     IntVarArray xs;
00144     OneArray(int n, int l, int u) : xs(*this,n,l,u) {
00145     }
00147     OneArray(OneArray& s) : Space(s) {
00148       xs.update(*this,s.xs);
00149     }
00151     virtual Space* copy(void) {
00152       return new OneArray(*this);
00153     }
00155     IntArgs solution(void) {
00156       IntArgs a(xs.size());
00157       for (int i = 0 ; i < a.size() ; ++i)
00158         a[i] = xs[i].val();
00159       return a;
00160     }
00162     virtual IntArgs* expectedSolutions(void) { return NULL; }
00163   };
00164 
00165 #ifdef GECODE_HAS_SET_VARS
00166 
00167   class OneArraySet : public Space {
00168   public:
00170     SetVarArray xs;
00172     OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) {
00173     }
00175     OneArraySet(OneArraySet& s) : Space(s) {
00176       xs.update(*this,s.xs);
00177     }
00179     virtual Space* copy(void) {
00180       return new OneArraySet(*this);
00181     }
00183     IntSetArgs solution(void) {
00184       IntSetArgs a(xs.size());
00185       for (int i = 0 ; i < a.size() ; ++i) {
00186         SetVarGlbRanges glbranges(xs[i]);
00187         a[i] = IntSet(glbranges);
00188       }
00189       return a;
00190     }
00192     virtual IntSetArgs* expectedSolutions(void) { return NULL; }
00193   };
00194 #endif
00195 
00197   template <class T>
00198   class LDSB : public Base {
00199   public:
00201     unsigned int c_d;
00203     unsigned int a_d;
00205     LDSB(std::string label, unsigned int c=0, unsigned int a=0)
00206       : Test::Base("LDSB::" + label),
00207         c_d(c), a_d(a) {}
00209     bool run(void) {
00210       OneArray *s = new OneArray(T::n, T::l, T::u);
00211       T::setup(*s, s->xs);
00212       Search::Options o = Search::Options::def;
00213       if (c_d != 0) o.c_d = c_d;
00214       if (a_d != 0) o.a_d = a_d;
00215       DFS<OneArray> e(s,o);
00216       bool r = check(e, T::expectedSolutions());
00217       delete s;
00218       return r;
00219     }
00220   };
00221 
00222 #ifdef GECODE_HAS_SET_VARS
00223 
00224   template <class T>
00225   class LDSBSet : public Base {
00226   public:
00228     unsigned int c_d;
00230     unsigned int a_d;
00232     LDSBSet(std::string label, unsigned int c=0, unsigned int a=0)
00233       : Test::Base("LDSB::" + label),
00234         c_d(c), a_d(a) {}
00236     bool run(void) {
00237       OneArraySet *s = new OneArraySet(T::n, T::l, T::u);
00238       T::setup(*s, s->xs);
00239       Search::Options o = Search::Options::def;
00240       if (c_d != 0) o.c_d = c_d;
00241       if (a_d != 0) o.a_d = a_d;
00242       DFS<OneArraySet> e(s,o);
00243       bool r = check(e, T::expectedSolutions());
00244       delete s;
00245       return r;
00246     }
00247   };
00248 #endif
00249 
00250   // Test cases
00251 
00253   class VarSym1 {
00254   public:
00256     static const int n = 4;
00258     static const int l = 0;
00260     static const int u = 3;
00262     static void setup(Home home, IntVarArray& xs) {
00263       Symmetries syms;
00264       IntArgs indices(4, 0,1,2,3);
00265       syms << VariableSymmetry(xs, indices);
00266       distinct(home, xs);
00267       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00268     }
00270     static std::vector<IntArgs> expectedSolutions(void) {
00271       static std::vector<IntArgs> expected;
00272       expected.clear();
00273       expected.push_back(IntArgs(4, 0,1,2,3));
00274       return expected;
00275     }
00276   };
00277 
00279   class VarSym1b {
00280   public:
00282     static const int n = 4;
00284     static const int l = 0;
00286     static const int u = 3;
00288     static void setup(Home home, IntVarArray& xs) {
00289       distinct(home, xs);
00290       Symmetries syms;
00291       syms << VariableSymmetry(xs);
00292       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00293     }
00295     static std::vector<IntArgs> expectedSolutions(void) {
00296       static std::vector<IntArgs> expected;
00297       expected.clear();
00298       expected.push_back(IntArgs(4, 0,1,2,3));
00299       return expected;
00300     }
00301   };
00302 
00304   class VarSym2 {
00305   public:
00307     static const int n = 4;
00309     static const int l = 0;
00311     static const int u = 3;
00313     static void setup(Home home, IntVarArray& xs) {
00314       Symmetries syms;
00315       IntArgs indices(4, 0,1,2,3);
00316       syms << VariableSymmetry(xs);
00317       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00318     }
00320     static std::vector<IntArgs> expectedSolutions(void) {
00321       static std::vector<IntArgs> expected;
00322       expected.clear();
00323       expected.push_back(IntArgs(4, 0,0,0,0));
00324       expected.push_back(IntArgs(4, 0,0,0,1));
00325       expected.push_back(IntArgs(4, 0,0,0,2));
00326       expected.push_back(IntArgs(4, 0,0,0,3));
00327       expected.push_back(IntArgs(4, 0,0,1,1));
00328       expected.push_back(IntArgs(4, 0,0,1,2));
00329       expected.push_back(IntArgs(4, 0,0,1,3));
00330       expected.push_back(IntArgs(4, 0,0,2,2));
00331       expected.push_back(IntArgs(4, 0,0,2,3));
00332       expected.push_back(IntArgs(4, 0,0,3,3));
00333       expected.push_back(IntArgs(4, 0,1,1,1));
00334       expected.push_back(IntArgs(4, 0,1,1,2));
00335       expected.push_back(IntArgs(4, 0,1,1,3));
00336       expected.push_back(IntArgs(4, 0,1,2,2));
00337       expected.push_back(IntArgs(4, 0,1,2,3));
00338       expected.push_back(IntArgs(4, 0,1,3,3));
00339       expected.push_back(IntArgs(4, 0,2,2,2));
00340       expected.push_back(IntArgs(4, 0,2,2,3));
00341       expected.push_back(IntArgs(4, 0,2,3,3));
00342       expected.push_back(IntArgs(4, 0,3,3,3));
00343       expected.push_back(IntArgs(4, 1,1,1,1));
00344       expected.push_back(IntArgs(4, 1,1,1,2));
00345       expected.push_back(IntArgs(4, 1,1,1,3));
00346       expected.push_back(IntArgs(4, 1,1,2,2));
00347       expected.push_back(IntArgs(4, 1,1,2,3));
00348       expected.push_back(IntArgs(4, 1,1,3,3));
00349       expected.push_back(IntArgs(4, 1,2,2,2));
00350       expected.push_back(IntArgs(4, 1,2,2,3));
00351       expected.push_back(IntArgs(4, 1,2,3,3));
00352       expected.push_back(IntArgs(4, 1,3,3,3));
00353       expected.push_back(IntArgs(4, 2,2,2,2));
00354       expected.push_back(IntArgs(4, 2,2,2,3));
00355       expected.push_back(IntArgs(4, 2,2,3,3));
00356       expected.push_back(IntArgs(4, 2,3,3,3));
00357       expected.push_back(IntArgs(4, 3,3,3,3));
00358       return expected;
00359     }
00360   };
00361 
00363   class VarSym3 {
00364   public:
00366     static const int n = 4;
00368     static const int l = 0;
00370     static const int u = 3;
00372     static void setup(Home home, IntVarArray& xs) {
00373       Symmetries syms;
00374       distinct(home, xs);
00375       syms << VariableSymmetry(IntVarArgs() << xs[0] << xs[1]);
00376       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
00377     }
00379     static std::vector<IntArgs> expectedSolutions(void) {
00380       static std::vector<IntArgs> expected;
00381       expected.clear();
00382       expected.push_back(IntArgs(4, 0,1,2,3));
00383       expected.push_back(IntArgs(4, 0,1,3,2));
00384       expected.push_back(IntArgs(4, 0,2,1,3));
00385       expected.push_back(IntArgs(4, 0,2,3,1));
00386       expected.push_back(IntArgs(4, 0,3,1,2));
00387       expected.push_back(IntArgs(4, 0,3,2,1));
00388       expected.push_back(IntArgs(4, 1,2,0,3));
00389       expected.push_back(IntArgs(4, 1,2,3,0));
00390       expected.push_back(IntArgs(4, 1,3,0,2));
00391       expected.push_back(IntArgs(4, 1,3,2,0));
00392       expected.push_back(IntArgs(4, 2,3,0,1));
00393       expected.push_back(IntArgs(4, 2,3,1,0));
00394       return expected;
00395     }
00396   };
00397 
00399   class VarSym4 {
00400   public:
00402     static const int n = 3;
00404     static const int l = 0;
00406     static const int u = 2;
00408     static void setup(Home home, IntVarArray& xs) {
00409       distinct(home, xs);
00410       Symmetries s;
00411       IntVarArgs symvars;
00412       symvars << xs[0];
00413       s << VariableSymmetry(symvars);
00414       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00415     }
00417     static std::vector<IntArgs> expectedSolutions(void) {
00418       static std::vector<IntArgs> expected;
00419       expected.clear();
00420       expected.push_back(IntArgs(3, 0,1,2));
00421       expected.push_back(IntArgs(3, 0,2,1));
00422       expected.push_back(IntArgs(3, 1,0,2));
00423       expected.push_back(IntArgs(3, 1,2,0));
00424       expected.push_back(IntArgs(3, 2,0,1));
00425       expected.push_back(IntArgs(3, 2,1,0));
00426       return expected;
00427     }
00428   };
00429 
00431   class VarSym5 {
00432   public:
00434     static const int n = 4;
00436     static const int l = 0;
00438     static const int u = 3;
00440     static void setup(Home home, IntVarArray& xs) {
00441       distinct(home, xs);
00442       Matrix<IntVarArray> m(xs, 4, 1);
00443       Symmetries s;
00444       s << VariableSymmetry(m.slice(0,2, 0,1));
00445       s << VariableSymmetry(m.slice(2,4, 0,1));
00446       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00447     }
00449     static std::vector<IntArgs> expectedSolutions(void) {
00450       static std::vector<IntArgs> expected;
00451       expected.clear();
00452       expected.push_back(IntArgs(4, 0,1,2,3));
00453       expected.push_back(IntArgs(4, 0,2,1,3));
00454       expected.push_back(IntArgs(4, 0,3,1,2));
00455       expected.push_back(IntArgs(4, 1,2,0,3));
00456       expected.push_back(IntArgs(4, 1,3,0,2));
00457       expected.push_back(IntArgs(4, 2,3,0,1));
00458       return expected;
00459     }
00460   };
00461 
00463   class MatSym1 {
00464   public:
00466     static const int n = 6;
00468     static const int l = 0;
00470     static const int u = 1;
00472     static void setup(Home home, IntVarArray& xs) {
00473       Matrix<IntVarArray> m(xs, 2, 3);
00474       Symmetries s;
00475       s << rows_interchange(m);
00476       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00477     }
00479     static std::vector<IntArgs> expectedSolutions(void) {
00480       static std::vector<IntArgs> expected;
00481       expected.clear();
00482       expected.push_back(IntArgs(6, 0,0, 0,0, 0,0));
00483       expected.push_back(IntArgs(6, 0,0, 0,0, 0,1));
00484       expected.push_back(IntArgs(6, 0,0, 0,0, 1,0));
00485       expected.push_back(IntArgs(6, 0,0, 0,0, 1,1));
00486       expected.push_back(IntArgs(6, 0,0, 0,1, 0,0));
00487       expected.push_back(IntArgs(6, 0,0, 0,1, 0,1));
00488       expected.push_back(IntArgs(6, 0,0, 0,1, 1,0));
00489       expected.push_back(IntArgs(6, 0,0, 0,1, 1,1));
00490       expected.push_back(IntArgs(6, 0,0, 1,0, 1,0));
00491       expected.push_back(IntArgs(6, 0,0, 1,0, 1,1));
00492       expected.push_back(IntArgs(6, 0,0, 1,1, 1,1));
00493       expected.push_back(IntArgs(6, 0,1, 0,0, 0,0));
00494       expected.push_back(IntArgs(6, 0,1, 0,0, 0,1));
00495       expected.push_back(IntArgs(6, 0,1, 0,0, 1,0));
00496       expected.push_back(IntArgs(6, 0,1, 0,0, 1,1));
00497       expected.push_back(IntArgs(6, 0,1, 0,1, 0,0));
00498       expected.push_back(IntArgs(6, 0,1, 0,1, 0,1));
00499       expected.push_back(IntArgs(6, 0,1, 0,1, 1,0));
00500       expected.push_back(IntArgs(6, 0,1, 0,1, 1,1));
00501       expected.push_back(IntArgs(6, 0,1, 1,0, 1,0));
00502       expected.push_back(IntArgs(6, 0,1, 1,0, 1,1));
00503       expected.push_back(IntArgs(6, 0,1, 1,1, 1,1));
00504       expected.push_back(IntArgs(6, 1,0, 1,0, 1,0));
00505       expected.push_back(IntArgs(6, 1,0, 1,0, 1,1));
00506       expected.push_back(IntArgs(6, 1,0, 1,1, 1,1));
00507       expected.push_back(IntArgs(6, 1,1, 1,1, 1,1));
00508       return expected;
00509     }
00510   };
00511 
00513   class MatSym2 {
00514   public:
00516     static const int n = 6;
00518     static const int l = 0;
00520     static const int u = 1;
00522     static void setup(Home home, IntVarArray& xs) {
00523       Matrix<IntVarArray> m(xs, 2, 3);
00524       Symmetries s;
00525       s << columns_interchange(m);
00526       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00527     }
00529     static std::vector<IntArgs> expectedSolutions(void) {
00530       static std::vector<IntArgs> expected;
00531       expected.clear();
00532       expected.push_back(IntArgs(6, 0,0, 0,0, 0,0));
00533       expected.push_back(IntArgs(6, 0,0, 0,0, 0,1));
00534       expected.push_back(IntArgs(6, 0,0, 0,0, 1,1));
00535       expected.push_back(IntArgs(6, 0,0, 0,1, 0,0));
00536       expected.push_back(IntArgs(6, 0,0, 0,1, 0,1));
00537       expected.push_back(IntArgs(6, 0,0, 0,1, 1,0));
00538       expected.push_back(IntArgs(6, 0,0, 0,1, 1,1));
00539       expected.push_back(IntArgs(6, 0,0, 1,1, 0,0));
00540       expected.push_back(IntArgs(6, 0,0, 1,1, 0,1));
00541       expected.push_back(IntArgs(6, 0,0, 1,1, 1,1));
00542       expected.push_back(IntArgs(6, 0,1, 0,0, 0,0));
00543       expected.push_back(IntArgs(6, 0,1, 0,0, 0,1));
00544       expected.push_back(IntArgs(6, 0,1, 0,0, 1,0));
00545       expected.push_back(IntArgs(6, 0,1, 0,0, 1,1));
00546       expected.push_back(IntArgs(6, 0,1, 0,1, 0,0));
00547       expected.push_back(IntArgs(6, 0,1, 0,1, 0,1));
00548       expected.push_back(IntArgs(6, 0,1, 0,1, 1,0));
00549       expected.push_back(IntArgs(6, 0,1, 0,1, 1,1));
00550       expected.push_back(IntArgs(6, 0,1, 1,0, 0,0));
00551       expected.push_back(IntArgs(6, 0,1, 1,0, 0,1));
00552       expected.push_back(IntArgs(6, 0,1, 1,0, 1,0));
00553       expected.push_back(IntArgs(6, 0,1, 1,0, 1,1));
00554       expected.push_back(IntArgs(6, 0,1, 1,1, 0,0));
00555       expected.push_back(IntArgs(6, 0,1, 1,1, 0,1));
00556       expected.push_back(IntArgs(6, 0,1, 1,1, 1,0));
00557       expected.push_back(IntArgs(6, 0,1, 1,1, 1,1));
00558       expected.push_back(IntArgs(6, 1,1, 0,0, 0,0));
00559       expected.push_back(IntArgs(6, 1,1, 0,0, 0,1));
00560       expected.push_back(IntArgs(6, 1,1, 0,0, 1,1));
00561       expected.push_back(IntArgs(6, 1,1, 0,1, 0,0));
00562       expected.push_back(IntArgs(6, 1,1, 0,1, 0,1));
00563       expected.push_back(IntArgs(6, 1,1, 0,1, 1,0));
00564       expected.push_back(IntArgs(6, 1,1, 0,1, 1,1));
00565       expected.push_back(IntArgs(6, 1,1, 1,1, 0,0));
00566       expected.push_back(IntArgs(6, 1,1, 1,1, 0,1));
00567       expected.push_back(IntArgs(6, 1,1, 1,1, 1,1));
00568       return expected;
00569     }
00570   };
00571 
00573   class MatSym3 {
00574   public:
00576     static const int n = 6;
00578     static const int l = 0;
00580     static const int u = 1;
00582     static void setup(Home home, IntVarArray& xs) {
00583       Matrix<IntVarArray> m(xs, 2, 3);
00584       Symmetries s;
00585       s << rows_interchange(m);
00586       s << columns_interchange(m);
00587       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00588     }
00590     static std::vector<IntArgs> expectedSolutions(void) {
00591       static std::vector<IntArgs> expected;
00592       expected.clear();
00593       expected.push_back(IntArgs(6, 0,0, 0,0, 0,0));
00594       expected.push_back(IntArgs(6, 0,0, 0,0, 0,1));
00595       expected.push_back(IntArgs(6, 0,0, 0,0, 1,1));
00596       expected.push_back(IntArgs(6, 0,0, 0,1, 0,0));
00597       expected.push_back(IntArgs(6, 0,0, 0,1, 0,1));
00598       expected.push_back(IntArgs(6, 0,0, 0,1, 1,0));
00599       expected.push_back(IntArgs(6, 0,0, 0,1, 1,1));
00600       expected.push_back(IntArgs(6, 0,0, 1,1, 1,1));
00601       expected.push_back(IntArgs(6, 0,1, 0,0, 0,0));
00602       expected.push_back(IntArgs(6, 0,1, 0,0, 0,1));
00603       expected.push_back(IntArgs(6, 0,1, 0,0, 1,0));
00604       expected.push_back(IntArgs(6, 0,1, 0,0, 1,1));
00605       expected.push_back(IntArgs(6, 0,1, 0,1, 0,0));
00606       expected.push_back(IntArgs(6, 0,1, 0,1, 0,1));
00607       expected.push_back(IntArgs(6, 0,1, 0,1, 1,0));
00608       expected.push_back(IntArgs(6, 0,1, 0,1, 1,1));
00609       expected.push_back(IntArgs(6, 0,1, 1,0, 1,0));
00610       expected.push_back(IntArgs(6, 0,1, 1,0, 1,1));
00611       expected.push_back(IntArgs(6, 0,1, 1,1, 1,1));
00612       expected.push_back(IntArgs(6, 1,1, 1,1, 1,1));
00613       return expected;
00614     }
00615   };
00616 
00618   class MatSym4 {
00619   public:
00621     static const int n = 4;
00623     static const int l = 0;
00625     static const int u = 1;
00627     static void setup(Home home, IntVarArray& xs) {
00628       Matrix<IntVarArray> m(xs, 1, 4);
00629       Symmetries s;
00630       s << rows_reflect(m);
00631       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00632     }
00634     static std::vector<IntArgs> expectedSolutions(void) {
00635       static std::vector<IntArgs> expected;
00636       expected.clear();
00637       expected.push_back(IntArgs(4, 0, 0, 0, 0));
00638       expected.push_back(IntArgs(4, 0, 0, 0, 1));
00639       expected.push_back(IntArgs(4, 0, 0, 1, 0));
00640       expected.push_back(IntArgs(4, 0, 0, 1, 1));
00641       expected.push_back(IntArgs(4, 0, 1, 0, 0));
00642       expected.push_back(IntArgs(4, 0, 1, 0, 1));
00643       expected.push_back(IntArgs(4, 0, 1, 1, 0));
00644       expected.push_back(IntArgs(4, 0, 1, 1, 1));
00645       expected.push_back(IntArgs(4, 1, 0, 0, 1));
00646       expected.push_back(IntArgs(4, 1, 0, 1, 1));
00647       expected.push_back(IntArgs(4, 1, 1, 1, 1));
00648       return expected;
00649     }
00650   };
00651 
00653   class SimIntVarSym1 {
00654   public:
00656     static const int n = 12;
00658     static const int l = 0;
00660     static const int u = 3;
00662     static void setup(Home home, IntVarArray& xs) {
00663       Matrix<IntVarArray> m(xs, 3, 4);
00664       // The values in the first column are distinct.
00665       distinct(home, m.col(0));
00666       // Each row sums to 3.
00667       for (int i = 0 ; i < 4 ; ++i)
00668         linear(home, m.row(i), IRT_EQ, 3);
00669 
00670       // Rows are interchangeable.
00671       Symmetries s;
00672       s << VariableSequenceSymmetry(xs, 3);
00673       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00674     }
00676     static std::vector<IntArgs> expectedSolutions(void) {
00677       static std::vector<IntArgs> expected;
00678       expected.clear();
00679       expected.push_back(IntArgs(12, 0,0,3, 1,0,2, 2,0,1, 3,0,0));
00680       expected.push_back(IntArgs(12, 0,0,3, 1,0,2, 2,1,0, 3,0,0));
00681       expected.push_back(IntArgs(12, 0,0,3, 1,1,1, 2,0,1, 3,0,0));
00682       expected.push_back(IntArgs(12, 0,0,3, 1,1,1, 2,1,0, 3,0,0));
00683       expected.push_back(IntArgs(12, 0,0,3, 1,2,0, 2,0,1, 3,0,0));
00684       expected.push_back(IntArgs(12, 0,0,3, 1,2,0, 2,1,0, 3,0,0));
00685       expected.push_back(IntArgs(12, 0,1,2, 1,0,2, 2,0,1, 3,0,0));
00686       expected.push_back(IntArgs(12, 0,1,2, 1,0,2, 2,1,0, 3,0,0));
00687       expected.push_back(IntArgs(12, 0,1,2, 1,1,1, 2,0,1, 3,0,0));
00688       expected.push_back(IntArgs(12, 0,1,2, 1,1,1, 2,1,0, 3,0,0));
00689       expected.push_back(IntArgs(12, 0,1,2, 1,2,0, 2,0,1, 3,0,0));
00690       expected.push_back(IntArgs(12, 0,1,2, 1,2,0, 2,1,0, 3,0,0));
00691       expected.push_back(IntArgs(12, 0,2,1, 1,0,2, 2,0,1, 3,0,0));
00692       expected.push_back(IntArgs(12, 0,2,1, 1,0,2, 2,1,0, 3,0,0));
00693       expected.push_back(IntArgs(12, 0,2,1, 1,1,1, 2,0,1, 3,0,0));
00694       expected.push_back(IntArgs(12, 0,2,1, 1,1,1, 2,1,0, 3,0,0));
00695       expected.push_back(IntArgs(12, 0,2,1, 1,2,0, 2,0,1, 3,0,0));
00696       expected.push_back(IntArgs(12, 0,2,1, 1,2,0, 2,1,0, 3,0,0));
00697       expected.push_back(IntArgs(12, 0,3,0, 1,0,2, 2,0,1, 3,0,0));
00698       expected.push_back(IntArgs(12, 0,3,0, 1,0,2, 2,1,0, 3,0,0));
00699       expected.push_back(IntArgs(12, 0,3,0, 1,1,1, 2,0,1, 3,0,0));
00700       expected.push_back(IntArgs(12, 0,3,0, 1,1,1, 2,1,0, 3,0,0));
00701       expected.push_back(IntArgs(12, 0,3,0, 1,2,0, 2,0,1, 3,0,0));
00702       expected.push_back(IntArgs(12, 0,3,0, 1,2,0, 2,1,0, 3,0,0));
00703       return expected;
00704     }
00705   };
00706 
00708   class SimIntVarSym2 {
00710     static const int nrows = 4;
00712     static const int ncols = 3;
00713   public:
00715     static const int n = nrows*ncols;
00717     static const int l = 0;
00719     static const int u = 3;
00721     static void setup(Home home, IntVarArray& xs) {
00722       Matrix<IntVarArray> m(xs, 3, 4);
00723       // The values in the first column are distinct.
00724       distinct(home, m.col(0));
00725       // Each row sums to 3.
00726       for (int i = 0 ; i < nrows ; ++i)
00727         linear(home, m.row(i), IRT_EQ, 3);
00728 
00729       Symmetries s;
00730 
00731       IntArgs a = IntArgs::create(n, 0);
00732       // Rows are interchangeable.
00733       s << VariableSequenceSymmetry(xs, 3);
00734       // Elements (i,1) and (i,2) in row i are interchangeable,
00735       // separately for each row.
00736       for (int i = 0 ; i < nrows ; i++) {
00737         IntVarArgs symvars;
00738         symvars << m(1,i) << m(2,i);
00739         s << VariableSymmetry(symvars);
00740       }
00741       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00742     }
00744     static std::vector<IntArgs> expectedSolutions(void) {
00745       static std::vector<IntArgs> expected;
00746       expected.clear();
00747       expected.push_back(IntArgs(12, 0,0,3, 1,0,2, 2,0,1, 3,0,0));
00748       expected.push_back(IntArgs(12, 0,0,3, 1,1,1, 2,0,1, 3,0,0));
00749       expected.push_back(IntArgs(12, 0,1,2, 1,0,2, 2,0,1, 3,0,0));
00750       expected.push_back(IntArgs(12, 0,1,2, 1,1,1, 2,0,1, 3,0,0));
00751       return expected;
00752     }
00753   };
00754 
00756   class SimIntValSym1 {
00757   public:
00759     static const int n = 2;
00761     static const int l = 0;
00763     static const int u = 6;
00765     static void setup(Home home, IntVarArray& xs) {
00766       rel(home, xs[0] + xs[1] == 6);
00767       // Values 0,1,2 are symmetric with 6,5,4.
00768       IntArgs values(6, 0,1,2, 6,5,4);
00769       Symmetries s;
00770       s << ValueSequenceSymmetry(values, 3);
00771       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00772     }
00774     static std::vector<IntArgs> expectedSolutions(void) {
00775       static std::vector<IntArgs> expected;
00776       expected.clear();
00777       expected.push_back(IntArgs(2, 0,6));
00778       expected.push_back(IntArgs(2, 1,5));
00779       expected.push_back(IntArgs(2, 2,4));
00780       expected.push_back(IntArgs(2, 3,3));
00781       return expected;
00782     }
00783   };
00784 
00786   class SimIntValSym2 {
00787   public:
00789     static const int n = 3;
00791     static const int l = 0;
00793     static const int u = 8;
00795     static void setup(Home home, IntVarArray& xs) {
00796       TupleSet tuples(3);
00797       tuples.add(1,1,1).add(4,4,4).add(7,7,7)
00798             .add(0,1,5).add(0,1,8).add(3,4,2)
00799             .add(3,4,8).add(6,7,2).add(6,7,5)
00800             .finalize();
00801       extensional(home, xs, tuples);
00802 
00803       // Values 0,1,2 are symmetric with 3,4,5, and with 6,7,8.
00804       IntArgs values(9, 0,1,2, 3,4,5, 6,7,8);
00805       Symmetries s;
00806       s << ValueSequenceSymmetry(values, 3);
00807       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00808     }
00810     static std::vector<IntArgs> expectedSolutions(void) {
00811       static std::vector<IntArgs> expected;
00812       expected.clear();
00813       expected.push_back(IntArgs(3, 0,1,5));
00814       expected.push_back(IntArgs(3, 1,1,1));
00815       return expected;
00816     }
00817   };
00818 
00820   class SimIntValSym3 {
00821   public:
00823     static const int n = 2;
00825     static const int l = 0;
00827     static const int u = 6;
00829     static void setup(Home home, IntVarArray& xs) {
00830       rel(home, xs[0] + xs[1] == 6);
00831       Symmetries s;
00832       // Values 0,1,2 are symmetric with 6,5,4.
00833       s << values_reflect(0,6);
00834       branch(home, xs, INT_VAR_NONE(), INT_VAL_MED(), s);
00835     }
00837     static std::vector<IntArgs> expectedSolutions(void) {
00838       static std::vector<IntArgs> expected;
00839       expected.clear();
00840       expected.push_back(IntArgs(2, 3,3));
00841       expected.push_back(IntArgs(2, 2,4));
00842       expected.push_back(IntArgs(2, 1,5));
00843       expected.push_back(IntArgs(2, 0,6));
00844       return expected;
00845     }
00846   };
00847 
00849   class ValSym1 {
00850   public:
00852     static const int n = 4;
00854     static const int l = 0;
00856     static const int u = 3;
00858     static void setup(Home home, IntVarArray& xs) {
00859       distinct(home, xs);
00860       Symmetries s;
00861       IntArgs indices(4, 0,1,2,3);
00862       s << ValueSymmetry(indices);
00863       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00864     }
00866     static std::vector<IntArgs> expectedSolutions(void) {
00867       static std::vector<IntArgs> expected;
00868       expected.clear();
00869       expected.push_back(IntArgs(4, 0,1,2,3));
00870       return expected;
00871     }
00872   };
00873 
00875   class ValSym1b {
00876   public:
00878     static const int n = 4;
00880     static const int l = 0;
00882     static const int u = 3;
00884     static void setup(Home home, IntVarArray& xs) {
00885       distinct(home, xs);
00886       Symmetries s;
00887       s << ValueSymmetry(xs[0]);
00888       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00889     }
00891     static std::vector<IntArgs> expectedSolutions(void) {
00892       static std::vector<IntArgs> expected;
00893       expected.clear();
00894       expected.push_back(IntArgs(4, 0,1,2,3));
00895       return expected;
00896     }
00897   };
00898 
00900   class ValSym1c {
00901   public:
00903     static const int n = 4;
00905     static const int l = 0;
00907     static const int u = 3;
00909     static void setup(Home home, IntVarArray& xs) {
00910       distinct(home, xs);
00911       Symmetries s;
00912       s << ValueSymmetry(xs[0]);
00913       branch(home, xs, INT_VAR_NONE(), INT_VAL_MAX(), s);
00914     }
00916     static std::vector<IntArgs> expectedSolutions(void) {
00917       static std::vector<IntArgs> expected;
00918       expected.clear();
00919       expected.push_back(IntArgs(4, 3,2,1,0));
00920       return expected;
00921     }
00922   };
00923 
00925   class ValSym2 {
00926   public:
00928     static const int n = 4;
00930     static const int l = 0;
00932     static const int u = 3;
00934     static void setup(Home home, IntVarArray& xs) {
00935       Symmetries s;
00936       IntArgs indices(4, 0,1,2,3);
00937       s << ValueSymmetry(indices);
00938       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00939     }
00941     static std::vector<IntArgs> expectedSolutions(void) {
00942       static std::vector<IntArgs> expected;
00943       expected.clear();
00944       expected.push_back(IntArgs(4, 0,0,0,0));
00945       expected.push_back(IntArgs(4, 0,0,0,1));
00946       expected.push_back(IntArgs(4, 0,0,1,0));
00947       expected.push_back(IntArgs(4, 0,0,1,1));
00948       expected.push_back(IntArgs(4, 0,0,1,2));
00949       expected.push_back(IntArgs(4, 0,1,0,0));
00950       expected.push_back(IntArgs(4, 0,1,0,1));
00951       expected.push_back(IntArgs(4, 0,1,0,2));
00952       expected.push_back(IntArgs(4, 0,1,1,0));
00953       expected.push_back(IntArgs(4, 0,1,1,1));
00954       expected.push_back(IntArgs(4, 0,1,1,2));
00955       expected.push_back(IntArgs(4, 0,1,2,0));
00956       expected.push_back(IntArgs(4, 0,1,2,1));
00957       expected.push_back(IntArgs(4, 0,1,2,2));
00958       expected.push_back(IntArgs(4, 0,1,2,3));
00959       return expected;
00960     }
00961   };
00962 
00964   class ValSym2b {
00965   public:
00967     static const int n = 4;
00969     static const int l = 0;
00971     static const int u = 3;
00973     static void setup(Home home, IntVarArray& xs) {
00974       Symmetries s;
00975       s << ValueSymmetry(xs[0]);
00976       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
00977     }
00979     static std::vector<IntArgs> expectedSolutions(void) {
00980       static std::vector<IntArgs> expected;
00981       expected.clear();
00982       expected.push_back(IntArgs(4, 0,0,0,0));
00983       expected.push_back(IntArgs(4, 0,0,0,1));
00984       expected.push_back(IntArgs(4, 0,0,1,0));
00985       expected.push_back(IntArgs(4, 0,0,1,1));
00986       expected.push_back(IntArgs(4, 0,0,1,2));
00987       expected.push_back(IntArgs(4, 0,1,0,0));
00988       expected.push_back(IntArgs(4, 0,1,0,1));
00989       expected.push_back(IntArgs(4, 0,1,0,2));
00990       expected.push_back(IntArgs(4, 0,1,1,0));
00991       expected.push_back(IntArgs(4, 0,1,1,1));
00992       expected.push_back(IntArgs(4, 0,1,1,2));
00993       expected.push_back(IntArgs(4, 0,1,2,0));
00994       expected.push_back(IntArgs(4, 0,1,2,1));
00995       expected.push_back(IntArgs(4, 0,1,2,2));
00996       expected.push_back(IntArgs(4, 0,1,2,3));
00997       return expected;
00998     }
00999   };
01000 
01002   class ValSym3 {
01003   public:
01005     static const int n = 4;
01007     static const int l = 0;
01009     static const int u = 3;
01011     static void setup(Home home, IntVarArray& xs) {
01012       distinct(home, xs);
01013       Symmetries s;
01014       IntArgs indices(2, 0,1);
01015       s << ValueSymmetry(indices);
01016       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01017     }
01019     static std::vector<IntArgs> expectedSolutions(void) {
01020       static std::vector<IntArgs> expected;
01021       expected.clear();
01022       expected.push_back(IntArgs(4, 0,1,2,3));
01023       expected.push_back(IntArgs(4, 0,1,3,2));
01024       expected.push_back(IntArgs(4, 0,2,1,3));
01025       expected.push_back(IntArgs(4, 0,2,3,1));
01026       expected.push_back(IntArgs(4, 0,3,1,2));
01027       expected.push_back(IntArgs(4, 0,3,2,1));
01028       expected.push_back(IntArgs(4, 2,0,1,3));
01029       expected.push_back(IntArgs(4, 2,0,3,1));
01030       expected.push_back(IntArgs(4, 2,3,0,1));
01031       expected.push_back(IntArgs(4, 3,0,1,2));
01032       expected.push_back(IntArgs(4, 3,0,2,1));
01033       expected.push_back(IntArgs(4, 3,2,0,1));
01034       return expected;
01035     }
01036   };
01037 
01039   class ValSym4 {
01040   public:
01042     static const int n = 3;
01044     static const int l = 0;
01046     static const int u = 2;
01048     static void setup(Home home, IntVarArray& xs) {
01049       distinct(home, xs);
01050       Symmetries s;
01051       IntArgs indices(1, 0);
01052       s << ValueSymmetry(indices);
01053       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01054     }
01056     static std::vector<IntArgs> expectedSolutions(void) {
01057       static std::vector<IntArgs> expected;
01058       expected.clear();
01059       expected.push_back(IntArgs(3, 0,1,2));
01060       expected.push_back(IntArgs(3, 0,2,1));
01061       expected.push_back(IntArgs(3, 1,0,2));
01062       expected.push_back(IntArgs(3, 1,2,0));
01063       expected.push_back(IntArgs(3, 2,0,1));
01064       expected.push_back(IntArgs(3, 2,1,0));
01065       return expected;
01066     }
01067   };
01068 
01070   class ValSym5 {
01071   public:
01073     static const int n = 4;
01075     static const int l = 0;
01077     static const int u = 3;
01079     static void setup(Home home, IntVarArray& xs) {
01080       distinct(home, xs);
01081       Symmetries s;
01082       IntArgs indices0(2, 0,1);
01083       IntArgs indices1(2, 2,3);
01084       s << ValueSymmetry(indices0);
01085       s << ValueSymmetry(indices1);
01086       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01087     }
01089     static std::vector<IntArgs> expectedSolutions(void) {
01090       static std::vector<IntArgs> expected;
01091       expected.clear();
01092       expected.push_back(IntArgs(4, 0,1,2,3));
01093       expected.push_back(IntArgs(4, 0,2,1,3));
01094       expected.push_back(IntArgs(4, 0,2,3,1));
01095       expected.push_back(IntArgs(4, 2,0,1,3));
01096       expected.push_back(IntArgs(4, 2,0,3,1));
01097       expected.push_back(IntArgs(4, 2,3,0,1));
01098       return expected;
01099     }
01100   };
01101 
01103   class VarValSym1 {
01104   public:
01106     static const int n = 4;
01108     static const int l = 0;
01110     static const int u = 3;
01112     static void setup(Home home, IntVarArray& xs) {
01113       Symmetries s;
01114       s << VariableSymmetry(xs);
01115       s << ValueSymmetry(IntArgs::create(4,0));
01116       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01117     }
01119     static std::vector<IntArgs> expectedSolutions(void) {
01120       static std::vector<IntArgs> expected;
01121       expected.clear();
01122       expected.push_back(IntArgs(4, 0,0,0,0));
01123       expected.push_back(IntArgs(4, 0,0,0,1));
01124       expected.push_back(IntArgs(4, 0,0,1,1));
01125       expected.push_back(IntArgs(4, 0,0,1,2));
01126       expected.push_back(IntArgs(4, 0,1,1,1));
01127       expected.push_back(IntArgs(4, 0,1,1,2));
01128       expected.push_back(IntArgs(4, 0,1,2,2));  // This solution is symmetric to the previous one.
01129       expected.push_back(IntArgs(4, 0,1,2,3));
01130       return expected;
01131     }
01132   };
01133 
01135   class LDSBLatin : public Base {
01136   public:
01138     class Latin : public Space {
01139     public:
01140       IntVarArray xs;
01141       Latin(int n = 4) : xs(*this, n*n, 1, n)
01142       {
01143         Matrix<IntVarArray> m(xs, n, n);
01144         for (int i = 0 ; i < n ; i++) {
01145           distinct(*this, m.col(i));
01146           distinct(*this, m.row(i));
01147         }
01148         Symmetries s;
01149         s << rows_interchange(m);
01150         s << columns_interchange(m);
01151         s << ValueSymmetry(IntSet(1,n));
01152         branch(*this, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01153       }
01154       // Search support.
01155       Latin(Latin& s) : Space(s)
01156       { xs.update(*this, s.xs); }
01157       virtual Space* copy(void)
01158       { return new Latin(*this); }
01159       IntArgs solution(void) {
01160         IntArgs a(xs.size());
01161         for (int i = 0 ; i < a.size() ; ++i)
01162           a[i] = xs[i].val();
01163         return a;
01164       }
01165 
01167       static std::vector<IntArgs> expectedSolutions(void) {
01168         static std::vector<IntArgs> expected;
01169         expected.clear();
01170         expected.push_back(IntArgs(16, 1,2,3,4, 2,1,4,3, 3,4,1,2, 4,3,2,1));
01171         expected.push_back(IntArgs(16, 1,2,3,4, 2,1,4,3, 3,4,2,1, 4,3,1,2));
01172         expected.push_back(IntArgs(16, 1,2,3,4, 2,3,4,1, 3,4,1,2, 4,1,2,3));
01173         expected.push_back(IntArgs(16, 1,2,3,4, 2,4,1,3, 3,1,4,2, 4,3,2,1));
01174         return expected;
01175       }
01176     };
01178     LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {}
01180     bool run(void) {
01181       Latin *s = new Latin();
01182       DFS<Latin> e(s);
01183       bool r = check(e, Latin::expectedSolutions());
01184       delete s;
01185       return r;
01186     }
01187   };
01188 
01189   /* This test should fail if the recomputation-handling does not work
01190    * properly.
01191    *
01192    * Why recomputation can be a problem
01193    * ==================================
01194    *
01195    * Every branch point in LDSB is binary, with a left and a right
01196    * branch.  Whenever backtracking happens -- when a right branch is
01197    * explored -- LDSB computes a set of symmetric literals to
01198    * exclude.
01199    *
01200    * !!! This calculation may depend on the current domains of the
01201    * !!! variables.
01202    *
01203    * During recomputation, parts of the search tree are replayed.  To
01204    * be specific, the branching constraints are posted, but no
01205    * propagation happens.  This means that at a given branch point,
01206    * the domains during recomputation may be different (weaker) than
01207    * they were the first time during search.
01208    *
01209    * !!! This *cannot* cause solutions to be missed --- LDSB will not
01210    * !!! be incorrect --- but it *does* change what will be pruned.
01211    *
01212    * If recomputation is not handled properly, the difference in
01213    * domains will cause extra solutions to be found.  This is a result
01214    * of symmetries failing to be broken.
01215    *
01216    */
01217 
01219   class Recomputation {
01220   public:
01222     static const int n = 4;
01224     static const int l = 0;
01226     static const int u = 1;
01228     static void setup(Home home, IntVarArray& xs) {
01229       TupleSet t(2);
01230       t.add(0,0).add(1,1).finalize();
01231       IntVarArgs va;
01232       va << xs[0] << xs[2];
01233       extensional(home, va, t);
01234       Symmetries syms;
01235       syms << VariableSequenceSymmetry(xs, 2);
01236       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
01237     }
01239     static std::vector<IntArgs> expectedSolutions(void) {
01240       static std::vector<IntArgs> expected;
01241       expected.clear();
01242       expected.push_back(IntArgs(4, 0,0,0,0));
01243       expected.push_back(IntArgs(4, 0,0,0,1));
01244 
01245       // This is the solution that will be found if recomputation is
01246       // not handled.  After branching on x[0]=0, we try x[1]=0.  When
01247       // x[1]=0 backtracks, the symmetry [x[0],x[1]] <-> [x[2],x[3]]
01248       // is active --- but only after propagation!  (Without
01249       // propagation, we do not have x[2]=0.)  If propagation happens,
01250       // we know that symmetry is active and we can post x[3]!=0.  If
01251       // it doesn't, we don't use the symmetry and we find a solution
01252       // where x[3]=0.
01253 
01254       // expected.push_back(IntArgs(4, 0,1,0,0));
01255 
01256       expected.push_back(IntArgs(4, 0,1,0,1));
01257 
01258       expected.push_back(IntArgs(4, 1,0,1,0));
01259       expected.push_back(IntArgs(4, 1,0,1,1));
01260       expected.push_back(IntArgs(4, 1,1,1,1));
01261       return expected;
01262     }
01263   };
01264 
01265   double position(const Space& home, IntVar x, int i) {
01266     (void) home;
01267     (void) x;
01268     return i;
01269   }
01270 
01272   class TieBreak {
01273   public:
01275     static const int n = 4;
01277     static const int l = 0;
01279     static const int u = 3;
01281     static void setup(Home home, IntVarArray& xs) {
01282       Symmetries syms;
01283       IntArgs indices(4, 0,1,2,3);
01284       syms << VariableSymmetry(xs, indices);
01285       distinct(home, xs);
01286       // This redundant constraint is to trick the variable
01287       // heuristic.
01288       rel(home, xs[1] != xs[2]);
01289       // xs[1] and xs[2] have higher degree than the others, so they
01290       // are considered first.  xs[2] is higher than x[1] by the merit
01291       // function, so it is assigned first.  Now all remaining
01292       // variables have the same degree, so they are searched in
01293       // reverse order (according to the merit function).  So, the
01294       // solution found is {3, 2, 0, 1}.
01295       branch(home, xs, tiebreak(INT_VAR_DEGREE_MAX(), INT_VAR_MERIT_MAX(position)), INT_VAL_MIN(), syms);
01296     }
01298     static std::vector<IntArgs> expectedSolutions(void) {
01299       static std::vector<IntArgs> expected;
01300       expected.clear();
01301       expected.push_back(IntArgs(4, 3,2,0,1));
01302       return expected;
01303     }
01304   };
01305 
01306 #ifdef GECODE_HAS_SET_VARS
01307 
01308   IntSetArgs ISA(int n, ...) {
01309     IntSetArgs sets;
01310     va_list args;
01311     va_start(args, n);
01312     int i = 0;
01313     IntArgs a;
01314     while (i < n) {
01315       int x = va_arg(args,int);
01316       if (x == -1) {
01317         i++;
01318         sets << IntSet(a);
01319         a = IntArgs();
01320       } else {
01321         a << x;
01322       }
01323     }
01324     va_end(args);
01325     return sets;
01326   }
01327 
01329   class SetVarSym1 {
01330   public:
01332     static const int n = 2;
01334     static const int l = 0;
01336     static const int u = 1;
01338     static void setup(Home home, SetVarArray& xs) {
01339       Symmetries syms;
01340       syms << VariableSymmetry(xs);
01341       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01342     }
01344     static std::vector<IntSetArgs> expectedSolutions(void) {
01345       static std::vector<IntSetArgs> expected;
01346       expected.clear();
01347       expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
01348       expected.push_back(ISA(2, 0,1,-1, 0,  -1));
01349       expected.push_back(ISA(2, 0,1,-1,   1,-1));
01350       expected.push_back(ISA(2, 0,1,-1,     -1));
01351       expected.push_back(ISA(2, 0,  -1, 0,1,-1));
01352       expected.push_back(ISA(2, 0,  -1, 0,  -1));
01353       expected.push_back(ISA(2, 0,  -1,   1,-1));
01354       expected.push_back(ISA(2, 0,  -1,     -1));
01355       // expected.push_back(ISA(2,   1,-1, 0,1,-1));
01356       // expected.push_back(ISA(2,   1,-1, 0,  -1));
01357       expected.push_back(ISA(2,   1,-1,   1,-1));
01358       expected.push_back(ISA(2,   1,-1,     -1));
01359       // expected.push_back(ISA(2,     -1, 0,1,-1));
01360       // expected.push_back(ISA(2,     -1, 0,  -1));
01361       // expected.push_back(ISA(2,     -1,   1,-1));
01362       expected.push_back(ISA(2,     -1,     -1));
01363       return expected;
01364     }
01365   };
01366 
01367   /*
01368    * This tests the special handling of value symmetries on set
01369    * values.  Look at the third solution (commented out) below.  The
01370    * first variable has been assigned to {0,1}.  If the value symmetry
01371    * is not handled specially, then we will consider the value
01372    * symmetry broken because the search has touched each value.
01373    * However, because both values have been assigned to the same
01374    * variable, 0 and 1 are still symmetric.  Therefore, the third
01375    * solution is symmetric to the second one and should be excluded.
01376    */
01377 
01379   class SetValSym1 {
01380   public:
01382     static const int n = 2;
01384     static const int l = 0;
01386     static const int u = 1;
01388     static void setup(Home home, SetVarArray& xs) {
01389       Symmetries syms;
01390       syms << ValueSymmetry(IntArgs(2, 0,1));
01391       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01392     }
01394     static std::vector<IntSetArgs> expectedSolutions(void) {
01395       static std::vector<IntSetArgs> expected;
01396       expected.clear();
01397       expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
01398       expected.push_back(ISA(2, 0,1,-1, 0,  -1));
01399       // expected.push_back(ISA(2, 0,1,-1,   1,-1)); // XXXXX bad solution
01400       expected.push_back(ISA(2, 0,1,-1,     -1));
01401       expected.push_back(ISA(2, 0,  -1, 0,1,-1));
01402       expected.push_back(ISA(2, 0,  -1, 0,  -1));
01403       expected.push_back(ISA(2, 0,  -1,   1,-1));
01404       expected.push_back(ISA(2, 0,  -1,     -1));
01405       // expected.push_back(ISA(2,   1,-1, 0,1,-1));
01406       // expected.push_back(ISA(2,   1,-1, 0,  -1));
01407       // expected.push_back(ISA(2,   1,-1,   1,-1));
01408       // expected.push_back(ISA(2,   1,-1,     -1));
01409       expected.push_back(ISA(2,     -1, 0,1,-1));
01410       expected.push_back(ISA(2,     -1, 0,  -1));
01411       // expected.push_back(ISA(2,     -1,   1,-1));
01412       expected.push_back(ISA(2,     -1,     -1));
01413       return expected;
01414     }
01415   };
01416 
01418   class SetValSym2 {
01419   public:
01421     static const int n = 3;
01423     static const int l = 1;
01425     static const int u = 4;
01427     static void setup(Home home, SetVarArray& xs) {
01428       Symmetries syms;
01429       syms << ValueSymmetry(IntArgs(4, 1,2,3,4));
01430       for (int i = 0 ; i < 3 ; i++)
01431         cardinality(home, xs[i], 1, 1);
01432       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01433     }
01435     static std::vector<IntSetArgs> expectedSolutions(void) {
01436       static std::vector<IntSetArgs> expected;
01437       expected.clear();
01438       expected.push_back(ISA(3, 1,-1, 1,-1, 1,-1));
01439       expected.push_back(ISA(3, 1,-1, 1,-1, 2,-1));
01440       expected.push_back(ISA(3, 1,-1, 2,-1, 1,-1));
01441       expected.push_back(ISA(3, 1,-1, 2,-1, 2,-1));
01442       expected.push_back(ISA(3, 1,-1, 2,-1, 3,-1));
01443       return expected;
01444     }
01445   };
01446 
01448   class SetVarSeqSym1 {
01449   public:
01451     static const int n = 4;
01453     static const int l = 0;
01455     static const int u = 1;
01457     static void setup(Home home, SetVarArray& xs) {
01458       Symmetries syms;
01459       syms << VariableSequenceSymmetry(xs,2);
01460       rel(home, xs[0], SOT_INTER, xs[1], SRT_EQ, IntSet::empty);
01461       rel(home, xs[2], SOT_INTER, xs[3], SRT_EQ, IntSet::empty);
01462       for (int i = 0 ; i < 4 ; i++)
01463         cardinality(home, xs[i], 1, 1);
01464       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01465     }
01467     static std::vector<IntSetArgs> expectedSolutions(void) {
01468       static std::vector<IntSetArgs> expected;
01469       expected.clear();
01470       expected.push_back(ISA(4, 0,-1, 1,-1, 0,-1, 1,-1));
01471       expected.push_back(ISA(4, 0,-1, 1,-1, 1,-1, 0,-1));
01472       //      expected.push_back(ISA(4, 1,-1, 0,-1, 0,-1, 1,-1));
01473       expected.push_back(ISA(4, 1,-1, 0,-1, 1,-1, 0,-1));
01474       return expected;
01475     }
01476   };
01477 
01479   class SetVarSeqSym2 {
01480   public:
01482     static const int n = 4;
01484     static const int l = 0;
01486     static const int u = 0;
01488     static void setup(Home home, SetVarArray& xs) {
01489       Symmetries syms;
01490       syms << VariableSequenceSymmetry(xs,2);
01491       rel(home, xs[0], SRT_EQ, xs[2]);
01492       branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
01493     }
01495     static std::vector<IntSetArgs> expectedSolutions(void) {
01496       static std::vector<IntSetArgs> expected;
01497       expected.clear();
01498 
01499       // Symmetric solutions are commented out.
01500       expected.push_back(ISA(4, 0, -1,0,-1,0,-1,0,-1));
01501       expected.push_back(ISA(4, 0, -1,0,-1,0,-1,  -1));
01502       // expected.push_back(ISA(4, 0, -1,0,-1,  -1,0,-1));
01503       // expected.push_back(ISA(4, 0, -1,0,-1,  -1,  -1));
01504       // expected.push_back(ISA(4, 0, -1,  -1,0,-1,0,-1));
01505       expected.push_back(ISA(4, 0, -1,  -1,0,-1,  -1));
01506       // expected.push_back(ISA(4, 0, -1,  -1,  -1,0,-1));
01507       // expected.push_back(ISA(4, 0, -1,  -1,  -1,  -1));
01508       // expected.push_back(ISA(4,    -1,0,-1,0,-1,0,-1));
01509       // expected.push_back(ISA(4,    -1,0,-1,0,-1,  -1));
01510       expected.push_back(ISA(4,    -1,0,-1,  -1,0,-1));
01511       expected.push_back(ISA(4,    -1,0,-1,  -1,  -1));
01512       // expected.push_back(ISA(4,    -1,  -1,0,-1,0,-1));
01513       // expected.push_back(ISA(4,    -1,  -1,0,-1,  -1));
01514       // expected.push_back(ISA(4,    -1,  -1,  -1,0,-1));
01515       expected.push_back(ISA(4,    -1,  -1,  -1,  -1));
01516 
01517       return expected;
01518     }
01519   };
01520 
01522   class ReflectSym1 {
01523   public:
01525     static const int n = 6;
01527     static const int l = 0;
01529     static const int u = 6;
01531     static void setup(Home home, IntVarArray& xs) {
01532       Matrix<IntVarArray> m(xs, 3, 2);
01533 
01534       distinct(home, xs);
01535       rel(home, abs(m(0,0)-m(1,0))==1);
01536       rel(home, abs(m(0,1)-m(1,1))==1);
01537       rel(home, abs(m(1,0)-m(2,0))==1);
01538       rel(home, abs(m(1,1)-m(2,1))==1);
01539 
01540       Symmetries s;
01541       s << values_reflect(l, u);
01542       s << rows_interchange(m);
01543       s << columns_reflect(m);
01544       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01545     }
01547     static std::vector<IntArgs> expectedSolutions(void) {
01548       static std::vector<IntArgs> expected;
01549       expected.clear();
01550       expected.push_back(IntArgs(6, 0,1,2,3,4,5));
01551       expected.push_back(IntArgs(6, 0,1,2,4,5,6));
01552       expected.push_back(IntArgs(6, 0,1,2,5,4,3));
01553       expected.push_back(IntArgs(6, 0,1,2,6,5,4));
01554       return expected;
01555     }
01556   };
01557 
01559   class ReflectSym2 {
01560   public:
01562     static const int n = 2;
01564     static const int l = 0;
01566     static const int u = 3;
01568     static void setup(Home home, IntVarArray& xs) {
01569       Symmetries s;
01570       s << values_reflect(l, u);
01571       branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
01572     }
01574     static std::vector<IntArgs> expectedSolutions(void) {
01575       static std::vector<IntArgs> expected;
01576       expected.clear();
01577       expected.push_back(IntArgs(2, 0,0));
01578       expected.push_back(IntArgs(2, 0,1));
01579       expected.push_back(IntArgs(2, 0,2));
01580       expected.push_back(IntArgs(2, 0,3));
01581       expected.push_back(IntArgs(2, 1,0));
01582       expected.push_back(IntArgs(2, 1,1));
01583       expected.push_back(IntArgs(2, 1,2));
01584       expected.push_back(IntArgs(2, 1,3));
01585       return expected;
01586     }
01587   };
01588 
01590   class Action1 {
01591   public:
01593     static const int n = 4;
01595     static const int l = 0;
01597     static const int u = 3;
01599     static void setup(Home home, IntVarArray& xs) {
01600       distinct(home, xs);
01601       Symmetries s;
01602       s << VariableSymmetry(xs);
01603       s << ValueSymmetry(IntArgs::create(4,0));
01604       branch(home, xs, INT_VAR_ACTION_MIN(0.8), INT_VAL_MIN(), s);
01605     }
01607     static std::vector<IntArgs> expectedSolutions(void) {
01608       static std::vector<IntArgs> expected;
01609       expected.clear();
01610       expected.push_back(IntArgs(4, 0,1,2,3));
01611       return expected;
01612     }
01613   };
01614 
01615 #endif
01616 
01617   LDSB<VarSym1> varsym1("VarSym1");
01618   LDSB<VarSym1b> varsym1b("VarSym1b");
01619   LDSB<VarSym2> varsym2("VarSym2");
01620   LDSB<VarSym3> varsym3("VarSym3");
01621   LDSB<VarSym4> varsym4("VarSym4");
01622   LDSB<VarSym5> varsym5("VarSym5");
01623   LDSB<MatSym1> matsym1("MatSym1");
01624   LDSB<MatSym2> matsym2("MatSym2");
01625   LDSB<MatSym3> matsym3("MatSym3");
01626   LDSB<MatSym4> matsym4("MatSym4");
01627   LDSB<SimIntVarSym1> simintvarsym1("SimIntVarSym1");
01628   LDSB<SimIntVarSym2> simintvarsym2("SimIntVarSym2");
01629   LDSB<SimIntValSym1> simintvalsym1("SimIntValSym1");
01630   LDSB<SimIntValSym2> simintvalsym2("SimIntValSym2");
01631   LDSB<SimIntValSym3> simintvalsym3("SimIntValSym3");
01632   LDSB<ValSym1> valsym1("ValSym1");
01633   LDSB<ValSym1b> valsym1b("ValSym1b");
01634   LDSB<ValSym1c> valsym1c("ValSym1c");
01635   LDSB<ValSym2> valsym2("ValSym2");
01636   LDSB<ValSym2b> valsym2b("ValSym2b");
01637   LDSB<ValSym3> valsym3("ValSym3");
01638   LDSB<ValSym4> valsym4("ValSym4");
01639   LDSB<ValSym5> valsym5("ValSym5");
01640   LDSB<VarValSym1> varvalsym1("VarValSym1");
01641   LDSBLatin latin("Latin");
01642   LDSB<Recomputation> recomp("Recomputation", 999,999);
01643   LDSB<TieBreak> tiebreak("TieBreak");
01644 
01645 #ifdef GECODE_HAS_SET_VARS
01646   LDSB<ReflectSym1> reflectsym1("ReflectSym1");
01647   LDSB<ReflectSym2> reflectsym2("ReflectSym2");
01648   LDSB<Action1> action1("Action1");
01649 
01650   LDSBSet<SetVarSym1> setvarsym1("SetVarSym1");
01651   LDSBSet<SetValSym1> setvalsym1("SetValSym1");
01652   LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1);
01653   LDSBSet<SetVarSeqSym1> setvarseqsym1("SetVarSeqSym1");
01654   LDSBSet<SetVarSeqSym2> setvarseqsym2("SetVarSeqSym2");
01655 #endif
01656 }}
01657 
01658 // STATISTICS: test-core