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: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00013 * $Revision: 11473 $ 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 #include <gecode/scheduling.hh> 00044 00045 using namespace Gecode; 00046 00061 //@ 00062 const int s00[] = { 00063 21, 112, 00064 50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2 00065 }; 00066 const int s01[] = { 00067 22, 110, 00068 60,50,28,27,26,24,23,22,21,18,17,16,15,14,13,12,8,7,6,4,3,2 00069 }; 00070 const int s02[] = { 00071 22, 192, 00072 86,71,62,59,57,49,47,41,37,36,35,31,28,26,19,17,14,12,10,9,8,4 00073 }; 00074 const int s03[] = { 00075 23, 110, 00076 44,41,38,37,32,31,29,28,21,19,16,15,14,13,12,10,8,7,5,4,3,2,1 00077 }; 00078 const int s04[] = { 00079 23, 332, 00080 129,123,120,112,91,89,83,68,58,56,53,50,49,48,47,38,31,30,26,24,17,15,1 00081 }; 00082 const int s05[] = { 00083 24, 120, 00084 47,46,41,40,34,33,32,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3 00085 }; 00086 const int s06[] = { 00087 24, 479, 00088 175,174,164,160,155,150,140,130,86,77,68,60,52,44,43,35,29,28,26,24,23,17,6,5 00089 }; 00090 const int s07[] = { 00091 25, 147, 00092 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 00093 }; 00094 const int s08[] = { 00095 25, 661, 00096 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 00097 }; 00098 const int s09[] = { 00099 26, 212, 00100 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 00101 }; 00102 const int s10[] = { 00103 26, 214, 00104 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 00105 }; 00106 const int s11[] = { 00107 26, 825, 00108 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 00109 }; 00110 const int s12[] = { 00111 27, 180, 00112 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 00113 }; 00114 const int s13[] = { 00115 27, 1179, 00116 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 00117 }; 00118 const int s14[] = { 00119 28, 201, 00120 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 00121 }; 00122 const int s15[] = { 00123 28, 1544, 00124 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 00125 }; 00126 const int s16[] = { 00127 29, 255, 00128 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 00129 }; 00130 const int s17[] = { 00131 29, 2134, 00132 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 00133 }; 00134 const int s18[] = { 00135 30, 237, 00136 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 00137 }; 00138 const int s19[] = { 00139 30, 2710, 00140 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 00141 }; 00142 const int s20[] = { 00143 40, 510, 00144 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 00145 }; 00146 const int s21[] = { 00147 40, 1121, 00148 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 00149 }; 00150 const int s22[] = { 00151 50, 788, 00152 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 00153 }; 00154 const int s23[] = { 00155 50, 1034, 00156 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 00157 }; 00158 const int s24[] = { 00159 60, 1097, 00160 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 00161 }; 00162 const int s25[] = { 00163 60, 1192, 00164 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 00165 }; 00166 const int s26[] = { 00167 75, 1412, 00168 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 00169 }; 00170 00171 00172 const int* specs[] = { 00173 &s00[0],&s01[0],&s02[0],&s03[0],&s04[0], 00174 &s05[0],&s06[0],&s07[0],&s08[0],&s09[0], 00175 &s10[0],&s11[0],&s12[0],&s13[0],&s14[0], 00176 &s15[0],&s16[0],&s17[0],&s18[0],&s19[0], 00177 &s20[0],&s21[0],&s22[0],&s23[0],&s24[0], 00178 &s25[0],&s26[0] 00179 }; 00180 const unsigned int n_specs = sizeof(specs) / sizeof(int*); 00182 00190 class PerfectSquare : public Script { 00191 protected: 00193 IntVarArray x; 00195 IntVarArray y; 00196 public: 00198 enum { 00199 PROP_REIFIED, 00200 PROP_CUMULATIVES 00201 }; 00203 PerfectSquare(const SizeOptions& opt) 00204 : x(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1), 00205 y(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1) { 00206 00207 const int* s = specs[opt.size()]; 00208 int n = *s++; 00209 int w = *s++; 00210 00211 // Restrict position according to square size 00212 for (int i=n; i--; ) { 00213 rel(*this, x[i], IRT_LQ, w-s[i]); 00214 rel(*this, y[i], IRT_LQ, w-s[i]); 00215 } 00216 00217 // Squares do not overlap 00218 for (int i=0; i<n; i++) 00219 for (int j=i+1; j<n; j++) 00220 rel(*this, (x[i]+s[i] <= x[j]) || (x[j]+s[j] <= x[i]) || 00221 (y[i]+s[i] <= y[j]) || (y[j]+s[j] <= y[i])); 00222 00223 /* 00224 * Capacity constraints 00225 * 00226 */ 00227 switch (opt.propagation()) { 00228 case PROP_REIFIED: 00229 { 00230 IntArgs sa(n,s); 00231 for (int cx=0; cx<w; cx++) { 00232 BoolVarArgs bx(*this,n,0,1); 00233 for (int i=0; i<n; i++) 00234 dom(*this, x[i], cx-s[i]+1, cx, bx[i]); 00235 linear(*this, sa, bx, IRT_EQ, w); 00236 } 00237 for (int cy=0; cy<w; cy++) { 00238 BoolVarArgs by(*this,n,0,1); 00239 for (int i=0; i<n; i++) 00240 dom(*this, y[i], cy-s[i]+1, cy, by[i]); 00241 linear(*this, sa, by, IRT_EQ, w); 00242 } 00243 } 00244 break; 00245 case PROP_CUMULATIVES: 00246 { 00247 IntArgs m(n), dh(n); 00248 for (int i = n; i--; ) { 00249 m[i]=0; dh[i]=s[i]; 00250 } 00251 IntArgs limit(1, w); 00252 { 00253 // x-direction 00254 IntVarArgs e(*this, n, 0, w); 00255 cumulatives(*this, m, x, dh, e, dh, limit, true); 00256 cumulatives(*this, m, x, dh, e, dh, limit, false); 00257 } 00258 { 00259 // y-direction 00260 IntVarArgs e(*this, n, 0, w); 00261 cumulatives(*this, m, y, dh, e, dh, limit, true); 00262 cumulatives(*this, m, y, dh, e, dh, limit, false); 00263 } 00264 } 00265 break; 00266 default: 00267 GECODE_NEVER; 00268 } 00269 00270 branch(*this, x, INT_VAR_MIN_MIN, INT_VAL_MIN); 00271 branch(*this, y, INT_VAR_MIN_MIN, INT_VAL_MIN); 00272 } 00273 00275 PerfectSquare(bool share, PerfectSquare& s) : Script(share,s) { 00276 x.update(*this, share, s.x); 00277 y.update(*this, share, s.y); 00278 } 00280 virtual Space* 00281 copy(bool share) { 00282 return new PerfectSquare(share,*this); 00283 } 00285 virtual void 00286 print(std::ostream& os) const { 00287 os << "\t"; 00288 for (int i=0; i<x.size(); i++) 00289 os << "(" << x[i] << "," << y[i] << ") "; 00290 os << std::endl; 00291 } 00292 }; 00293 00297 int 00298 main(int argc, char* argv[]) { 00299 SizeOptions opt("PerfectSquare"); 00300 opt.propagation(PerfectSquare::PROP_REIFIED); 00301 opt.propagation(PerfectSquare::PROP_REIFIED, "reified"); 00302 opt.propagation(PerfectSquare::PROP_CUMULATIVES, "cumulatives"); 00303 opt.a_d(5); 00304 opt.c_d(20); 00305 opt.parse(argc,argv); 00306 if (opt.size() >= n_specs) { 00307 std::cerr << "Error: size must be between 0 and " << n_specs - 1 00308 << std::endl; 00309 return 1; 00310 } 00311 Script::run<PerfectSquare,DFS,SizeOptions>(opt); 00312 return 0; 00313 } 00314 00315 // STATISTICS: example-any 00316