Generated on Wed Mar 19 07:29:53 2008 for Gecode by doxygen 1.5.5

domino.cc

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: 2007-11-30 13:58:34 +0100 (Fri, 30 Nov 2007) $ by $Author: tack $
00013  *     $Revision: 5524 $
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 "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; // skip board size information
00094     
00095     // Copy spec information to the board
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     // Initialize the separator column in the board
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     // Variables representing the coordinates of the first
00108     // and second half of a domino piece
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           // The two coordinates must be adjacent.
00123           // I.e., they may differ by 1 or by the width.
00124           // The separator column makes sure that a field
00125           // at the right border is not adjacent to the first field
00126           // in the next row.
00127           IntVar diff(this, possibleDiffs);
00128           abs(this, minus(this, p1[dominoCount], p2[dominoCount]),
00129               diff, ICL_DOM);
00130 
00131           // If the piece is symmetrical, order the locations
00132           if (i == j)
00133             rel(this, p1[dominoCount], IRT_LE, p2[dominoCount]);
00134           
00135           // Link the current piece to the board
00136           element(this, board, p1[dominoCount], i);
00137           element(this, board, p2[dominoCount], j);
00138           
00139           // Link the current piece to the array where its
00140           // number is stored.
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           // Find valid placements for piece i-j
00151           // Extensional is used as a table-constraint listing all valid
00152           // tuples.
00153           // Note that when i == j, only one of the orientations are used.
00154           REG valids;
00155           for (int pos = 0; pos < (width+1)*height; ++pos) {
00156             if ((pos+1) % width+1 != 0) { // not end-col
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) { // not end-row
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           // Link the current piece to the array where its
00177           // number is stored.
00178           element(this, x, p1[dominoCount], dominoCount);
00179           element(this, x, p2[dominoCount], dominoCount);
00180           dominoCount++;
00181         }
00182     }
00183 
00184     // Branch by piece
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     // Install branchings
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     { // width*height of the board
00255       8,7,
00256       // the board itself
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     { // width*height of the board
00269       8,7,
00270       // the board itself
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     { // width*height of the board
00283       8,7,
00284       // the board itself
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     { // width*height of the board
00297       8,7,
00298       // the board itself
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     { // width*height of the board
00311       8,7,
00312       // the board itself
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     { // width*height of the board
00325       8,7,
00326       // the board itself
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 // STATISTICS: example-any