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 post(*this, tt(~(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 BoolVarArgs b(n);
00232 for (int cx=0; cx<w; cx++) {
00233 for (int i=0; i<n; i++) {
00234 b[i].init(*this,0,1);
00235 dom(*this, x[i], cx-s[i]+1, cx, b[i]);
00236 }
00237 linear(*this, sa, b, IRT_EQ, w);
00238 }
00239 for (int cy=0; cy<w; cy++) {
00240 for (int i=0; i<n; i++) {
00241 b[i].init(*this,0,1);
00242 dom(*this, y[i], cy-s[i]+1, cy, b[i]);
00243 }
00244 linear(*this, sa, b, IRT_EQ, w);
00245 }
00246 }
00247 break;
00248 case PROP_CUMULATIVES:
00249 {
00250 IntArgs m(n), dh(n);
00251 for (int i = n; i--; ) {
00252 m[i]=0; dh[i]=s[i];
00253 }
00254 IntVarArgs e(n);
00255 IntArgs limit(1);
00256 {
00257
00258 for (int i = n; i--; )
00259 e[i].init(*this, 0, w);
00260 limit[0] = w;
00261 cumulatives(*this, m, x, dh, e, dh, limit, true);
00262 cumulatives(*this, m, x, dh, e, dh, limit, false);
00263 }
00264 {
00265
00266 for (int i = n; i--; )
00267 e[i].init(*this, 0, w);
00268 limit[0] = w;
00269 cumulatives(*this, m, y, dh, e, dh, limit, true);
00270 cumulatives(*this, m, y, dh, e, dh, limit, false);
00271 }
00272 }
00273 break;
00274 default:
00275 GECODE_NEVER;
00276 }
00277
00278 branch(*this, x, INT_VAR_MIN_MIN, INT_VAL_MIN);
00279 branch(*this, y, INT_VAR_MIN_MIN, INT_VAL_MIN);
00280 }
00281
00283 PerfectSquare(bool share, PerfectSquare& s) : Script(share,s) {
00284 x.update(*this, share, s.x);
00285 y.update(*this, share, s.y);
00286 }
00288 virtual Space*
00289 copy(bool share) {
00290 return new PerfectSquare(share,*this);
00291 }
00293 virtual void
00294 print(std::ostream& os) const {
00295 os << "\t";
00296 for (int i=0; i<x.size(); i++)
00297 os << "(" << x[i] << "," << y[i] << ") ";
00298 os << std::endl;
00299 }
00300 };
00301
00305 int
00306 main(int argc, char* argv[]) {
00307 SizeOptions opt("PerfectSquare");
00308 opt.propagation(PerfectSquare::PROP_REIFIED);
00309 opt.propagation(PerfectSquare::PROP_REIFIED, "reified");
00310 opt.propagation(PerfectSquare::PROP_CUMULATIVES, "cumulatives");
00311 opt.a_d(5);
00312 opt.c_d(20);
00313 opt.parse(argc,argv);
00314 if (opt.size() >= n_specs) {
00315 std::cerr << "Error: size must be between 0 and " << n_specs - 1
00316 << std::endl;
00317 return 1;
00318 }
00319 Script::run<PerfectSquare,DFS,SizeOptions>(opt);
00320 return 0;
00321 }
00322
00323
00324