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