Generated on Sat Feb 7 2015 02:01:11 for Gecode by doxygen 1.8.9.1
domino.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  * Mikael Lagerkvist <lagerkvist@gecode.org>
6  *
7  * Copyright:
8  * Guido Tack, 2006
9  * Mikael Lagerkvist, 2006
10  *
11  * Last modified:
12  * $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
13  * $Revision: 13820 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/driver.hh>
41 #include <gecode/int.hh>
42 #include <gecode/minimodel.hh>
43 
44 using namespace Gecode;
45 
46 namespace {
47 
52  extern const int *specs[];
57  extern const unsigned int n_examples;
58 
59 }
60 
72 class Domino : public Script {
73 private:
75  const int *spec;
77  int width;
79  int height;
80 
82  IntVarArray x;
83 
84 public:
86  enum {
88  PROP_EXTENSIONAL
89  };
90 
93  : spec(specs[opt.size()]),
94  width(spec[0]), height(spec[1]),
95  x(*this, (width+1)*height, 0, 28) {
96  spec+=2; // skip board size information
97 
98  // Copy spec information to the board
99  IntArgs board((width+1)*height);
100  for (int i=0; i<width; i++)
101  for (int j=0; j<height; j++)
102  board[j*(width+1)+i] = spec[j*width+i];
103 
104  // Initialize the separator column in the board
105  for (int i=0; i<height; i++) {
106  board[i*(width+1)+8] = -1;
107  rel(*this, x[i*(width+1)+8]==28);
108  }
109 
110  // Variables representing the coordinates of the first
111  // and second half of a domino piece
112  IntVarArgs p1(*this, 28, 0, (width+1)*height-1);
113  IntVarArgs p2(*this, 28, 0, (width+1)*height-1);
114 
115 
116  if (opt.propagation() == PROP_ELEMENT) {
117  int dominoCount = 0;
118 
119  int possibleDiffsA[] = {1, width+1};
120  IntSet possibleDiffs(possibleDiffsA, 2);
121 
122  for (int i=0; i<=6; i++)
123  for (int j=i; j<=6; j++) {
124 
125  // The two coordinates must be adjacent.
126  // I.e., they may differ by 1 or by the width.
127  // The separator column makes sure that a field
128  // at the right border is not adjacent to the first field
129  // in the next row.
130  IntVar diff(*this, possibleDiffs);
131  abs(*this, expr(*this, p1[dominoCount]-p2[dominoCount]),
132  diff, ICL_DOM);
133 
134  // If the piece is symmetrical, order the locations
135  if (i == j)
136  rel(*this, p1[dominoCount], IRT_LE, p2[dominoCount]);
137 
138  // Link the current piece to the board
139  element(*this, board, p1[dominoCount], i);
140  element(*this, board, p2[dominoCount], j);
141 
142  // Link the current piece to the array where its
143  // number is stored.
144  element(*this, x, p1[dominoCount], dominoCount);
145  element(*this, x, p2[dominoCount], dominoCount);
146  dominoCount++;
147  }
148  } else {
149  int dominoCount = 0;
150 
151  for (int i=0; i<=6; i++)
152  for (int j=i; j<=6; j++) {
153  // Find valid placements for piece i-j
154  // Extensional is used as a table-constraint listing all valid
155  // tuples.
156  // Note that when i == j, only one of the orientations are used.
157  REG valids;
158  for (int pos = 0; pos < (width+1)*height; ++pos) {
159  if ((pos+1) % (width+1) != 0) { // not end-col
160  if (board[pos] == i && board[pos+1] == j)
161  valids |= REG(pos) + REG(pos+1);
162  if (board[pos] == j && board[pos+1] == i && i != j)
163  valids |= REG(pos+1) + REG(pos);
164  }
165  if (pos/(width+1) < height-1) { // not end-row
166  if (board[pos] == i && board[pos+width+1] == j)
167  valids |= REG(pos) + REG(pos+width+1);
168  if (board[pos] == j && board[pos+width+1] == i && i != j)
169  valids |= REG(pos+width+1) + REG(pos);
170  }
171  }
172  IntVarArgs piece(2);
173  piece[0] = p1[dominoCount];
174  piece[1] = p2[dominoCount];
175  extensional(*this, piece, valids);
176 
177 
178  // Link the current piece to the array where its
179  // number is stored.
180  element(*this, x, p1[dominoCount], dominoCount);
181  element(*this, x, p2[dominoCount], dominoCount);
182  dominoCount++;
183  }
184  }
185 
186  // Branch by piece
187  IntVarArgs ps(28*2);
188  for (int i=0; i<28; i++) {
189  ps[2*i] = p1[i];
190  ps[2*i+1] = p2[i];
191  }
192 
193  branch(*this, ps, INT_VAR_NONE(), INT_VAL_MIN());
194  }
195 
197  virtual void
198  print(std::ostream& os) const {
199  for (int h = 0; h < height; ++h) {
200  os << "\t";
201  for (int w = 0; w < width; ++w) {
202  int val = x[h*(width+1)+w].min();
203  char c = val < 10 ? '0'+val : 'A' + (val-10);
204  os << c;
205  }
206  os << std::endl;
207  }
208  os << std::endl;
209  }
211  Domino(bool share, Domino& s) :
212  Script(share,s), spec(s.spec), width(s.width), height(s.height) {
213  x.update(*this, share, s.x);
214  }
216  virtual Space*
217  copy(bool share) {
218  return new Domino(share,*this);
219  }
220 
221 };
222 
223 
227 int
228 main(int argc, char* argv[]) {
229  SizeOptions opt("Domino");
230  opt.size(0);
232  opt.propagation(Domino::PROP_ELEMENT, "element");
233  opt.propagation(Domino::PROP_EXTENSIONAL, "extensional");
234  opt.parse(argc,argv);
235  if (opt.size() >= n_examples) {
236  std::cerr << "Error: size must be between 0 and "
237  << n_examples-1 << std::endl;
238  return 1;
239  }
240  Script::run<Domino,DFS,SizeOptions>(opt);
241  return 0;
242 }
243 
244 
245 namespace {
246 
252 
254  const int domino0[] =
255  { // width*height of the board
256  8,7,
257  // the board itself
258  2,1,0,3,0,4,5,5,
259  6,2,0,6,3,1,4,0,
260  3,2,3,6,2,5,4,3,
261  5,4,5,1,1,2,1,2,
262  0,0,1,5,0,5,4,4,
263  4,6,2,1,3,6,6,1,
264  4,2,0,6,5,3,3,6
265  };
266 
268  const int domino1[] =
269  { // width*height of the board
270  8,7,
271  // the board itself
272  5,1,2,4,6,2,0,5,
273  6,6,4,3,5,0,1,5,
274  2,0,4,0,4,0,5,0,
275  6,1,3,6,3,5,4,3,
276  3,1,0,1,2,2,1,4,
277  3,6,6,2,4,0,5,4,
278  1,3,6,1,2,3,5,2
279  };
280 
282  const int domino2[] =
283  { // width*height of the board
284  8,7,
285  // the board itself
286  4,4,5,4,0,3,6,5,
287  1,6,0,1,5,3,4,1,
288  2,6,2,2,5,3,6,0,
289  1,3,0,6,4,4,2,3,
290  3,5,5,2,4,2,2,1,
291  2,1,3,3,5,6,6,1,
292  5,1,6,0,0,0,4,0
293  };
294 
296  const int domino3[] =
297  { // width*height of the board
298  8,7,
299  // the board itself
300  3,0,2,3,3,4,4,3,
301  6,5,3,4,2,0,2,1,
302  6,5,1,2,3,0,2,0,
303  4,5,4,1,6,6,2,5,
304  4,3,6,1,0,4,5,5,
305  1,3,2,5,6,0,0,1,
306  0,5,4,6,2,1,6,1
307  };
308 
310  const int domino4[] =
311  { // width*height of the board
312  8,7,
313  // the board itself
314  4,1,5,2,4,4,6,2,
315  2,5,6,1,4,6,0,2,
316  6,5,1,1,0,1,4,3,
317  6,2,1,1,3,2,0,6,
318  3,6,3,3,5,5,0,5,
319  3,0,1,0,0,5,4,3,
320  3,2,4,5,4,2,6,0
321  };
322 
324  const int domino5[] =
325  { // width*height of the board
326  8,7,
327  // the board itself
328  4,1,2,1,0,2,4,4,
329  5,5,6,6,0,4,6,3,
330  6,0,5,1,1,0,5,3,
331  3,4,2,2,0,3,1,2,
332  3,6,5,6,1,2,3,2,
333  2,5,0,6,6,3,3,5,
334  4,1,0,0,4,1,4,5
335  };
336 
338  const int *specs[] =
339  {domino0,domino1,domino2,domino3,domino4,domino5};
341  const unsigned n_examples = sizeof(specs)/sizeof(int*);
343 
344 }
345 
346 // STATISTICS: example-any
void size(unsigned int s)
Set default size.
Definition: options.hpp:467
Options for scripts with additional size parameter
Definition: driver.hh:567
virtual Space * copy(bool share)
Copy space during cloning.
Definition: domino.cpp:217
Use extensional constraints.
Definition: domino.cpp:88
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
Domino(const SizeOptions &opt)
Actual model.
Definition: domino.cpp:92
void propagation(int v)
Set default propagation value.
Definition: options.hpp:181
Regular expressions over integer values.
Definition: minimodel.hh:1401
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:49
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:435
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
int main(int argc, char *argv[])
Main-function.
Definition: domino.cpp:228
Integer variable array.
Definition: int.hh:741
Domino(bool share, Domino &s)
Constructor for cloning s.
Definition: domino.cpp:211
Computation spaces.
Definition: core.hpp:1362
Parametric base-class for scripts.
Definition: driver.hh:622
virtual void print(std::ostream &os) const
Print solution.
Definition: domino.cpp:198
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs p2(4, 4, 3, 3, 5)
Gecode::IntArgs i(4, 1, 2, 3, 4)
Options opt
The options.
Definition: test.cpp:101
Use element constraints.
Definition: domino.cpp:87
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
unsigned int size(I &i)
Size of all ranges of range iterator i.
Less ( )
Definition: int.hh:907
Integer sets.
Definition: int.hh:171
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntConLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition: extensional.cpp:45
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
const unsigned int n_examples
Number of board specifications.
Definition: domino.cpp:57
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Integer variables.
Definition: int.hh:350
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Gecode toplevel namespace
Example: Solitaire domino
Definition: domino.cpp:72
BrancherHandle branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:43
Gecode::IntArgs p1(4, 2, 2, 2, 2)
Domain propagation or consistency.
Definition: int.hh:940