Generated on Thu Mar 22 10:39:31 2012 for Gecode by doxygen 1.6.3

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-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $
00013  *     $Revision: 11473 $
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