main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Feb 11 2025 17:33:26 for Gecode by
doxygen
1.12.0
examples
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
* 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
56
//@
57
const
int
s00[] = {
58
21, 112,
59
50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2
60
};
61
const
int
s01[] = {
62
22, 110,
63
60,50,28,27,26,24,23,22,21,18,17,16,15,14,13,12,8,7,6,4,3,2
64
};
65
const
int
s02[] = {
66
22, 192,
67
86,71,62,59,57,49,47,41,37,36,35,31,28,26,19,17,14,12,10,9,8,4
68
};
69
const
int
s03[] = {
70
23, 110,
71
44,41,38,37,32,31,29,28,21,19,16,15,14,13,12,10,8,7,5,4,3,2,1
72
};
73
const
int
s04[] = {
74
23, 332,
75
129,123,120,112,91,89,83,68,58,56,53,50,49,48,47,38,31,30,26,24,17,15,1
76
};
77
const
int
s05[] = {
78
24, 120,
79
47,46,41,40,34,33,32,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
80
};
81
const
int
s06[] = {
82
24, 479,
83
175,174,164,160,155,150,140,130,86,77,68,60,52,44,43,35,29,28,26,24,23,17,6,5
84
};
85
const
int
s07[] = {
86
25, 147,
87
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
88
};
89
const
int
s08[] = {
90
25, 661,
91
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
92
};
93
const
int
s09[] = {
94
26, 212,
95
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
96
};
97
const
int
s10[] = {
98
26, 214,
99
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
100
};
101
const
int
s11[] = {
102
26, 825,
103
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
104
};
105
const
int
s12[] = {
106
27, 180,
107
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
108
};
109
const
int
s13[] = {
110
27, 1179,
111
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
112
};
113
const
int
s14[] = {
114
28, 201,
115
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
116
};
117
const
int
s15[] = {
118
28, 1544,
119
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
120
};
121
const
int
s16[] = {
122
29, 255,
123
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
124
};
125
const
int
s17[] = {
126
29, 2134,
127
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
128
};
129
const
int
s18[] = {
130
30, 237,
131
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
132
};
133
const
int
s19[] = {
134
30, 2710,
135
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
136
};
137
const
int
s20[] = {
138
40, 510,
139
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
140
};
141
const
int
s21[] = {
142
40, 1121,
143
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
144
};
145
const
int
s22[] = {
146
50, 788,
147
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
148
};
149
const
int
s23[] = {
150
50, 1034,
151
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
152
};
153
const
int
s24[] = {
154
60, 1097,
155
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
156
};
157
const
int
s25[] = {
158
60, 1192,
159
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
160
};
161
const
int
s26[] = {
162
75, 1412,
163
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
164
};
165
166
167
const
int
* specs[] = {
168
&s00[0],&s01[0],&s02[0],&s03[0],&s04[0],
169
&s05[0],&s06[0],&s07[0],&s08[0],&s09[0],
170
&s10[0],&s11[0],&s12[0],&s13[0],&s14[0],
171
&s15[0],&s16[0],&s17[0],&s18[0],&s19[0],
172
&s20[0],&s21[0],&s22[0],&s23[0],&s24[0],
173
&s25[0],&s26[0]
174
};
175
const
unsigned
int
n_specs =
sizeof
(specs) /
sizeof
(
int
*);
177
185
class
PerfectSquare
:
public
Script
{
186
protected
:
188
IntVarArray
x
;
190
IntVarArray
y
;
191
public
:
193
enum
{
194
PROP_REIFIED
,
195
PROP_CUMULATIVES
196
};
198
PerfectSquare
(
const
SizeOptions
& opt)
199
:
Script
(opt),
200
x
(*this,
specs
[opt.size()][0],0,
specs
[opt.size()][1]-1),
201
y
(*this,
specs
[opt.size()][0],0,
specs
[opt.size()][1]-1) {
202
203
const
int
* s =
specs
[opt.size()];
204
int
n
= *s++;
205
int
w = *s++;
206
207
// Restrict position according to square size
208
for
(
int
i=0; i<
n
; i++) {
209
rel
(*
this
,
x
[i],
IRT_LQ
, w-s[i]);
210
rel
(*
this
,
y
[i],
IRT_LQ
, w-s[i]);
211
}
212
213
IntArgs
sa(
n
,s);
214
215
// Squares do not overlap
216
nooverlap
(*
this
,
x
, sa,
y
, sa);
217
218
/*
219
* Capacity constraints
220
*
221
*/
222
switch
(opt.propagation()) {
223
case
PROP_REIFIED
:
224
{
225
for
(
int
cx=0; cx<w; cx++) {
226
BoolVarArgs
bx(*
this
,
n
,0,1);
227
for
(
int
i=0; i<
n
; i++)
228
dom
(*
this
,
x
[i], cx-s[i]+1, cx, bx[i]);
229
linear
(*
this
, sa, bx,
IRT_EQ
, w);
230
}
231
for
(
int
cy=0; cy<w; cy++) {
232
BoolVarArgs
by(*
this
,
n
,0,1);
233
for
(
int
i=0; i<
n
; i++)
234
dom
(*
this
,
y
[i], cy-s[i]+1, cy, by[i]);
235
linear
(*
this
, sa, by,
IRT_EQ
, w);
236
}
237
}
238
break
;
239
case
PROP_CUMULATIVES
:
240
{
241
IntArgs
m(
n
), dh(
n
);
242
for
(
int
i=0; i<
n
; i++) {
243
m[i]=0; dh[i]=s[i];
244
}
245
IntArgs
limit({w});
246
{
247
// x-direction
248
IntVarArgs
e(
n
);
249
for
(
int
i=0; i<
n
; i++)
250
e[i]=
expr
(*
this
,
x
[i]+dh[i]);
251
cumulatives
(*
this
, m,
x
, dh, e, dh, limit,
true
);
252
cumulatives
(*
this
, m,
x
, dh, e, dh, limit,
false
);
253
}
254
{
255
// y-direction
256
IntVarArgs
e(
n
);
257
for
(
int
i=0; i<
n
; i++)
258
e[i]=
expr
(*
this
,
y
[i]+dh[i]);
259
cumulatives
(*
this
, m,
y
, dh, e, dh, limit,
true
);
260
cumulatives
(*
this
, m,
y
, dh, e, dh, limit,
false
);
261
}
262
}
263
break
;
264
default
:
265
GECODE_NEVER
;
266
}
267
268
branch
(*
this
,
x
,
INT_VAR_MIN_MIN
(),
INT_VAL_MIN
());
269
branch
(*
this
,
y
,
INT_VAR_MIN_MIN
(),
INT_VAL_MIN
());
270
}
271
273
PerfectSquare
(
PerfectSquare
& s) :
Script
(s) {
274
x
.
update
(*
this
, s.
x
);
275
y
.
update
(*
this
, s.
y
);
276
}
278
virtual
Space
*
279
copy
(
void
) {
280
return
new
PerfectSquare
(*
this
);
281
}
283
virtual
void
284
print
(std::ostream& os)
const
{
285
os <<
"\t"
;
286
for
(
int
i=0; i<
x
.
size
(); i++)
287
os <<
"("
<<
x
[i] <<
","
<<
y
[i] <<
") "
;
288
os << std::endl;
289
}
290
};
291
295
int
296
main
(
int
argc,
char
* argv[]) {
297
SizeOptions
opt(
"PerfectSquare"
);
298
opt.propagation(
PerfectSquare::PROP_REIFIED
);
299
opt.propagation(
PerfectSquare::PROP_REIFIED
,
"reified"
);
300
opt.propagation(
PerfectSquare::PROP_CUMULATIVES
,
"cumulatives"
);
301
opt.a_d(5);
302
opt.c_d(20);
303
opt.
parse
(argc,argv);
304
if
(opt.size() >= n_specs) {
305
std::cerr <<
"Error: size must be between 0 and "
<< n_specs - 1
306
<< std::endl;
307
return
1;
308
}
309
Script::run<PerfectSquare,DFS,SizeOptions>
(opt);
310
return
0;
311
}
312
313
// STATISTICS: example-any
314
n
int n
Number of negative literals for node type.
Definition
bool-expr.cpp:234
Gecode::BoolVarArgs
Passing Boolean variables.
Definition
int.hh:712
Gecode::Driver::ScriptBase
Parametric base-class for scripts.
Definition
driver.hh:729
Gecode::Driver::ScriptBase::run
static void run(const Options &opt, Script *s=NULL)
Definition
script.hpp:290
Gecode::IntArgs
Passing integer arguments.
Definition
int.hh:628
Gecode::IntVarArgs
Passing integer variables.
Definition
int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition
int.hh:763
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition
driver.hh:675
Gecode::Space
Computation spaces.
Definition
core.hpp:1742
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements)
Definition
array.hpp:926
Gecode::VarArray::update
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition
array.hpp:1013
PerfectSquare
Example: Packing squares into a rectangle
Definition
perfect-square.cpp:185
PerfectSquare::PROP_REIFIED
@ PROP_REIFIED
Use reified constraints.
Definition
perfect-square.cpp:194
PerfectSquare::PROP_CUMULATIVES
@ PROP_CUMULATIVES
Use cumulatives constraint.
Definition
perfect-square.cpp:195
PerfectSquare::print
virtual void print(std::ostream &os) const
Print solution.
Definition
perfect-square.cpp:284
PerfectSquare::main
int main(int argc, char *argv[])
Main-function.
Definition
perfect-square.cpp:296
PerfectSquare::x
IntVarArray x
Array of x-coordinates of squares.
Definition
perfect-square.cpp:188
PerfectSquare::specs
const int * specs[]
Main-function.
Definition
perfect-square.cpp:167
PerfectSquare::PerfectSquare
PerfectSquare(const SizeOptions &opt)
Actual model.
Definition
perfect-square.cpp:198
PerfectSquare::PerfectSquare
PerfectSquare(PerfectSquare &s)
Constructor for cloning s.
Definition
perfect-square.cpp:273
PerfectSquare::copy
virtual Space * copy(void)
Copy during cloning.
Definition
perfect-square.cpp:279
PerfectSquare::y
IntVarArray y
Array of y-coordinates of squares.
Definition
perfect-square.cpp:190
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition
test.cpp:120
driver.hh
int.hh
Gecode::branch
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
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition
linear.cpp:41
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition
rel.cpp:68
Gecode::nooverlap
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntPropLevel ipl=IPL_DEF)
Post propagator for rectangle packing.
Definition
no-overlap.cpp:51
Gecode::IRT_EQ
@ IRT_EQ
Equality ( )
Definition
int.hh:926
Gecode::IRT_LQ
@ IRT_LQ
Less or equal ( )
Definition
int.hh:928
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition
int-expr.cpp:915
Gecode::dom
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition
dom.cpp:40
Gecode::cumulatives
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, IntPropLevel ipl=IPL_DEF)
Post propagators for the cumulatives constraint.
Definition
cumulatives.cpp:110
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition
val.hpp:55
Gecode::INT_VAR_MIN_MIN
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Definition
var.hpp:186
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition
macros.hpp:56