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 extensional(*this, IntVarArgs({p1[dominoCount],p2[dominoCount]}),
00170 valids);
00171
00172
00173
00174
00175 element(*this, x, p1[dominoCount], dominoCount);
00176 element(*this, x, p2[dominoCount], dominoCount);
00177 dominoCount++;
00178 }
00179 }
00180
00181
00182 IntVarArgs ps(28*2);
00183 for (int i=0; i<28; i++) {
00184 ps[2*i] = p1[i];
00185 ps[2*i+1] = p2[i];
00186 }
00187
00188 branch(*this, ps, INT_VAR_NONE(), INT_VAL_MIN());
00189 }
00190
00192 virtual void
00193 print(std::ostream& os) const {
00194 for (int h = 0; h < height; ++h) {
00195 os << "\t";
00196 for (int w = 0; w < width; ++w) {
00197 int val = x[h*(width+1)+w].min();
00198 char c = val < 10 ? '0'+val : 'A' + (val-10);
00199 os << c;
00200 }
00201 os << std::endl;
00202 }
00203 os << std::endl;
00204 }
00206 Domino(Domino& s) :
00207 Script(s), spec(s.spec), width(s.width), height(s.height) {
00208 x.update(*this, s.x);
00209 }
00211 virtual Space*
00212 copy(void) {
00213 return new Domino(*this);
00214 }
00215
00216 };
00217
00218
00222 int
00223 main(int argc, char* argv[]) {
00224 SizeOptions opt("Domino");
00225 opt.size(0);
00226 opt.propagation(Domino::PROP_ELEMENT);
00227 opt.propagation(Domino::PROP_ELEMENT, "element");
00228 opt.propagation(Domino::PROP_EXTENSIONAL, "extensional");
00229 opt.parse(argc,argv);
00230 if (opt.size() >= n_examples) {
00231 std::cerr << "Error: size must be between 0 and "
00232 << n_examples-1 << std::endl;
00233 return 1;
00234 }
00235 Script::run<Domino,DFS,SizeOptions>(opt);
00236 return 0;
00237 }
00238
00239
00240 namespace {
00241
00247
00249 const int domino0[] =
00250 {
00251 8,7,
00252
00253 2,1,0,3,0,4,5,5,
00254 6,2,0,6,3,1,4,0,
00255 3,2,3,6,2,5,4,3,
00256 5,4,5,1,1,2,1,2,
00257 0,0,1,5,0,5,4,4,
00258 4,6,2,1,3,6,6,1,
00259 4,2,0,6,5,3,3,6
00260 };
00261
00263 const int domino1[] =
00264 {
00265 8,7,
00266
00267 5,1,2,4,6,2,0,5,
00268 6,6,4,3,5,0,1,5,
00269 2,0,4,0,4,0,5,0,
00270 6,1,3,6,3,5,4,3,
00271 3,1,0,1,2,2,1,4,
00272 3,6,6,2,4,0,5,4,
00273 1,3,6,1,2,3,5,2
00274 };
00275
00277 const int domino2[] =
00278 {
00279 8,7,
00280
00281 4,4,5,4,0,3,6,5,
00282 1,6,0,1,5,3,4,1,
00283 2,6,2,2,5,3,6,0,
00284 1,3,0,6,4,4,2,3,
00285 3,5,5,2,4,2,2,1,
00286 2,1,3,3,5,6,6,1,
00287 5,1,6,0,0,0,4,0
00288 };
00289
00291 const int domino3[] =
00292 {
00293 8,7,
00294
00295 3,0,2,3,3,4,4,3,
00296 6,5,3,4,2,0,2,1,
00297 6,5,1,2,3,0,2,0,
00298 4,5,4,1,6,6,2,5,
00299 4,3,6,1,0,4,5,5,
00300 1,3,2,5,6,0,0,1,
00301 0,5,4,6,2,1,6,1
00302 };
00303
00305 const int domino4[] =
00306 {
00307 8,7,
00308
00309 4,1,5,2,4,4,6,2,
00310 2,5,6,1,4,6,0,2,
00311 6,5,1,1,0,1,4,3,
00312 6,2,1,1,3,2,0,6,
00313 3,6,3,3,5,5,0,5,
00314 3,0,1,0,0,5,4,3,
00315 3,2,4,5,4,2,6,0
00316 };
00317
00319 const int domino5[] =
00320 {
00321 8,7,
00322
00323 4,1,2,1,0,2,4,4,
00324 5,5,6,6,0,4,6,3,
00325 6,0,5,1,1,0,5,3,
00326 3,4,2,2,0,3,1,2,
00327 3,6,5,6,1,2,3,2,
00328 2,5,0,6,6,3,3,5,
00329 4,1,0,0,4,1,4,5
00330 };
00331
00333 const int *specs[] =
00334 {domino0,domino1,domino2,domino3,domino4,domino5};
00336 const unsigned n_examples = sizeof(specs)/sizeof(int*);
00338
00339 }
00340
00341