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