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