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