Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
40using namespace Gecode;
41
42namespace {
43
48 extern const int *specs[];
53 extern const unsigned int n_examples;
54
55}
56
68class Domino : public Script {
69private:
71 const int *spec;
73 int width;
75 int height;
76
79
80public:
82 enum {
85 };
86
88 Domino(const SizeOptions& opt)
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 extensional(*this, IntVarArgs({p1[dominoCount],p2[dominoCount]}),
170 valids);
171
172
173 // Link the current piece to the array where its
174 // number is stored.
175 element(*this, x, p1[dominoCount], dominoCount);
176 element(*this, x, p2[dominoCount], dominoCount);
177 dominoCount++;
178 }
179 }
180
181 // Branch by piece
182 IntVarArgs ps(28*2);
183 for (int i=0; i<28; i++) {
184 ps[2*i] = p1[i];
185 ps[2*i+1] = p2[i];
186 }
187
188 branch(*this, ps, INT_VAR_NONE(), INT_VAL_MIN());
189 }
190
192 virtual void
193 print(std::ostream& os) const {
194 for (int h = 0; h < height; ++h) {
195 os << "\t";
196 for (int w = 0; w < width; ++w) {
197 int val = x[h*(width+1)+w].min();
198 char c = val < 10 ? '0'+val : 'A' + (val-10);
199 os << c;
200 }
201 os << std::endl;
202 }
203 os << std::endl;
204 }
207 Script(s), spec(s.spec), width(s.width), height(s.height) {
208 x.update(*this, s.x);
209 }
211 virtual Space*
212 copy(void) {
213 return new Domino(*this);
214 }
215
216};
217
218
222int
223main(int argc, char* argv[]) {
224 SizeOptions opt("Domino");
225 opt.size(0);
226 opt.propagation(Domino::PROP_ELEMENT);
227 opt.propagation(Domino::PROP_ELEMENT, "element");
228 opt.propagation(Domino::PROP_EXTENSIONAL, "extensional");
229 opt.parse(argc,argv);
230 if (opt.size() >= n_examples) {
231 std::cerr << "Error: size must be between 0 and "
232 << n_examples-1 << std::endl;
233 return 1;
234 }
236 return 0;
237}
238
239
240namespace {
241
247
249 const int domino0[] =
250 { // width*height of the board
251 8,7,
252 // the board itself
253 2,1,0,3,0,4,5,5,
254 6,2,0,6,3,1,4,0,
255 3,2,3,6,2,5,4,3,
256 5,4,5,1,1,2,1,2,
257 0,0,1,5,0,5,4,4,
258 4,6,2,1,3,6,6,1,
259 4,2,0,6,5,3,3,6
260 };
261
263 const int domino1[] =
264 { // width*height of the board
265 8,7,
266 // the board itself
267 5,1,2,4,6,2,0,5,
268 6,6,4,3,5,0,1,5,
269 2,0,4,0,4,0,5,0,
270 6,1,3,6,3,5,4,3,
271 3,1,0,1,2,2,1,4,
272 3,6,6,2,4,0,5,4,
273 1,3,6,1,2,3,5,2
274 };
275
277 const int domino2[] =
278 { // width*height of the board
279 8,7,
280 // the board itself
281 4,4,5,4,0,3,6,5,
282 1,6,0,1,5,3,4,1,
283 2,6,2,2,5,3,6,0,
284 1,3,0,6,4,4,2,3,
285 3,5,5,2,4,2,2,1,
286 2,1,3,3,5,6,6,1,
287 5,1,6,0,0,0,4,0
288 };
289
291 const int domino3[] =
292 { // width*height of the board
293 8,7,
294 // the board itself
295 3,0,2,3,3,4,4,3,
296 6,5,3,4,2,0,2,1,
297 6,5,1,2,3,0,2,0,
298 4,5,4,1,6,6,2,5,
299 4,3,6,1,0,4,5,5,
300 1,3,2,5,6,0,0,1,
301 0,5,4,6,2,1,6,1
302 };
303
305 const int domino4[] =
306 { // width*height of the board
307 8,7,
308 // the board itself
309 4,1,5,2,4,4,6,2,
310 2,5,6,1,4,6,0,2,
311 6,5,1,1,0,1,4,3,
312 6,2,1,1,3,2,0,6,
313 3,6,3,3,5,5,0,5,
314 3,0,1,0,0,5,4,3,
315 3,2,4,5,4,2,6,0
316 };
317
319 const int domino5[] =
320 { // width*height of the board
321 8,7,
322 // the board itself
323 4,1,2,1,0,2,4,4,
324 5,5,6,6,0,4,6,3,
325 6,0,5,1,1,0,5,3,
326 3,4,2,2,0,3,1,2,
327 3,6,5,6,1,2,3,2,
328 2,5,0,6,6,3,3,5,
329 4,1,0,0,4,1,4,5
330 };
331
333 const int *specs[] =
334 {domino0,domino1,domino2,domino3,domino4,domino5};
336 const unsigned n_examples = sizeof(specs)/sizeof(int*);
338
339}
340
341// STATISTICS: example-any
Node * x
Pointer to corresponding Boolean expression node.
Example: Solitaire domino
Definition domino.cpp:68
int main(int argc, char *argv[])
Main-function.
Definition domino.cpp:223
virtual Space * copy(void)
Copy space during cloning.
Definition domino.cpp:212
const unsigned int n_examples
Number of board specifications.
Definition domino.cpp:53
Domino(Domino &s)
Constructor for cloning s.
Definition domino.cpp:206
virtual void print(std::ostream &os) const
Print solution.
Definition domino.cpp:193
@ PROP_EXTENSIONAL
Use extensional constraints.
Definition domino.cpp:84
@ PROP_ELEMENT
Use element constraints.
Definition domino.cpp:83
Domino(const SizeOptions &opt)
Actual model.
Definition domino.cpp:88
const int * specs[]
Board specifications.
Definition domino.cpp:48
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
Passing integer arguments.
Definition int.hh:628
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:656
Integer variable array.
Definition int.hh:763
Integer variables.
Definition int.hh:371
Regular expressions over integer values.
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_LE
Less ( )
Definition int.hh:929
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55