Generated on Thu Mar 22 10:39:31 2012 for Gecode by doxygen 1.6.3

perfect-square.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  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2003
00009  *     Mikael Lagerkvist, 2005
00010  *
00011  *  Last modified:
00012  *     $Date: 2011-07-13 14:17:55 +0200 (Wed, 13 Jul 2011) $ by $Author: tack $
00013  *     $Revision: 12188 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <gecode/driver.hh>
00041 #include <gecode/int.hh>
00042 #include <gecode/minimodel.hh>
00043 
00044 using namespace Gecode;
00045 
00060 //@
00061 const int s00[] = {
00062   21, 112,
00063   50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2
00064 };
00065 const int s01[] = {
00066   22, 110,
00067   60,50,28,27,26,24,23,22,21,18,17,16,15,14,13,12,8,7,6,4,3,2
00068 };
00069 const int s02[] = {
00070   22, 192,
00071   86,71,62,59,57,49,47,41,37,36,35,31,28,26,19,17,14,12,10,9,8,4
00072 };
00073 const int s03[] = {
00074   23, 110,
00075   44,41,38,37,32,31,29,28,21,19,16,15,14,13,12,10,8,7,5,4,3,2,1
00076 };
00077 const int s04[] = {
00078   23, 332,
00079   129,123,120,112,91,89,83,68,58,56,53,50,49,48,47,38,31,30,26,24,17,15,1
00080 };
00081 const int s05[] = {
00082   24, 120,
00083   47,46,41,40,34,33,32,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
00084 };
00085 const int s06[] = {
00086   24, 479,
00087   175,174,164,160,155,150,140,130,86,77,68,60,52,44,43,35,29,28,26,24,23,17,6,5
00088 };
00089 const int s07[] = {
00090   25, 147,
00091   74,73,41,40,34,33,32,27,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
00092 };
00093 const int s08[] = {
00094   25, 661,
00095   262,248,238,210,203,196,175,161,111,106,102,84,83,77,73,64,41,38,36,31,23,18,17,7,5
00096 };
00097 const int s09[] = {
00098   26, 212,
00099   99,85,65,62,57,56,55,48,39,38,32,28,26,24,23,20,19,17,16,12,7,6,5,4,2,1
00100 };
00101 const int s10[] = {
00102   26, 214,
00103   86,72,67,64,61,56,55,44,43,39,36,35,34,32,30,29,27,26,23,20,19,10,9,8,6,5
00104 };
00105 const int s11[] = {
00106   26, 825,
00107   304,302,288,277,246,235,233,189,157,135,127,117,109,92,90,83,81,76,57,53,49,37,26,25,8,5
00108 };
00109 const int s12[] = {
00110   27, 180,
00111   89,56,51,50,48,43,41,40,39,36,34,31,29,25,23,21,19,16,15,13,12,10,9,7,6,4,1
00112 };
00113 const int s13[] = {
00114   27, 1179,
00115   484,440,387,379,360,352,316,308,198,194,168,149,145,119,114,108,82,80,69,66,63,50,42,35,29,24,18
00116 };
00117 const int s14[] = {
00118   28, 201,
00119   77,70,68,67,64,56,54,39,38,36,34,32,30,24,22,21,18,17,16,13,12,11,10,6,4,3,2,1
00120 };
00121 const int s15[] = {
00122   28, 1544,
00123   649,615,510,473,456,439,419,385,260,216,214,208,203,175,147,135,125,116,104,94,81,55,49,17,12,7,6,4
00124 };
00125 const int s16[] = {
00126   29, 255,
00127   112,107,84,75,68,64,59,51,49,43,37,36,31,29,28,27,26,25,24,22,17,15,13,11,8,7,6,2,1
00128 };
00129 const int s17[] = {
00130   29, 2134,
00131   855,769,761,717,648,604,562,518,338,293,292,286,265,226,224,204,186,179,174,165,161,109,100,91,69,45,43,17,9
00132 };
00133 const int s18[] = {
00134   30, 237,
00135   88,82,79,76,73,56,53,46,45,43,40,39,36,34,33,32,29,27,25,24,23,21,20,16,11,10,9,5,3,1
00136 };
00137 const int s19[] = {
00138   30, 2710,
00139   992,981,948,936,826,782,781,737,465,440,418,289,272,264,260,242,227,210,208,154,140,124,122,108,92,64,29,16,15,4
00140 };
00141 const int s20[] = {
00142   40, 510,
00143   219,173,156,135,134,128,124,118,114,95,81,79,71,65,63,59,58,55,54,51,49,46,34,33,32,31,28,24,21,20,19,18,17,16,14,10,8,4,3,1
00144 };
00145 const int s21[] = {
00146   40, 1121,
00147   409,408,396,345,317,316,242,238,221,198,166,159,157,143,130,123,120,117,109,102,101,93,87,79,76,67,64,55,53,49,46,44,39,33,21,19,14,13,5,3
00148 };
00149 const int s22[] = {
00150   50, 788,
00151   301,300,246,242,187,182,177,168,145,139,135,128,114,110,103,93,87,84,82,81,79,73,69,63,58,57,52,51,49,47,41,40,34,33,26,23,22,21,20,19,18,15,13,11,10,9,8,7,4,2
00152 };
00153 const int s23[] = {
00154   50, 1034,
00155   588,446,305,283,175,163,160,138,132,130,128,124,120,116,110,107,106,103,101,100,94,86,85,82,80,77,74,64,63,62,61,60,57,54,47,46,45,43,40,39,32,30,28,27,26,25,22,7,6,1
00156 };
00157 const int s24[] = {
00158   60, 1097,
00159   645,452,268,264,204,188,184,176,172,165,161,143,132,127,116,114,108,104,100,94,92,90,88,84,75,74,72,71,69,68,67,64,62,61,56,51,46,36,34,30,29,28,26,25,21,20,19,18,17,16,15,14,12,10,9,7,5,4,2,1
00160 };
00161 const int s25[] = {
00162   60, 1192,
00163   638,554,335,303,285,271,219,180,174,159,149,148,136,125,110,98,94,85,77,76,75,74,72,71,69,65,63,62,61,60,59,57,55,51,50,49,48,47,46,45,44,43,40,39,37,35,32,31,25,16,15,14,12,10,9,8,6,4,2,1
00164 };
00165 const int s26[] = {
00166   75, 1412,
00167   793,619,473,320,287,207,188,181,179,170,167,153,151,149,142,140,132,127,121,117,116,106,105,103,97,93,92,91,90,87,84,83,82,76,74,73,72,71,70,69,67,66,65,64,63,61,54,53,49,45,39,38,35,34,33,32,30,29,28,27,26,24,21,20,19,18,15,14,13,11,10,9,6,5,3
00168 };
00169 
00170 
00171 const int* specs[] = {
00172   &s00[0],&s01[0],&s02[0],&s03[0],&s04[0],
00173   &s05[0],&s06[0],&s07[0],&s08[0],&s09[0],
00174   &s10[0],&s11[0],&s12[0],&s13[0],&s14[0],
00175   &s15[0],&s16[0],&s17[0],&s18[0],&s19[0],
00176   &s20[0],&s21[0],&s22[0],&s23[0],&s24[0],
00177   &s25[0],&s26[0]
00178 };
00179 const unsigned int n_specs = sizeof(specs) / sizeof(int*);
00181 
00189 class PerfectSquare : public Script {
00190 protected:
00192   IntVarArray x;
00194   IntVarArray y;
00195 public:
00197   enum {
00198     PROP_REIFIED,    
00199     PROP_CUMULATIVES 
00200   };
00202   PerfectSquare(const SizeOptions& opt)
00203     : x(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1),
00204       y(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1) {
00205 
00206     const int* s = specs[opt.size()];
00207     int n = *s++;
00208     int w = *s++;
00209 
00210     // Restrict position according to square size
00211     for (int i=n; i--; ) {
00212       rel(*this, x[i], IRT_LQ, w-s[i]);
00213       rel(*this, y[i], IRT_LQ, w-s[i]);
00214     }
00215 
00216     IntArgs sa(n,s);
00217 
00218     // Squares do not overlap
00219     nooverlap(*this, x, sa, y, sa);
00220 
00221     /*
00222      * Capacity constraints
00223      *
00224      */
00225     switch (opt.propagation()) {
00226     case PROP_REIFIED:
00227       {
00228         for (int cx=0; cx<w; cx++) {
00229           BoolVarArgs bx(*this,n,0,1);
00230           for (int i=0; i<n; i++)
00231             dom(*this, x[i], cx-s[i]+1, cx, bx[i]);
00232           linear(*this, sa, bx, IRT_EQ, w);
00233         }
00234         for (int cy=0; cy<w; cy++) {
00235           BoolVarArgs by(*this,n,0,1);
00236           for (int i=0; i<n; i++)
00237             dom(*this, y[i], cy-s[i]+1, cy, by[i]);
00238           linear(*this, sa, by, IRT_EQ, w);
00239         }
00240       }
00241       break;
00242     case PROP_CUMULATIVES:
00243       {
00244         IntArgs m(n), dh(n);
00245         for (int i = n; i--; ) {
00246           m[i]=0; dh[i]=s[i];
00247         }
00248         IntArgs limit(1, w);
00249         {
00250           // x-direction
00251           IntVarArgs e(n);
00252           for (int i=n; i--;)
00253             e[i]=expr(*this, x[i]+dh[i]);
00254           cumulatives(*this, m, x, dh, e, dh, limit, true);
00255           cumulatives(*this, m, x, dh, e, dh, limit, false);
00256         }
00257         {
00258           // y-direction
00259           IntVarArgs e(n);
00260           for (int i=n; i--;)
00261             e[i]=expr(*this, y[i]+dh[i]);
00262           cumulatives(*this, m, y, dh, e, dh, limit, true);
00263           cumulatives(*this, m, y, dh, e, dh, limit, false);
00264         }
00265       }
00266       break;
00267     default:
00268       GECODE_NEVER;
00269     }
00270 
00271     branch(*this, x, INT_VAR_MIN_MIN, INT_VAL_MIN);
00272     branch(*this, y, INT_VAR_MIN_MIN, INT_VAL_MIN);
00273   }
00274 
00276   PerfectSquare(bool share, PerfectSquare& s) : Script(share,s) {
00277     x.update(*this, share, s.x);
00278     y.update(*this, share, s.y);
00279   }
00281   virtual Space*
00282   copy(bool share) {
00283     return new PerfectSquare(share,*this);
00284   }
00286   virtual void
00287   print(std::ostream& os) const {
00288     os << "\t";
00289     for (int i=0; i<x.size(); i++)
00290       os << "(" << x[i] << "," << y[i] << ") ";
00291     os << std::endl;
00292   }
00293 };
00294 
00298 int
00299 main(int argc, char* argv[]) {
00300   SizeOptions opt("PerfectSquare");
00301   opt.propagation(PerfectSquare::PROP_REIFIED);
00302   opt.propagation(PerfectSquare::PROP_REIFIED,     "reified");
00303   opt.propagation(PerfectSquare::PROP_CUMULATIVES, "cumulatives");
00304   opt.a_d(5);
00305   opt.c_d(20);
00306   opt.parse(argc,argv);
00307   if (opt.size() >= n_specs) {
00308     std::cerr << "Error: size must be between 0 and " << n_specs - 1
00309               << std::endl;
00310     return 1;
00311   }
00312   Script::run<PerfectSquare,DFS,SizeOptions>(opt);
00313   return 0;
00314 }
00315 
00316 // STATISTICS: example-any
00317