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
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 : Script(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 IntArgs sa(n,s);
00218
00219
00220 nooverlap(*this, x, sa, y, sa);
00221
00222
00223
00224
00225
00226 switch (opt.propagation()) {
00227 case PROP_REIFIED:
00228 {
00229 for (int cx=0; cx<w; cx++) {
00230 BoolVarArgs bx(*this,n,0,1);
00231 for (int i=0; i<n; i++)
00232 dom(*this, x[i], cx-s[i]+1, cx, bx[i]);
00233 linear(*this, sa, bx, IRT_EQ, w);
00234 }
00235 for (int cy=0; cy<w; cy++) {
00236 BoolVarArgs by(*this,n,0,1);
00237 for (int i=0; i<n; i++)
00238 dom(*this, y[i], cy-s[i]+1, cy, by[i]);
00239 linear(*this, sa, by, IRT_EQ, w);
00240 }
00241 }
00242 break;
00243 case PROP_CUMULATIVES:
00244 {
00245 IntArgs m(n), dh(n);
00246 for (int i = n; i--; ) {
00247 m[i]=0; dh[i]=s[i];
00248 }
00249 IntArgs limit(1, w);
00250 {
00251
00252 IntVarArgs e(n);
00253 for (int i=n; i--;)
00254 e[i]=expr(*this, x[i]+dh[i]);
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(n);
00261 for (int i=n; i--;)
00262 e[i]=expr(*this, y[i]+dh[i]);
00263 cumulatives(*this, m, y, dh, e, dh, limit, true);
00264 cumulatives(*this, m, y, dh, e, dh, limit, false);
00265 }
00266 }
00267 break;
00268 default:
00269 GECODE_NEVER;
00270 }
00271
00272 branch(*this, x, INT_VAR_MIN_MIN(), INT_VAL_MIN());
00273 branch(*this, y, INT_VAR_MIN_MIN(), INT_VAL_MIN());
00274 }
00275
00277 PerfectSquare(bool share, PerfectSquare& s) : Script(share,s) {
00278 x.update(*this, share, s.x);
00279 y.update(*this, share, s.y);
00280 }
00282 virtual Space*
00283 copy(bool share) {
00284 return new PerfectSquare(share,*this);
00285 }
00287 virtual void
00288 print(std::ostream& os) const {
00289 os << "\t";
00290 for (int i=0; i<x.size(); i++)
00291 os << "(" << x[i] << "," << y[i] << ") ";
00292 os << std::endl;
00293 }
00294 };
00295
00299 int
00300 main(int argc, char* argv[]) {
00301 SizeOptions opt("PerfectSquare");
00302 opt.propagation(PerfectSquare::PROP_REIFIED);
00303 opt.propagation(PerfectSquare::PROP_REIFIED, "reified");
00304 opt.propagation(PerfectSquare::PROP_CUMULATIVES, "cumulatives");
00305 opt.a_d(5);
00306 opt.c_d(20);
00307 opt.parse(argc,argv);
00308 if (opt.size() >= n_specs) {
00309 std::cerr << "Error: size must be between 0 and " << n_specs - 1
00310 << std::endl;
00311 return 1;
00312 }
00313 Script::run<PerfectSquare,DFS,SizeOptions>(opt);
00314 return 0;
00315 }
00316
00317
00318