main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:07 for Gecode by
doxygen
1.8.4
test
nogoods.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
*
6
* Contributing authors:
7
* Guido Tack <tack@gecode.org>
8
*
9
* Copyright:
10
* Christian Schulte, 2013
11
* Guido Tack, 2004
12
*
13
* Last modified:
14
* $Date: 2013-07-09 12:19:11 +0200 (Tue, 09 Jul 2013) $ by $Author: schulte $
15
* $Revision: 13831 $
16
*
17
* This file is part of Gecode, the generic constraint
18
* development environment:
19
* http://www.gecode.org
20
*
21
* Permission is hereby granted, free of charge, to any person obtaining
22
* a copy of this software and associated documentation files (the
23
* "Software"), to deal in the Software without restriction, including
24
* without limitation the rights to use, copy, modify, merge, publish,
25
* distribute, sublicense, and/or sell copies of the Software, and to
26
* permit persons to whom the Software is furnished to do so, subject to
27
* the following conditions:
28
*
29
* The above copyright notice and this permission notice shall be
30
* included in all copies or substantial portions of the Software.
31
*
32
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39
*
40
*/
41
42
#include <
gecode/minimodel.hh
>
43
#include <
gecode/search.hh
>
44
45
#include "
test/test.hh
"
46
47
namespace
Test {
48
50
namespace
NoGoods
{
51
52
using namespace
Gecode;
53
55
void
dummy
(
Space
& home) {
56
}
57
59
class
Queens
:
public
Space
{
60
public
:
62
const
static
int
n
= 18;
64
IntVarArray
q
;
66
Queens
(
IntValBranch
ivb,
bool
assign
,
bool
null)
67
: q(*this,
n
,0,
n
-1) {
68
distinct
(*
this
,
IntArgs::create
(
n
,0,1), q,
ICL_VAL
);
69
distinct
(*
this
,
IntArgs::create
(
n
,0,-1), q,
ICL_VAL
);
70
distinct
(*
this
, q,
ICL_VAL
);
71
if
(assign) {
72
IntVar
x
(*
this
,0,1);
Gecode::assign
(*
this
, x,
INT_ASSIGN_MIN
());
73
}
74
{
75
IntVarArgs
q1(
n
/2), q2(
n
/2);
76
for
(
int
i
=0;
i
<
n
/2;
i
++) {
77
q1[
i
] = q[
i
]; q2[
i
] = q[
n
/2 +
i
];
78
}
79
branch
(*
this
, q1,
INT_VAR_NONE
(), ivb);
80
if
(null)
81
branch
(*
this
, &
dummy
);
82
branch
(*
this
, q2,
INT_VAR_NONE
(), ivb);
83
}
84
if
(assign) {
85
IntVar
x
(*
this
,0,1);
Gecode::assign
(*
this
, x,
INT_ASSIGN_MIN
());
86
}
87
}
89
Queens
(
bool
share,
Queens
& s) :
Space
(share,s) {
90
q.update(*
this
, share, s.
q
);
91
}
93
virtual
Space
*
copy
(
bool
share) {
94
return
new
Queens
(share,*
this
);
95
}
97
bool
same
(
const
Queens
& s)
const
{
98
for
(
int
i
=0;
i
<q.
size
();
i
++)
99
if
(q[
i
].val() != s.
q
[
i
].val())
100
return
false
;
101
return
true
;
102
}
104
static
unsigned
int
nodeinc
(
void
) {
105
return
500;
106
}
108
static
std::string
name
(
void
) {
109
return
"Queens"
;
110
}
112
static
std::string
val
(
IntValBranch
ivb) {
113
switch
(ivb.
select
()) {
114
case
IntValBranch::SEL_MIN
:
return
"INT_VAL_MIN"
;
115
case
IntValBranch::SEL_MAX
:
return
"INT_VAL_MAX"
;
116
case
IntValBranch::SEL_SPLIT_MIN
:
return
"INT_VAL_SPLIT_MIN"
;
117
case
IntValBranch::SEL_SPLIT_MAX
:
return
"INT_VAL_SPLIT_MAX"
;
118
case
IntValBranch::SEL_VALUES_MIN
:
return
"INT_VALUES_MIN"
;
119
case
IntValBranch::SEL_VALUES_MAX
:
return
"INT_VALUES_MAX"
;
120
default
:
GECODE_NEVER
;
121
}
122
return
""
;
123
}
124
};
125
126
#ifdef GECODE_HAS_SET_VARS
127
class
Hamming
:
public
Space
{
129
private
:
131
static
const
int
size
= 16;
133
static
const
int
distance = 4;
135
static
const
int
bits = 8;
137
SetVarArray
x
;
138
public
:
140
Hamming
(
SetValBranch
svb,
bool
assign
,
bool
null) :
141
x
(*this,
size
,
IntSet
::empty,1,bits) {
142
SetVarArgs
cx(
x
.size());
143
for
(
int
i
=
x
.size();
i
--;)
144
cx[
i
] =
expr
(*
this
, -
x
[
i
]);
145
146
for
(
int
i=0; i<
x
.size(); i++)
147
for
(
int
j=i+1; j<
x
.size(); j++)
148
rel
(*
this
,
149
cardinality
(
x
[j] & cx[i]) +
150
cardinality
(
x
[i] & cx[j]) >= distance);
151
152
if
(assign) {
153
IntVar
x
(*
this
,0,1);
Gecode::assign
(*
this
, x,
INT_ASSIGN_MIN
());
154
}
155
{
156
SetVarArgs
x1(
size
/2), x2(
size
/2);
157
for
(
int
i=0; i<
size
/2; i++) {
158
x1[
i
] =
x
[
i
]; x2[
i
] =
x
[
size
/2 +
i
];
159
}
160
branch
(*
this
, x1,
SET_VAR_NONE
(), svb);
161
if
(null)
162
branch
(*
this
, &
dummy
);
163
branch
(*
this
, x2,
SET_VAR_NONE
(), svb);
164
}
165
if
(assign) {
166
IntVar
x
(*
this
,0,1);
Gecode::assign
(*
this
, x,
INT_ASSIGN_MIN
());
167
}
168
}
170
Hamming
(
bool
share,
Hamming
& s) :
Space
(share,s) {
171
x
.update(*
this
, share, s.x);
172
}
174
virtual
Space
*
copy
(
bool
share) {
175
return
new
Hamming
(share,*
this
);
176
}
178
bool
same
(
const
Hamming
& s)
const
{
179
for
(
int
i
=0;
i
<
x
.size();
i
++) {
180
SetVarGlbRanges
a
(
x
[
i
]),
b
(s.x[i]);
181
if
(!
Iter::Ranges::equal
(
a
,b))
182
return
false
;
183
}
184
return
true
;
185
}
187
static
unsigned
int
nodeinc
(
void
) {
188
return
35;
189
}
191
static
std::string
name
(
void
) {
192
return
"Hamming"
;
193
}
195
static
std::string
val
(
SetValBranch
svb) {
196
switch
(svb.
select
()) {
197
case
SetValBranch::SEL_MIN_INC
:
return
"SET_VAL_MIN_INC"
;
198
case
SetValBranch::SEL_MAX_INC
:
return
"SET_VAL_MAX_INC"
;
199
case
SetValBranch::SEL_MIN_EXC
:
return
"SET_VAL_MIN_EXC"
;
200
case
SetValBranch::SEL_MAX_EXC
:
return
"SET_VAL_MAX_EXC"
;
201
default
:
GECODE_NEVER
;
202
}
203
return
""
;
204
}
205
};
206
#endif
207
209
template
<
class
Model,
class
ValBranch>
210
class
NoGoods
:
public
Base
{
211
protected
:
213
ValBranch
vb
;
215
unsigned
int
t
;
217
bool
a
;
219
bool
n
;
220
public
:
222
static
std::string
str
(
unsigned
int
i
) {
223
std::stringstream s;
224
s <<
i
;
225
return
s.str();
226
}
228
NoGoods
(
ValBranch
vb0,
unsigned
int
t0,
bool
a0,
bool
n0)
229
:
Base
(
"NoGoods::"
+Model::name()+
"::"
+Model::val(vb0)+
"::"
+str(t0)+
230
"::"
+(a0 ?
"+"
:
"-"
)+
"::"
+(n0 ?
"+"
:
"-"
)),
231
vb(vb0),
t
(t0),
a
(a0),
n
(n0) {}
233
virtual
bool
run
(
void
) {
234
Model* m =
new
Model(vb,
a
,
n
);
235
// Solution without no-goods
236
Model* s_plain =
dfs
(m);
237
// Stop and re-start for a while to collect no-goods
238
{
239
Search::NodeStop
ns(Model::nodeinc());
240
Search::Options
o;
241
o.
stop
= &ns;
242
o.
threads
=
t
;
243
o.
nogoods_limit
= 256U;
244
DFS<Model>
e(m,o);
245
while
(
true
) {
246
Model* s = e.
next
();
247
delete
s;
248
if
(!e.
stopped
())
249
break
;
250
// Add no-goods
251
e.
nogoods
().
post
(*m);
252
ns.
limit
(ns.
limit
()+Model::nodeinc());
253
}
254
}
255
// Compare whether the a or the same solution is found with no-goods
256
Model* s_nogoods =
dfs
(m);
257
258
bool
ok = ((s_nogoods != NULL) &&
259
((
t
!= 1) || s_plain->same(*s_nogoods)));
260
261
delete
m;
262
delete
s_nogoods;
263
delete
s_plain;
264
265
return
ok;
266
}
267
};
268
269
271
class
Create
{
272
public
:
274
Create
(
void
) {
275
bool
a
=
false
;
276
do
{
277
bool
n
=
false
;
278
do
{
279
for
(
unsigned
int
t
= 1;
t
<=4;
t
++) {
280
(void)
new
NoGoods<Queens,IntValBranch>
(
INT_VAL_MIN
(),
t
,
a
,
n
);
281
(void)
new
NoGoods<Queens,IntValBranch>
(
INT_VAL_MAX
(),
t
,
a
,
n
);
282
(void)
new
NoGoods<Queens,IntValBranch>
(
INT_VAL_SPLIT_MIN
(),
t
,
a
,
n
);
283
(void)
new
NoGoods<Queens,IntValBranch>
(
INT_VAL_SPLIT_MAX
(),
t
,
a
,
n
);
284
(void)
new
NoGoods<Queens,IntValBranch>
(
INT_VALUES_MIN
(),
t
,
a
,
n
);
285
(void)
new
NoGoods<Queens,IntValBranch>
(
INT_VALUES_MAX
(),
t
,
a
,
n
);
286
#ifdef GECODE_HAS_SET_VARS
287
(void)
new
NoGoods<Hamming,SetValBranch>
(
SET_VAL_MIN_INC
(),
t
,
a
,
n
);
288
(void)
new
NoGoods<Hamming,SetValBranch>
(
SET_VAL_MIN_EXC
(),
t
,
a
,
n
);
289
(void)
new
NoGoods<Hamming,SetValBranch>
(
SET_VAL_MAX_INC
(),
t
,
a
,
n
);
290
(void)
new
NoGoods<Hamming,SetValBranch>
(
SET_VAL_MAX_EXC
(),
t
,
a
,
n
);
291
#endif
292
}
293
n = !
n
;
294
}
while
(n);
295
a = !
a
;
296
}
while
(a);
297
}
298
};
299
300
Create
c
;
301
}
302
303
}
304
305
// STATISTICS: test-search