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 "examples/support.hh"
00041 #include "gecode/minimodel.hh"
00042
00043 namespace {
00044
00049 extern const int *specs[];
00054 extern const unsigned int n_examples;
00055
00056 }
00057
00069 class Domino : public Example {
00070 private:
00072 const int *spec;
00074 int width;
00076 int height;
00077
00079 IntVarArray x;
00080
00081 public:
00083 enum {
00084 PROP_ELEMENT,
00085 PROP_EXTENSIONAL
00086 };
00087
00089 Domino(const SizeOptions& opt)
00090 : spec(specs[opt.size()]),
00091 width(spec[0]), height(spec[1]),
00092 x(this, (width+1)*height, 0, 28) {
00093 spec+=2;
00094
00095
00096 IntArgs board((width+1)*height);
00097 for (int i=0; i<width; i++)
00098 for (int j=0; j<height; j++)
00099 board[j*(width+1)+i] = spec[j*width+i];
00100
00101
00102 for (int i=0; i<height; i++) {
00103 board[i*(width+1)+8] = -1;
00104 post(this, x[i*(width+1)+8]==28);
00105 }
00106
00107
00108
00109 IntVarArray p1(this, 28, 0, (width+1)*height-1);
00110 IntVarArray p2(this, 28, 0, (width+1)*height-1);
00111
00112
00113 if (opt.propagation() == PROP_ELEMENT) {
00114 int dominoCount = 0;
00115
00116 int possibleDiffsA[] = {1, width+1};
00117 IntSet possibleDiffs(possibleDiffsA, 2);
00118
00119 for (int i=0; i<=6; i++)
00120 for (int j=i; j<=6; j++) {
00121
00122
00123
00124
00125
00126
00127 IntVar diff(this, possibleDiffs);
00128 abs(this, minus(this, p1[dominoCount], p2[dominoCount]),
00129 diff, ICL_DOM);
00130
00131
00132 if (i == j)
00133 rel(this, p1[dominoCount], IRT_LE, p2[dominoCount]);
00134
00135
00136 element(this, board, p1[dominoCount], i);
00137 element(this, board, p2[dominoCount], j);
00138
00139
00140
00141 element(this, x, p1[dominoCount], dominoCount);
00142 element(this, x, p2[dominoCount], dominoCount);
00143 dominoCount++;
00144 }
00145 } else {
00146 int dominoCount = 0;
00147
00148 for (int i=0; i<=6; i++)
00149 for (int j=i; j<=6; j++) {
00150
00151
00152
00153
00154 REG valids;
00155 for (int pos = 0; pos < (width+1)*height; ++pos) {
00156 if ((pos+1) % width+1 != 0) {
00157 if (board[pos] == i && board[pos+1] == j)
00158 valids |= REG(pos) + REG(pos+1);
00159 if (board[pos] == j && board[pos+1] == i && i != j)
00160 valids |= REG(pos+1) + REG(pos);
00161 }
00162 if (pos/(width+1) < height) {
00163 if (board[pos] == i && board[pos+width+1] == j)
00164 valids |= REG(pos) + REG(pos+width+1);
00165 if (board[pos] == j && board[pos+width+1] == i && i != j)
00166 valids |= REG(pos+width+1) + REG(pos);
00167 }
00168
00169 }
00170 IntVarArgs piece(2);
00171 piece[0] = p1[dominoCount];
00172 piece[1] = p2[dominoCount];
00173 extensional(this, piece, valids);
00174
00175
00176
00177
00178 element(this, x, p1[dominoCount], dominoCount);
00179 element(this, x, p2[dominoCount], dominoCount);
00180 dominoCount++;
00181 }
00182 }
00183
00184
00185 IntVarArgs ps(28*2);
00186 for (int i=0; i<28; i++) {
00187 ps[2*i] = p1[i];
00188 ps[2*i+1] = p2[i];
00189 }
00190
00191
00192 branch(this, ps, INT_VAR_NONE, INT_VAL_MIN);
00193 }
00194
00196 virtual void
00197 print(std::ostream& os) {
00198 for (int h = 0; h < height; ++h) {
00199 os << "\t";
00200 for (int w = 0; w < width; ++w) {
00201 int val = x[h*(width+1)+w].min();
00202 char c = val < 10 ? '0'+val : 'A' + (val-10);
00203 os << c;
00204 }
00205 os << std::endl;
00206 }
00207 os << std::endl;
00208 }
00210 Domino(bool share, Domino& s) :
00211 Example(share,s), spec(s.spec), width(s.width), height(s.height) {
00212 x.update(this, share, s.x);
00213 }
00215 virtual Space*
00216 copy(bool share) {
00217 return new Domino(share,*this);
00218 }
00219
00220 };
00221
00222
00226 int
00227 main(int argc, char* argv[]) {
00228 SizeOptions opt("Domino");
00229 opt.size(0);
00230 opt.propagation(Domino::PROP_ELEMENT);
00231 opt.propagation(Domino::PROP_ELEMENT, "element");
00232 opt.propagation(Domino::PROP_EXTENSIONAL, "extensional");
00233 opt.parse(argc,argv);
00234 if (opt.size() >= n_examples) {
00235 std::cerr << "Error: size must be between 0 and "
00236 << n_examples-1 << std::endl;
00237 return 1;
00238 }
00239 Example::run<Domino,DFS,SizeOptions>(opt);
00240 return 0;
00241 }
00242
00243
00244 namespace {
00245
00251
00253 const int domino0[] =
00254 {
00255 8,7,
00256
00257 2,1,0,3,0,4,5,5,
00258 6,2,0,6,3,1,4,0,
00259 3,2,3,6,2,5,4,3,
00260 5,4,5,1,1,2,1,2,
00261 0,0,1,5,0,5,4,4,
00262 4,6,2,1,3,6,6,1,
00263 4,2,0,6,5,3,3,6
00264 };
00265
00267 const int domino1[] =
00268 {
00269 8,7,
00270
00271 5,1,2,4,6,2,0,5,
00272 6,6,4,3,5,0,1,5,
00273 2,0,4,0,4,0,5,0,
00274 6,1,3,6,3,5,4,3,
00275 3,1,0,1,2,2,1,4,
00276 3,6,6,2,4,0,5,4,
00277 1,3,6,1,2,3,5,2
00278 };
00279
00281 const int domino2[] =
00282 {
00283 8,7,
00284
00285 4,4,5,4,0,3,6,5,
00286 1,6,0,1,5,3,4,1,
00287 2,6,2,2,5,3,6,0,
00288 1,3,0,6,4,4,2,3,
00289 3,5,5,2,4,2,2,1,
00290 2,1,3,3,5,6,6,1,
00291 5,1,6,0,0,0,4,0
00292 };
00293
00295 const int domino3[] =
00296 {
00297 8,7,
00298
00299 3,0,2,3,3,4,4,3,
00300 6,5,3,4,2,0,2,1,
00301 6,5,1,2,3,0,2,0,
00302 4,5,4,1,6,6,2,5,
00303 4,3,6,1,0,4,5,5,
00304 1,3,2,5,6,0,0,1,
00305 0,5,4,6,2,1,6,1
00306 };
00307
00309 const int domino4[] =
00310 {
00311 8,7,
00312
00313 4,1,5,2,4,4,6,2,
00314 2,5,6,1,4,6,0,2,
00315 6,5,1,1,0,1,4,3,
00316 6,2,1,1,3,2,0,6,
00317 3,6,3,3,5,5,0,5,
00318 3,0,1,0,0,5,4,3,
00319 3,2,4,5,4,2,6,0
00320 };
00321
00323 const int domino5[] =
00324 {
00325 8,7,
00326
00327 4,1,2,1,0,2,4,4,
00328 5,5,6,6,0,4,6,3,
00329 6,0,5,1,1,0,5,3,
00330 3,4,2,2,0,3,1,2,
00331 3,6,5,6,1,2,3,2,
00332 2,5,0,6,6,3,3,5,
00333 4,1,0,0,4,1,4,5
00334 };
00335
00337 const int *specs[] =
00338 {domino0,domino1,domino2,domino3,domino4,domino5};
00340 const unsigned n_examples = sizeof(specs)/sizeof(int*);
00342
00343 }
00344
00345