main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Mar 13 2014 04:39:27 for Gecode by
doxygen
1.8.1.2
examples
langford-number.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5
* Mikael Lagerkvist <lagerkvist@gecode.org>
6
* Christian Schulte <schulte@gecode.org>
7
*
8
* Copyright:
9
* Patrick Pekczynski, 2004
10
* Mikael Lagerkvist, 2006
11
* Christian Schulte, 2007
12
*
13
* Last modified:
14
* $Date: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
15
* $Revision: 11473 $
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/driver.hh
>
43
#include <
gecode/int.hh
>
44
#include <
gecode/minimodel.hh
>
45
46
using namespace
Gecode;
47
53
class
LangfordNumberOptions
:
public
Options
{
54
public
:
55
int
k,
n
;
56
57
LangfordNumberOptions
(
const
char
* s,
int
k0,
int
n0)
58
:
Options
(s), k(k0), n(n0) {}
60
void
parse
(
int
& argc,
char
* argv[]) {
61
Options::parse
(argc,argv);
62
if
(argc < 3)
63
return
;
64
n = atoi(argv[1]);
65
k = atoi(argv[2]);
66
}
68
virtual
void
help
(
void
) {
69
Options::help
();
70
std::cerr <<
"\t(unsigned int) default: "
<< n << std::endl
71
<<
"\t\tparameter n"
<< std::endl
72
<<
"\t(unsigned int) default: "
<< k << std::endl
73
<<
"\t\tparameter k"
<< std::endl;
74
}
75
};
76
84
class
LangfordNumber
:
public
Script
{
85
protected
:
86
int
k,
n
;
87
IntVarArray
y
;
88
89
public
:
91
enum
{
92
PROP_REIFIED
,
93
PROP_EXTENSIONAL
,
94
PROP_EXTENSIONAL_CHANNEL
95
};
97
LangfordNumber
(
const
LangfordNumberOptions
&
opt
)
98
: k(opt.k), n(opt.n), y(*this,k*n,1,n) {
99
100
switch
(opt.
propagation
()) {
101
case
PROP_REIFIED:
102
{
103
// Position of values in sequence
104
IntVarArgs
pv(*
this
,k*n,0,k*n-1);
105
Matrix<IntVarArgs>
p(pv,n,k);
106
107
/*
108
* The occurences of v in the Langford sequence are v numbers apart.
109
*
110
* Let \#(i, v) denote the position of the i-th occurence of
111
* value v in the Langford Sequence. Then
112
*
113
* \f$ \forall i, j \in \{1, \dots, k\}, i \neq j:
114
* \forall v \in \{1, \dots, n\}: \#(i, v) + (v + 1) = \#(j, v)\f$
115
*
116
*/
117
for
(
int
i
=0;
i
<n;
i
++)
118
for
(
int
j=0; j<k-1; j++)
119
rel
(*
this
, p(
i
,j)+
i
+2 == p(
i
,j+1));
120
121
distinct
(*
this
, pv, opt.
icl
());
122
123
// Channel positions <-> values
124
for
(
int
i
=0;
i
<n;
i
++)
125
for
(
int
j=0; j<k; j++)
126
element
(*
this
, y, p(
i
,j),
i
+1);
127
}
128
break
;
129
case
PROP_EXTENSIONAL:
130
{
131
IntArgs
a
(n-1);
132
for
(
int
v
=2;
v
<=n;
v
++)
133
a[
v
-2]=
v
;
134
for
(
int
v
=1;
v
<=n;
v
++) {
135
// Construct regular expression for all symbols but v
136
if
(
v
> 1)
137
a[
v
-2]=
v
-1;
138
REG
ra
(a), rv(
v
);
139
extensional
(*
this
, y, *
ra
+rv+(
ra
(
v
,
v
)+rv)(k-1,k-1)+*
ra
);
140
}
141
}
142
break
;
143
case
PROP_EXTENSIONAL_CHANNEL:
144
{
145
// Boolean variables for channeling
146
BoolVarArgs
bv(*
this
,k*n*n,0,1);
147
Matrix<BoolVarArgs>
b
(bv,k*n,n);
148
149
// Post channel constraints
150
for
(
int
i
=0;
i
<n*k;
i
++)
151
channel
(*
this
, b.
col
(
i
), y[
i
], 1);
152
153
// For placing two numbers three steps apart, we construct the
154
// regular expression 0*100010*, and apply it to the projection of
155
// the sequence on the value.
156
REG
r0(0), r1(1);
157
for
(
int
v
=1;
v
<=n;
v
++)
158
extensional
(*
this
, b.
row
(
v
-1),
159
*r0 + r1 + (r0(
v
,
v
) + r1)(k-1,k-1) + *r0);
160
}
161
break
;
162
}
163
164
// Symmetry breaking
165
rel
(*
this
, y[0],
IRT_LE
, y[n*k-1]);
166
167
// Branching
168
branch
(*
this
, y,
INT_VAR_SIZE_MIN
,
INT_VAL_MAX
);
169
}
170
172
virtual
void
print
(std::ostream& os)
const
{
173
os <<
"\t"
<< y << std::endl;
174
}
175
177
LangfordNumber
(
bool
share,
LangfordNumber
& l)
178
:
Script
(share, l), k(l.k), n(l.n) {
179
y.update(*
this
, share, l.
y
);
180
181
}
183
virtual
Space
*
184
copy
(
bool
share) {
185
return
new
LangfordNumber
(share, *
this
);
186
}
187
};
188
189
193
int
194
main
(
int
argc,
char
* argv[]) {
195
LangfordNumberOptions
opt
(
"Langford Numbers"
,3,9);
196
opt.
icl
(
ICL_DOM
);
197
opt.
propagation
(
LangfordNumber::PROP_EXTENSIONAL_CHANNEL
);
198
opt.
propagation
(
LangfordNumber::PROP_REIFIED
,
199
"reified"
);
200
opt.
propagation
(
LangfordNumber::PROP_EXTENSIONAL
,
201
"extensional"
);
202
opt.
propagation
(
LangfordNumber::PROP_EXTENSIONAL_CHANNEL
,
203
"extensional-channel"
);
204
opt.
parse
(argc, argv);
205
if
(opt.
k
< 1) {
206
std::cerr <<
"k must be at least 1!"
<< std::endl;
207
return
1;
208
}
209
if
(opt.
k
> opt.
n
) {
210
std::cerr <<
"n must be at least k!"
<< std::endl;
211
return
1;
212
}
213
Script::run<LangfordNumber,DFS,LangfordNumberOptions>(
opt
);
214
return
0;
215
}
216
217
// STATISTICS: example-any
218