domino.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Mikael Lagerkvist <lagerkvist@gecode.org> 00006 * 00007 * Copyright: 00008 * Guido Tack, 2006 00009 * Mikael Lagerkvist, 2006 00010 * 00011 * Last modified: 00012 * $Date: 2010-05-08 19:24:20 +0200 (Sat, 08 May 2010) $ by $Author: tack $ 00013 * $Revision: 10910 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 : spec(specs[opt.size()]), 00094 width(spec[0]), height(spec[1]), 00095 x(*this, (width+1)*height, 0, 28) { 00096 spec+=2; // skip board size information 00097 00098 // Copy spec information to the board 00099 IntArgs board((width+1)*height); 00100 for (int i=0; i<width; i++) 00101 for (int j=0; j<height; j++) 00102 board[j*(width+1)+i] = spec[j*width+i]; 00103 00104 // Initialize the separator column in the board 00105 for (int i=0; i<height; i++) { 00106 board[i*(width+1)+8] = -1; 00107 rel(*this, x[i*(width+1)+8]==28); 00108 } 00109 00110 // Variables representing the coordinates of the first 00111 // and second half of a domino piece 00112 IntVarArgs p1(*this, 28, 0, (width+1)*height-1); 00113 IntVarArgs p2(*this, 28, 0, (width+1)*height-1); 00114 00115 00116 if (opt.propagation() == PROP_ELEMENT) { 00117 int dominoCount = 0; 00118 00119 int possibleDiffsA[] = {1, width+1}; 00120 IntSet possibleDiffs(possibleDiffsA, 2); 00121 00122 for (int i=0; i<=6; i++) 00123 for (int j=i; j<=6; j++) { 00124 00125 // The two coordinates must be adjacent. 00126 // I.e., they may differ by 1 or by the width. 00127 // The separator column makes sure that a field 00128 // at the right border is not adjacent to the first field 00129 // in the next row. 00130 IntVar diff(*this, possibleDiffs); 00131 abs(*this, expr(*this, p1[dominoCount]-p2[dominoCount]), 00132 diff, ICL_DOM); 00133 00134 // If the piece is symmetrical, order the locations 00135 if (i == j) 00136 rel(*this, p1[dominoCount], IRT_LE, p2[dominoCount]); 00137 00138 // Link the current piece to the board 00139 element(*this, board, p1[dominoCount], i); 00140 element(*this, board, p2[dominoCount], j); 00141 00142 // Link the current piece to the array where its 00143 // number is stored. 00144 element(*this, x, p1[dominoCount], dominoCount); 00145 element(*this, x, p2[dominoCount], dominoCount); 00146 dominoCount++; 00147 } 00148 } else { 00149 int dominoCount = 0; 00150 00151 for (int i=0; i<=6; i++) 00152 for (int j=i; j<=6; j++) { 00153 // Find valid placements for piece i-j 00154 // Extensional is used as a table-constraint listing all valid 00155 // tuples. 00156 // Note that when i == j, only one of the orientations are used. 00157 REG valids; 00158 for (int pos = 0; pos < (width+1)*height; ++pos) { 00159 if ((pos+1) % (width+1) != 0) { // not end-col 00160 if (board[pos] == i && board[pos+1] == j) 00161 valids |= REG(pos) + REG(pos+1); 00162 if (board[pos] == j && board[pos+1] == i && i != j) 00163 valids |= REG(pos+1) + REG(pos); 00164 } 00165 if (pos/(width+1) < height-1) { // not end-row 00166 if (board[pos] == i && board[pos+width+1] == j) 00167 valids |= REG(pos) + REG(pos+width+1); 00168 if (board[pos] == j && board[pos+width+1] == i && i != j) 00169 valids |= REG(pos+width+1) + REG(pos); 00170 } 00171 } 00172 IntVarArgs piece(2); 00173 piece[0] = p1[dominoCount]; 00174 piece[1] = p2[dominoCount]; 00175 extensional(*this, piece, valids); 00176 00177 00178 // Link the current piece to the array where its 00179 // number is stored. 00180 element(*this, x, p1[dominoCount], dominoCount); 00181 element(*this, x, p2[dominoCount], dominoCount); 00182 dominoCount++; 00183 } 00184 } 00185 00186 // Branch by piece 00187 IntVarArgs ps(28*2); 00188 for (int i=0; i<28; i++) { 00189 ps[2*i] = p1[i]; 00190 ps[2*i+1] = p2[i]; 00191 } 00192 00193 branch(*this, ps, INT_VAR_NONE, INT_VAL_MIN); 00194 } 00195 00197 virtual void 00198 print(std::ostream& os) const { 00199 for (int h = 0; h < height; ++h) { 00200 os << "\t"; 00201 for (int w = 0; w < width; ++w) { 00202 int val = x[h*(width+1)+w].min(); 00203 char c = val < 10 ? '0'+val : 'A' + (val-10); 00204 os << c; 00205 } 00206 os << std::endl; 00207 } 00208 os << std::endl; 00209 } 00211 Domino(bool share, Domino& s) : 00212 Script(share,s), spec(s.spec), width(s.width), height(s.height) { 00213 x.update(*this, share, s.x); 00214 } 00216 virtual Space* 00217 copy(bool share) { 00218 return new Domino(share,*this); 00219 } 00220 00221 }; 00222 00223 00227 int 00228 main(int argc, char* argv[]) { 00229 SizeOptions opt("Domino"); 00230 opt.size(0); 00231 opt.propagation(Domino::PROP_ELEMENT); 00232 opt.propagation(Domino::PROP_ELEMENT, "element"); 00233 opt.propagation(Domino::PROP_EXTENSIONAL, "extensional"); 00234 opt.parse(argc,argv); 00235 if (opt.size() >= n_examples) { 00236 std::cerr << "Error: size must be between 0 and " 00237 << n_examples-1 << std::endl; 00238 return 1; 00239 } 00240 Script::run<Domino,DFS,SizeOptions>(opt); 00241 return 0; 00242 } 00243 00244 00245 namespace { 00246 00252 00254 const int domino0[] = 00255 { // width*height of the board 00256 8,7, 00257 // the board itself 00258 2,1,0,3,0,4,5,5, 00259 6,2,0,6,3,1,4,0, 00260 3,2,3,6,2,5,4,3, 00261 5,4,5,1,1,2,1,2, 00262 0,0,1,5,0,5,4,4, 00263 4,6,2,1,3,6,6,1, 00264 4,2,0,6,5,3,3,6 00265 }; 00266 00268 const int domino1[] = 00269 { // width*height of the board 00270 8,7, 00271 // the board itself 00272 5,1,2,4,6,2,0,5, 00273 6,6,4,3,5,0,1,5, 00274 2,0,4,0,4,0,5,0, 00275 6,1,3,6,3,5,4,3, 00276 3,1,0,1,2,2,1,4, 00277 3,6,6,2,4,0,5,4, 00278 1,3,6,1,2,3,5,2 00279 }; 00280 00282 const int domino2[] = 00283 { // width*height of the board 00284 8,7, 00285 // the board itself 00286 4,4,5,4,0,3,6,5, 00287 1,6,0,1,5,3,4,1, 00288 2,6,2,2,5,3,6,0, 00289 1,3,0,6,4,4,2,3, 00290 3,5,5,2,4,2,2,1, 00291 2,1,3,3,5,6,6,1, 00292 5,1,6,0,0,0,4,0 00293 }; 00294 00296 const int domino3[] = 00297 { // width*height of the board 00298 8,7, 00299 // the board itself 00300 3,0,2,3,3,4,4,3, 00301 6,5,3,4,2,0,2,1, 00302 6,5,1,2,3,0,2,0, 00303 4,5,4,1,6,6,2,5, 00304 4,3,6,1,0,4,5,5, 00305 1,3,2,5,6,0,0,1, 00306 0,5,4,6,2,1,6,1 00307 }; 00308 00310 const int domino4[] = 00311 { // width*height of the board 00312 8,7, 00313 // the board itself 00314 4,1,5,2,4,4,6,2, 00315 2,5,6,1,4,6,0,2, 00316 6,5,1,1,0,1,4,3, 00317 6,2,1,1,3,2,0,6, 00318 3,6,3,3,5,5,0,5, 00319 3,0,1,0,0,5,4,3, 00320 3,2,4,5,4,2,6,0 00321 }; 00322 00324 const int domino5[] = 00325 { // width*height of the board 00326 8,7, 00327 // the board itself 00328 4,1,2,1,0,2,4,4, 00329 5,5,6,6,0,4,6,3, 00330 6,0,5,1,1,0,5,3, 00331 3,4,2,2,0,3,1,2, 00332 3,6,5,6,1,2,3,2, 00333 2,5,0,6,6,3,3,5, 00334 4,1,0,0,4,1,4,5 00335 }; 00336 00338 const int *specs[] = 00339 {domino0,domino1,domino2,domino3,domino4,domino5}; 00341 const unsigned n_examples = sizeof(specs)/sizeof(int*); 00343 00344 } 00345 00346 // STATISTICS: example-any