00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "examples/support.hh"
00023 #include "minimodel.hh"
00024
00025 extern const int *specs[];
00026 extern const unsigned int n_examples;
00027
00040 class PicturePuzzle : public Example {
00041 private:
00042 const int *spec;
00043 int width, height;
00044 BoolVarArray b;
00045
00047 BoolVar pos(int h, int w) {
00048 return b[h*width + w];
00049 }
00050
00052 REG get_constraint(int& spos) {
00053
00054 const bool print_spec = false;
00055 REG r = *REG(0);
00056 int size = spec[spos++];
00057 if (print_spec) std::cout << size << "(" << spos << "): ";
00058 for (int i = 0; i < size; ++i, ++spos) {
00059 if (i) r = r + +REG(0);
00060 if (print_spec) std::cout << spec[spos] << " ";
00061 r = r + REG(1)(spec[spos],spec[spos]);
00062 }
00063 if (print_spec) std::cout << std::endl;
00064 r = r + *REG(0);
00065
00066 return r;
00067 }
00068
00069
00070 public:
00072 PicturePuzzle(const Options& o)
00073 : spec(specs[o.size]), width(spec[0]), height(spec[1]),
00074 b(this,width*height,0,1) {
00075 int spos = 2;
00076 MiniModel::Matrix<BoolVarArray> m(b, width, height);
00077
00078
00079 for (int w = 0; w < width; ++w) {
00080
00081 REG r = get_constraint(spos);
00082 DFA d = r;
00083 regular(this, m.col(w), d);
00084 }
00085
00086
00087 for (int h = 0; h < height; ++h) {
00088
00089 REG r = get_constraint(spos);
00090 DFA d = r;
00091 regular(this, m.row(h), d);
00092 }
00093
00094
00095 branch(this, b, BVAR_NONE, BVAL_MAX);
00096 }
00097
00099 PicturePuzzle(bool share, PicturePuzzle& s) :
00100 Example(share,s), spec(s.spec), width(s.width), height(s.height) {
00101 b.update(this, share, s.b);
00102 }
00103
00105 virtual Space*
00106 copy(bool share) {
00107 return new PicturePuzzle(share,*this);
00108 }
00109
00111 virtual void
00112 print(void) {
00113 for (int h = 0; h < height; ++h) {
00114 std::cout << '\t';
00115 for (int w = 0; w < width; ++w) {
00116 if (pos(h,w).val() == 1) {
00117 std::cout << "#";
00118 } else {
00119 std::cout << " ";
00120 }
00121 }
00122 std::cout << std::endl;
00123 }
00124 std::cout << std::endl;
00125 }
00126 };
00127
00128
00132 int
00133 main(int argc, char** argv) {
00134 Options o("PicturePuzzle");
00135 o.size = 8;
00136 o.parse(argc,argv);
00137 if (o.size >= n_examples) {
00138 std::cerr << "Error: size must be between 0 and "
00139 << n_examples-1 << std::endl;
00140 return 1;
00141 }
00142 Example::run<PicturePuzzle,DFS>(o);
00143 return 0;
00144 }
00145
00146
00158
00159 static const int heart[] =
00160 { 9, 9,
00161
00162 1, 3,
00163 2, 2, 3,
00164 2, 2, 2,
00165 2, 2, 2,
00166 2, 2, 2,
00167 2, 2, 2,
00168 2, 2, 2,
00169 2, 2, 3,
00170 1, 3,
00171
00172 2, 2, 2,
00173 2, 4, 4,
00174 3, 1, 3, 1,
00175 3, 2, 1, 2,
00176 2, 1, 1,
00177 2, 2, 2,
00178 2, 2, 2,
00179 1, 3,
00180 1, 1
00181 };
00182
00184 static const int bear[] =
00185 { 13, 8,
00186
00187 1, 2,
00188 2, 2, 1,
00189 2, 3, 2,
00190 1, 6,
00191 2, 1, 4,
00192 1, 3,
00193 1, 4,
00194 1, 4,
00195 1, 4,
00196 1, 5,
00197 1, 4,
00198 2, 1, 3,
00199 1, 2,
00200
00201 1, 1,
00202 1, 2,
00203 2, 4, 4,
00204 1, 12,
00205 1, 8,
00206 1, 9,
00207 2, 3, 4,
00208 2, 2, 2
00209 };
00210
00212 static const int crocodile[] =
00213 { 15, 9,
00214
00215 1, 3,
00216 1, 4,
00217 2, 2, 2,
00218 2, 3, 1,
00219 2, 2, 3,
00220 2, 3, 2,
00221 2, 2, 3,
00222 2, 4, 2,
00223 2, 3, 2,
00224 1, 6,
00225 2, 1, 3,
00226 2, 1, 3,
00227 2, 1, 4,
00228 1, 5,
00229 1, 5,
00230
00231 1, 3,
00232 3, 2, 3, 2,
00233 2, 10, 3,
00234 1, 15,
00235 5, 1, 1, 1, 1, 6,
00236 2, 1, 7,
00237 2, 1, 4,
00238 2, 1, 4,
00239 1, 4
00240 };
00241
00243 static const int unknown[] =
00244 { 10, 10,
00245
00246 1, 3,
00247 2, 2, 1,
00248 2, 2, 2,
00249 2, 2, 1,
00250 3, 1, 2, 1,
00251 2, 1, 1,
00252 3, 1, 4, 1,
00253 3, 1, 1, 2,
00254 2, 3, 1,
00255 1, 4,
00256
00257 1, 3,
00258 2, 2, 1,
00259 2, 1, 1,
00260 2, 1, 4,
00261 4, 1, 1, 1, 1,
00262 4, 2, 1, 1, 1,
00263 3, 2, 1, 1,
00264 2, 1, 2,
00265 2, 2, 3,
00266 1, 3
00267 };
00268
00270 static const int pinwheel[] =
00271 { 6, 6,
00272
00273 2, 1, 2,
00274 1, 1,
00275 1, 2,
00276 1, 2,
00277 1, 1,
00278 2, 2, 1,
00279
00280 2, 2, 1,
00281 1, 1,
00282 1, 2,
00283 1, 2,
00284 1, 1,
00285 2, 1, 2
00286 };
00287
00289 static const int difficult[] =
00290 { 15, 15,
00291
00292 1, 3,
00293 1, 2,
00294 1, 2,
00295 1, 1,
00296 1, 2,
00297 1, 3,
00298 1, 2,
00299 1, 4,
00300 1, 3,
00301 1, 4,
00302 2, 2, 1,
00303 2, 1, 1,
00304 2, 1, 1,
00305 2, 1, 1,
00306 1, 3,
00307
00308 1, 3,
00309 2, 1, 1,
00310 2, 1, 1,
00311 2, 1, 1,
00312 2, 1, 2,
00313 1, 5,
00314 1, 1,
00315 1, 2,
00316 1, 1,
00317 1, 1,
00318 2, 1, 2,
00319 2, 1, 2,
00320 2, 2, 1,
00321 2, 2, 2,
00322 1, 3
00323 };
00324
00326 static const int non_unique[] =
00327 { 11, 15,
00328
00329 1, 5,
00330 3, 1, 2, 4,
00331 3, 2, 1, 3,
00332 4, 2, 2, 1, 1,
00333 4, 1, 1, 1, 1,
00334 2, 1, 5,
00335 5, 2, 1, 1, 3, 2,
00336 5, 2, 1, 1, 1, 1,
00337 3, 1, 4, 1,
00338 2, 1, 1,
00339 1, 1,
00340
00341 2, 2, 2,
00342 2, 2, 2,
00343 1, 4,
00344 2, 1, 1,
00345 2, 1, 1,
00346 4, 1, 1, 1, 1,
00347 2, 1, 1,
00348 2, 1, 4,
00349 3, 1, 1, 1,
00350 3, 1, 1, 4,
00351 2, 1, 3,
00352 2, 1, 2,
00353 1, 5,
00354 2, 2, 2,
00355 2, 3, 3
00356 };
00357
00363 static const int dragonfly[] =
00364 { 20, 20,
00365
00366 4, 1, 1, 1, 2,
00367 5, 3, 1, 2, 1, 1,
00368 5, 1, 4, 2, 1, 1,
00369 4, 1, 3, 2, 4,
00370 4, 1, 4, 6, 1,
00371 3, 1, 11, 1,
00372 4, 5, 1, 6, 2,
00373 1, 14,
00374 2, 7, 2,
00375 2, 7, 2,
00376 3, 6, 1, 1,
00377 2, 9, 2,
00378 4, 3, 1, 1, 1,
00379 3, 3, 1, 3,
00380 3, 2, 1, 3,
00381 3, 2, 1, 5,
00382 3, 3, 2, 2,
00383 3, 3, 3, 2,
00384 3, 2, 3, 2,
00385 2, 2, 6,
00386
00387 2, 7, 1,
00388 3, 1, 1, 2,
00389 3, 2, 1, 2,
00390 3, 1, 2, 2,
00391 3, 4, 2, 3,
00392 3, 3, 1, 4,
00393 3, 3, 1, 3,
00394 3, 2, 1, 4,
00395 2, 2, 9,
00396 3, 2, 1, 5,
00397 2, 2, 7,
00398 1, 14,
00399 2, 8, 2,
00400 3, 6, 2, 2,
00401 4, 2, 8, 1, 3,
00402 4, 1, 5, 5, 2,
00403 5, 1, 3, 2, 4, 1,
00404 5, 3, 1, 2, 4, 1,
00405 5, 1, 1, 3, 1, 3,
00406 4, 2, 1, 1, 2
00407 };
00408
00414 static const int p200[] =
00415 { 25, 25,
00416
00417 4, 1,1,2,2,
00418 3, 5,5,7,
00419 4, 5,2,2,9,
00420 4, 3,2,3,9,
00421 5, 1,1,3,2,7,
00422 3, 3,1,5,
00423 5, 7,1,1,1,3,
00424 6, 1,2,1,1,2,1,
00425 3, 4,2,4,
00426 4, 1,2,2,2,
00427 3, 4,6,2,
00428 4, 1,2,2,1,
00429 4, 3,3,2,1,
00430 3, 4,1,15,
00431 6, 1,1,1,3,1,1,
00432 6, 2,1,1,2,2,3,
00433 4, 1,4,4,1,
00434 4, 1,4,3,2,
00435 4, 1,1,2,2,
00436 5, 7,2,3,1,1,
00437 5, 2,1,1,1,5,
00438 3, 1,2,5,
00439 4, 1,1,1,3,
00440 3, 4,2,1,
00441 1, 3,
00442
00443 3, 2,2,3,
00444 5, 4,1,1,1,4,
00445 5, 4,1,2,1,1,
00446 7, 4,1,1,1,1,1,1,
00447 6, 2,1,1,2,3,5,
00448 6, 1,1,1,1,2,1,
00449 5, 3,1,5,1,2,
00450 6, 3,2,2,1,2,2,
00451 7, 2,1,4,1,1,1,1,
00452 6, 2,2,1,2,1,2,
00453 6, 1,1,1,3,2,3,
00454 5, 1,1,2,7,3,
00455 5, 1,2,2,1,5,
00456 5, 3,2,2,1,2,
00457 4, 3,2,1,2,
00458 3, 5,1,2,
00459 4, 2,2,1,2,
00460 4, 4,2,1,2,
00461 4, 6,2,3,2,
00462 4, 7,4,3,2,
00463 3, 7,4,4,
00464 3, 7,1,4,
00465 3, 6,1,4,
00466 3, 4,2,2,
00467 2, 2,1
00468 };
00469
00471 const int *specs[] = {heart, bear, crocodile, unknown,
00472 pinwheel, difficult, non_unique, dragonfly, p200};
00474 const unsigned n_examples = sizeof(specs)/sizeof(int*);
00476
00477