Generated on Fri Oct 19 11:24:49 2018 for Gecode by doxygen 1.6.3

ortho-latin.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
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/driver.hh>
00035 #include <gecode/int.hh>
00036 
00037 using namespace Gecode;
00038 
00044 class OrthoLatinSquare : public Script {
00045 protected:
00047   const int n;
00049   IntVarArray x1;
00051   IntVarArray x2;
00052 
00053 public:
00055   IntVar& y1(int i, int j) {
00056     return x1[i*n+j];
00057   }
00059   const IntVar& y1(int i, int j) const {
00060     return x1[i*n+j];
00061   }
00063   IntVar& y2(int i, int j) {
00064     return x2[i*n+j];
00065   }
00067   const IntVar& y2(int i, int j) const {
00068     return x2[i*n+j];
00069   }
00070 
00072   OrthoLatinSquare(const SizeOptions& opt)
00073     : Script(opt),
00074       n(opt.size()),
00075       x1(*this,n*n,1,n), x2(*this,n*n,1,n) {
00076     const int nn = n*n;
00077     IntVarArgs z(*this,nn,0,n*n-1);
00078 
00079     distinct(*this, z, opt.ipl());
00080     // Connect
00081     {
00082       IntArgs mod(n*n);
00083       IntArgs div(n*n);
00084       for (int i=0; i<n; i++)
00085         for (int j=0; j<n; j++) {
00086           mod[i*n+j] = j+1;
00087           div[i*n+j] = i+1;
00088         }
00089       for (int i = nn; i--; ) {
00090         element(*this, div, z[i], x2[i]);
00091         element(*this, mod, z[i], x1[i]);
00092       }
00093     }
00094 
00095     // Rows
00096     for (int i = n; i--; ) {
00097       IntVarArgs ry(n);
00098       for (int j = n; j--; )
00099         ry[j] = y1(i,j);
00100       distinct(*this, ry, opt.ipl());
00101       for (int j = n; j--; )
00102         ry[j] = y2(i,j);
00103       distinct(*this, ry, opt.ipl());
00104     }
00105     for (int j = n; j--; ) {
00106       IntVarArgs cy(n);
00107       for (int i = n; i--; )
00108         cy[i] = y1(i,j);
00109       distinct(*this, cy, opt.ipl());
00110       for (int i = n; i--; )
00111         cy[i] = y2(i,j);
00112       distinct(*this, cy, opt.ipl());
00113     }
00114 
00115     for (int i = 1; i<n; i++) {
00116       IntVarArgs ry1(n);
00117       IntVarArgs ry2(n);
00118       for (int j = n; j--; ) {
00119         ry1[j] = y1(i-1,j);
00120         ry2[j] = y2(i,j);
00121       }
00122       rel(*this, ry1, IRT_GQ, ry2);
00123     }
00124 
00125     branch(*this, z, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
00126   }
00127 
00129   OrthoLatinSquare(OrthoLatinSquare& s)
00130     : Script(s), n(s.n) {
00131       x1.update(*this, s.x1);
00132       x2.update(*this, s.x2);
00133   }
00134 
00136   virtual Space*
00137   copy(void) {
00138     return new OrthoLatinSquare(*this);
00139   }
00141   virtual void
00142   print(std::ostream& os) const {
00143     for (int i = 0; i<n; i++) {
00144       os << "\t";
00145       for (int j = 0; j<n; j++) {
00146         os.width(2);
00147         os << y1(i,j) << "  ";
00148       }
00149       os << std::endl;
00150     }
00151     os << std::endl;
00152     for (int i = 0; i<n; i++) {
00153       os << "\t";
00154       for (int j = 0; j<n; j++) {
00155         os.width(2);
00156         os << y2(i,j) << "  ";
00157       }
00158       os << std::endl;
00159     }
00160     os << std::endl;
00161   }
00162 
00163 };
00164 
00169 int
00170 main(int argc, char* argv[]) {
00171   SizeOptions opt("OrthoLatinSquare");
00172   opt.size(7);
00173   opt.ipl(IPL_DOM);
00174   opt.parse(argc,argv);
00175   Script::run<OrthoLatinSquare,DFS,SizeOptions>(opt);
00176   return 0;
00177 }
00178 
00179 // STATISTICS: example-any
00180