00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
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
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
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
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
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
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
00316