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
00042 namespace {
00043
00048 extern const int *specs[];
00053 extern const unsigned int n_examples;
00054
00055 }
00056
00068 class Domino : public Script {
00069 private:
00071 const int *spec;
00073 int width;
00075 int height;
00076
00078 IntVarArray x;
00079
00080 public:
00082 enum {
00083 PROP_ELEMENT,
00084 PROP_EXTENSIONAL
00085 };
00086
00088 Domino(const SizeOptions& opt)
00089 : Script(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 rel(*this, x[i*(width+1)+8]==28);
00105 }
00106
00107
00108
00109 IntVarArgs p1(*this, 28, 0, (width+1)*height-1);
00110 IntVarArgs 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, expr(*this, p1[dominoCount]-p2[dominoCount]),
00129 diff, IPL_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-1) {
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 IntVarArgs piece(2);
00170 piece[0] = p1[dominoCount];
00171 piece[1] = p2[dominoCount];
00172 extensional(*this, piece, valids);
00173
00174
00175
00176
00177 element(*this, x, p1[dominoCount], dominoCount);
00178 element(*this, x, p2[dominoCount], dominoCount);
00179 dominoCount++;
00180 }
00181 }
00182
00183
00184 IntVarArgs ps(28*2);
00185 for (int i=0; i<28; i++) {
00186 ps[2*i] = p1[i];
00187 ps[2*i+1] = p2[i];
00188 }
00189
00190 branch(*this, ps, INT_VAR_NONE(), INT_VAL_MIN());
00191 }
00192
00194 virtual void
00195 print(std::ostream& os) const {
00196 for (int h = 0; h < height; ++h) {
00197 os << "\t";
00198 for (int w = 0; w < width; ++w) {
00199 int val = x[h*(width+1)+w].min();
00200 char c = val < 10 ? '0'+val : 'A' + (val-10);
00201 os << c;
00202 }
00203 os << std::endl;
00204 }
00205 os << std::endl;
00206 }
00208 Domino(Domino& s) :
00209 Script(s), spec(s.spec), width(s.width), height(s.height) {
00210 x.update(*this, s.x);
00211 }
00213 virtual Space*
00214 copy(void) {
00215 return new Domino(*this);
00216 }
00217
00218 };
00219
00220
00224 int
00225 main(int argc, char* argv[]) {
00226 SizeOptions opt("Domino");
00227 opt.size(0);
00228 opt.propagation(Domino::PROP_ELEMENT);
00229 opt.propagation(Domino::PROP_ELEMENT, "element");
00230 opt.propagation(Domino::PROP_EXTENSIONAL, "extensional");
00231 opt.parse(argc,argv);
00232 if (opt.size() >= n_examples) {
00233 std::cerr << "Error: size must be between 0 and "
00234 << n_examples-1 << std::endl;
00235 return 1;
00236 }
00237 Script::run<Domino,DFS,SizeOptions>(opt);
00238 return 0;
00239 }
00240
00241
00242 namespace {
00243
00249
00251 const int domino0[] =
00252 {
00253 8,7,
00254
00255 2,1,0,3,0,4,5,5,
00256 6,2,0,6,3,1,4,0,
00257 3,2,3,6,2,5,4,3,
00258 5,4,5,1,1,2,1,2,
00259 0,0,1,5,0,5,4,4,
00260 4,6,2,1,3,6,6,1,
00261 4,2,0,6,5,3,3,6
00262 };
00263
00265 const int domino1[] =
00266 {
00267 8,7,
00268
00269 5,1,2,4,6,2,0,5,
00270 6,6,4,3,5,0,1,5,
00271 2,0,4,0,4,0,5,0,
00272 6,1,3,6,3,5,4,3,
00273 3,1,0,1,2,2,1,4,
00274 3,6,6,2,4,0,5,4,
00275 1,3,6,1,2,3,5,2
00276 };
00277
00279 const int domino2[] =
00280 {
00281 8,7,
00282
00283 4,4,5,4,0,3,6,5,
00284 1,6,0,1,5,3,4,1,
00285 2,6,2,2,5,3,6,0,
00286 1,3,0,6,4,4,2,3,
00287 3,5,5,2,4,2,2,1,
00288 2,1,3,3,5,6,6,1,
00289 5,1,6,0,0,0,4,0
00290 };
00291
00293 const int domino3[] =
00294 {
00295 8,7,
00296
00297 3,0,2,3,3,4,4,3,
00298 6,5,3,4,2,0,2,1,
00299 6,5,1,2,3,0,2,0,
00300 4,5,4,1,6,6,2,5,
00301 4,3,6,1,0,4,5,5,
00302 1,3,2,5,6,0,0,1,
00303 0,5,4,6,2,1,6,1
00304 };
00305
00307 const int domino4[] =
00308 {
00309 8,7,
00310
00311 4,1,5,2,4,4,6,2,
00312 2,5,6,1,4,6,0,2,
00313 6,5,1,1,0,1,4,3,
00314 6,2,1,1,3,2,0,6,
00315 3,6,3,3,5,5,0,5,
00316 3,0,1,0,0,5,4,3,
00317 3,2,4,5,4,2,6,0
00318 };
00319
00321 const int domino5[] =
00322 {
00323 8,7,
00324
00325 4,1,2,1,0,2,4,4,
00326 5,5,6,6,0,4,6,3,
00327 6,0,5,1,1,0,5,3,
00328 3,4,2,2,0,3,1,2,
00329 3,6,5,6,1,2,3,2,
00330 2,5,0,6,6,3,3,5,
00331 4,1,0,0,4,1,4,5
00332 };
00333
00335 const int *specs[] =
00336 {domino0,domino1,domino2,domino3,domino4,domino5};
00338 const unsigned n_examples = sizeof(specs)/sizeof(int*);
00340
00341 }
00342
00343