Generated on Sun Mar 19 2017 08:30:25 for Gecode by doxygen 1.8.13
perfect-square.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Mikael Lagerkvist <lagerkvist@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2003
9  * Mikael Lagerkvist, 2005
10  *
11  * Last modified:
12  * $Date: 2015-03-17 16:09:39 +0100 (Tue, 17 Mar 2015) $ by $Author: schulte $
13  * $Revision: 14447 $
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 
60 //@
61 const int s00[] = {
62  21, 112,
63  50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2
64 };
65 const int s01[] = {
66  22, 110,
67  60,50,28,27,26,24,23,22,21,18,17,16,15,14,13,12,8,7,6,4,3,2
68 };
69 const int s02[] = {
70  22, 192,
71  86,71,62,59,57,49,47,41,37,36,35,31,28,26,19,17,14,12,10,9,8,4
72 };
73 const int s03[] = {
74  23, 110,
75  44,41,38,37,32,31,29,28,21,19,16,15,14,13,12,10,8,7,5,4,3,2,1
76 };
77 const int s04[] = {
78  23, 332,
79  129,123,120,112,91,89,83,68,58,56,53,50,49,48,47,38,31,30,26,24,17,15,1
80 };
81 const int s05[] = {
82  24, 120,
83  47,46,41,40,34,33,32,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
84 };
85 const int s06[] = {
86  24, 479,
87  175,174,164,160,155,150,140,130,86,77,68,60,52,44,43,35,29,28,26,24,23,17,6,5
88 };
89 const int s07[] = {
90  25, 147,
91  74,73,41,40,34,33,32,27,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
92 };
93 const int s08[] = {
94  25, 661,
95  262,248,238,210,203,196,175,161,111,106,102,84,83,77,73,64,41,38,36,31,23,18,17,7,5
96 };
97 const int s09[] = {
98  26, 212,
99  99,85,65,62,57,56,55,48,39,38,32,28,26,24,23,20,19,17,16,12,7,6,5,4,2,1
100 };
101 const int s10[] = {
102  26, 214,
103  86,72,67,64,61,56,55,44,43,39,36,35,34,32,30,29,27,26,23,20,19,10,9,8,6,5
104 };
105 const int s11[] = {
106  26, 825,
107  304,302,288,277,246,235,233,189,157,135,127,117,109,92,90,83,81,76,57,53,49,37,26,25,8,5
108 };
109 const int s12[] = {
110  27, 180,
111  89,56,51,50,48,43,41,40,39,36,34,31,29,25,23,21,19,16,15,13,12,10,9,7,6,4,1
112 };
113 const int s13[] = {
114  27, 1179,
115  484,440,387,379,360,352,316,308,198,194,168,149,145,119,114,108,82,80,69,66,63,50,42,35,29,24,18
116 };
117 const int s14[] = {
118  28, 201,
119  77,70,68,67,64,56,54,39,38,36,34,32,30,24,22,21,18,17,16,13,12,11,10,6,4,3,2,1
120 };
121 const int s15[] = {
122  28, 1544,
123  649,615,510,473,456,439,419,385,260,216,214,208,203,175,147,135,125,116,104,94,81,55,49,17,12,7,6,4
124 };
125 const int s16[] = {
126  29, 255,
127  112,107,84,75,68,64,59,51,49,43,37,36,31,29,28,27,26,25,24,22,17,15,13,11,8,7,6,2,1
128 };
129 const int s17[] = {
130  29, 2134,
131  855,769,761,717,648,604,562,518,338,293,292,286,265,226,224,204,186,179,174,165,161,109,100,91,69,45,43,17,9
132 };
133 const int s18[] = {
134  30, 237,
135  88,82,79,76,73,56,53,46,45,43,40,39,36,34,33,32,29,27,25,24,23,21,20,16,11,10,9,5,3,1
136 };
137 const int s19[] = {
138  30, 2710,
139  992,981,948,936,826,782,781,737,465,440,418,289,272,264,260,242,227,210,208,154,140,124,122,108,92,64,29,16,15,4
140 };
141 const int s20[] = {
142  40, 510,
143  219,173,156,135,134,128,124,118,114,95,81,79,71,65,63,59,58,55,54,51,49,46,34,33,32,31,28,24,21,20,19,18,17,16,14,10,8,4,3,1
144 };
145 const int s21[] = {
146  40, 1121,
147  409,408,396,345,317,316,242,238,221,198,166,159,157,143,130,123,120,117,109,102,101,93,87,79,76,67,64,55,53,49,46,44,39,33,21,19,14,13,5,3
148 };
149 const int s22[] = {
150  50, 788,
151  301,300,246,242,187,182,177,168,145,139,135,128,114,110,103,93,87,84,82,81,79,73,69,63,58,57,52,51,49,47,41,40,34,33,26,23,22,21,20,19,18,15,13,11,10,9,8,7,4,2
152 };
153 const int s23[] = {
154  50, 1034,
155  588,446,305,283,175,163,160,138,132,130,128,124,120,116,110,107,106,103,101,100,94,86,85,82,80,77,74,64,63,62,61,60,57,54,47,46,45,43,40,39,32,30,28,27,26,25,22,7,6,1
156 };
157 const int s24[] = {
158  60, 1097,
159  645,452,268,264,204,188,184,176,172,165,161,143,132,127,116,114,108,104,100,94,92,90,88,84,75,74,72,71,69,68,67,64,62,61,56,51,46,36,34,30,29,28,26,25,21,20,19,18,17,16,15,14,12,10,9,7,5,4,2,1
160 };
161 const int s25[] = {
162  60, 1192,
163  638,554,335,303,285,271,219,180,174,159,149,148,136,125,110,98,94,85,77,76,75,74,72,71,69,65,63,62,61,60,59,57,55,51,50,49,48,47,46,45,44,43,40,39,37,35,32,31,25,16,15,14,12,10,9,8,6,4,2,1
164 };
165 const int s26[] = {
166  75, 1412,
167  793,619,473,320,287,207,188,181,179,170,167,153,151,149,142,140,132,127,121,117,116,106,105,103,97,93,92,91,90,87,84,83,82,76,74,73,72,71,70,69,67,66,65,64,63,61,54,53,49,45,39,38,35,34,33,32,30,29,28,27,26,24,21,20,19,18,15,14,13,11,10,9,6,5,3
168 };
169 
170 
171 const int* specs[] = {
172  &s00[0],&s01[0],&s02[0],&s03[0],&s04[0],
173  &s05[0],&s06[0],&s07[0],&s08[0],&s09[0],
174  &s10[0],&s11[0],&s12[0],&s13[0],&s14[0],
175  &s15[0],&s16[0],&s17[0],&s18[0],&s19[0],
176  &s20[0],&s21[0],&s22[0],&s23[0],&s24[0],
177  &s25[0],&s26[0]
178 };
179 const unsigned int n_specs = sizeof(specs) / sizeof(int*);
181 
189 class PerfectSquare : public Script {
190 protected:
195 public:
197  enum {
199  PROP_CUMULATIVES
200  };
203  : Script(opt),
204  x(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1),
205  y(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1) {
206 
207  const int* s = specs[opt.size()];
208  int n = *s++;
209  int w = *s++;
210 
211  // Restrict position according to square size
212  for (int i=n; i--; ) {
213  rel(*this, x[i], IRT_LQ, w-s[i]);
214  rel(*this, y[i], IRT_LQ, w-s[i]);
215  }
216 
217  IntArgs sa(n,s);
218 
219  // Squares do not overlap
220  nooverlap(*this, x, sa, y, sa);
221 
222  /*
223  * Capacity constraints
224  *
225  */
226  switch (opt.propagation()) {
227  case PROP_REIFIED:
228  {
229  for (int cx=0; cx<w; cx++) {
230  BoolVarArgs bx(*this,n,0,1);
231  for (int i=0; i<n; i++)
232  dom(*this, x[i], cx-s[i]+1, cx, bx[i]);
233  linear(*this, sa, bx, IRT_EQ, w);
234  }
235  for (int cy=0; cy<w; cy++) {
236  BoolVarArgs by(*this,n,0,1);
237  for (int i=0; i<n; i++)
238  dom(*this, y[i], cy-s[i]+1, cy, by[i]);
239  linear(*this, sa, by, IRT_EQ, w);
240  }
241  }
242  break;
243  case PROP_CUMULATIVES:
244  {
245  IntArgs m(n), dh(n);
246  for (int i = n; i--; ) {
247  m[i]=0; dh[i]=s[i];
248  }
249  IntArgs limit(1, w);
250  {
251  // x-direction
252  IntVarArgs e(n);
253  for (int i=n; i--;)
254  e[i]=expr(*this, x[i]+dh[i]);
255  cumulatives(*this, m, x, dh, e, dh, limit, true);
256  cumulatives(*this, m, x, dh, e, dh, limit, false);
257  }
258  {
259  // y-direction
260  IntVarArgs e(n);
261  for (int i=n; i--;)
262  e[i]=expr(*this, y[i]+dh[i]);
263  cumulatives(*this, m, y, dh, e, dh, limit, true);
264  cumulatives(*this, m, y, dh, e, dh, limit, false);
265  }
266  }
267  break;
268  default:
269  GECODE_NEVER;
270  }
271 
272  branch(*this, x, INT_VAR_MIN_MIN(), INT_VAL_MIN());
273  branch(*this, y, INT_VAR_MIN_MIN(), INT_VAL_MIN());
274  }
275 
277  PerfectSquare(bool share, PerfectSquare& s) : Script(share,s) {
278  x.update(*this, share, s.x);
279  y.update(*this, share, s.y);
280  }
282  virtual Space*
283  copy(bool share) {
284  return new PerfectSquare(share,*this);
285  }
287  virtual void
288  print(std::ostream& os) const {
289  os << "\t";
290  for (int i=0; i<x.size(); i++)
291  os << "(" << x[i] << "," << y[i] << ") ";
292  os << std::endl;
293  }
294 };
295 
299 int
300 main(int argc, char* argv[]) {
301  SizeOptions opt("PerfectSquare");
304  opt.propagation(PerfectSquare::PROP_CUMULATIVES, "cumulatives");
305  opt.a_d(5);
306  opt.c_d(20);
307  opt.parse(argc,argv);
308  if (opt.size() >= n_specs) {
309  std::cerr << "Error: size must be between 0 and " << n_specs - 1
310  << std::endl;
311  return 1;
312  }
313  Script::run<PerfectSquare,DFS,SizeOptions>(opt);
314  return 0;
315 }
316 
317 // STATISTICS: example-any
318 
void size(unsigned int s)
Set default size.
Definition: options.hpp:485
Options for scripts with additional size parameter
Definition: driver.hh:579
Example: Packing squares into a rectangle
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
void propagation(int v)
Set default propagation value.
Definition: options.hpp:181
void c_d(unsigned int d)
Set default copy recomputation distance.
Definition: options.hpp:279
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:437
Less or equal ( )
Definition: int.hh:906
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:192
Integer variable array.
Definition: int.hh:741
virtual Space * copy(bool share)
Copy during cloning.
Computation spaces.
Definition: core.hpp:1362
Parametric base-class for scripts.
Definition: driver.hh:633
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
void a_d(unsigned int d)
Set default adaptive recomputation distance.
Definition: options.hpp:288
Gecode::IntArgs i(4, 1, 2, 3, 4)
PerfectSquare(const SizeOptions &opt)
Actual model.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
Options opt
The options.
Definition: test.cpp:101
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.
int main(int argc, char *argv[])
Main-function.
void cumulatives(Home home, const IntVarArgs &m, const IntVarArgs &s, const IntVarArgs &p, const IntVarArgs &e, const IntVarArgs &u, const IntArgs &c, bool at_most, IntConLevel cl)
Post propagators for the cumulatives constraint.
Use cumulatives constraint.
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
Use reified constraints.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
IntVarArray x
Array of x-coordinates of squares.
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntConLevel)
Post propagator for rectangle packing.
Definition: no-overlap.cpp:55
Gecode toplevel namespace
virtual void print(std::ostream &os) const
Print solution.
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
PerfectSquare(bool share, PerfectSquare &s)
Constructor for cloning s.
IntVarArray y
Array of y-coordinates of squares.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60