Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/driver.hh>
39 #include <gecode/int.hh>
40 #include <gecode/minimodel.hh>
41 
42 using namespace Gecode;
43 
50 public:
51  int k, n;
52  LangfordNumberOptions(const char* s, int k0, int n0)
54  : Options(s), k(k0), n(n0) {}
56  void parse(int& argc, char* argv[]) {
57  Options::parse(argc,argv);
58  if (argc < 3)
59  return;
60  n = atoi(argv[1]);
61  k = atoi(argv[2]);
62  }
64  virtual void help(void) {
65  Options::help();
66  std::cerr << "\t(unsigned int) default: " << n << std::endl
67  << "\t\tparameter n" << std::endl
68  << "\t(unsigned int) default: " << k << std::endl
69  << "\t\tparameter k" << std::endl;
70  }
71 };
72 
80 class LangfordNumber : public Script {
81 protected:
82  int k, n;
84 
85 public:
87  enum {
90  PROP_EXTENSIONAL_CHANNEL
91  };
94  : Script(opt), k(opt.k), n(opt.n), y(*this,k*n,1,n) {
95 
96  switch (opt.propagation()) {
97  case PROP_REIFIED:
98  {
99  // Position of values in sequence
100  IntVarArgs pv(*this,k*n,0,k*n-1);
101  Matrix<IntVarArgs> p(pv,n,k);
102 
103  /*
104  * The occurences of v in the Langford sequence are v numbers apart.
105  *
106  * Let \#(i, v) denote the position of the i-th occurence of
107  * value v in the Langford Sequence. Then
108  *
109  * \f$ \forall i, j \in \{1, \dots, k\}, i \neq j:
110  * \forall v \in \{1, \dots, n\}: \#(i, v) + (v + 1) = \#(j, v)\f$
111  *
112  */
113  for (int i=0; i<n; i++)
114  for (int j=0; j<k-1; j++)
115  rel(*this, p(i,j)+i+2 == p(i,j+1));
116 
117  distinct(*this, pv, opt.ipl());
118 
119  // Channel positions <-> values
120  for (int i=0; i<n; i++)
121  for (int j=0; j<k; j++)
122  element(*this, y, p(i,j), i+1);
123  }
124  break;
125  case PROP_EXTENSIONAL:
126  {
127  IntArgs a(n-1);
128  for (int v=2; v<=n; v++)
129  a[v-2]=v;
130  for (int v=1; v<=n; v++) {
131  // Construct regular expression for all symbols but v
132  if (v > 1)
133  a[v-2]=v-1;
134  REG ra(a), rv(v);
135  extensional(*this, y, *ra+rv+(ra(v,v)+rv)(k-1,k-1)+*ra);
136  }
137  }
138  break;
139  case PROP_EXTENSIONAL_CHANNEL:
140  {
141  // Boolean variables for channeling
142  BoolVarArgs bv(*this,k*n*n,0,1);
143  Matrix<BoolVarArgs> b(bv,k*n,n);
144 
145  // Post channel constraints
146  for (int i=0; i<n*k; i++)
147  channel(*this, b.col(i), y[i], 1);
148 
149  // For placing two numbers three steps apart, we construct the
150  // regular expression 0*100010*, and apply it to the projection of
151  // the sequence on the value.
152  REG r0(0), r1(1);
153  for (int v=1; v<=n; v++)
154  extensional(*this, b.row(v-1),
155  *r0 + r1 + (r0(v,v) + r1)(k-1,k-1) + *r0);
156  }
157  break;
158  }
159 
160  // Symmetry breaking
161  rel(*this, y[0], IRT_LE, y[n*k-1]);
162 
163  // Branching
164  branch(*this, y, INT_VAR_SIZE_MIN(), INT_VAL_MAX());
165  }
166 
168  virtual void print(std::ostream& os) const {
169  os << "\t" << y << std::endl;
170  }
171 
174  : Script(l), k(l.k), n(l.n) {
175  y.update(*this, l.y);
176 
177  }
179  virtual Space*
180  copy(void) {
181  return new LangfordNumber(*this);
182  }
183 };
184 
185 
189 int
190 main(int argc, char* argv[]) {
191  LangfordNumberOptions opt("Langford Numbers",3,9);
192  opt.ipl(IPL_DOM);
195  "reified");
197  "extensional");
199  "extensional-channel");
200  opt.parse(argc, argv);
201  if (opt.k < 1) {
202  std::cerr << "k must be at least 1!" << std::endl;
203  return 1;
204  }
205  if (opt.k > opt.n) {
206  std::cerr << "n must be at least k!" << std::endl;
207  return 1;
208  }
209  Script::run<LangfordNumber,DFS,LangfordNumberOptions>(opt);
210  return 0;
211 }
212 
213 // STATISTICS: example-any
214 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Example: Langford's number problem
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void propagation(int v)
Set default propagation value.
Definition: options.hpp:203
int n
Passing integer variables.
Definition: int.hh:656
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:39
Less ( )
Definition: int.hh:929
LangfordNumber(LangfordNumber &l)
Constructor for cloning l.
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Computation spaces.
Definition: core.hpp:1742
void 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:39
Regular expressions over integer values.
Definition: minimodel.hh:1625
Integer variable array.
Definition: int.hh:763
virtual void print(std::ostream &os) const
Print solution.
Gecode toplevel namespace
int main(int argc, char *argv[])
Main-function.
Use extensional and channel constraints.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Options opt
The options.
Definition: test.cpp:97
Passing Boolean variables.
Definition: int.hh:712
Options for scripts
Definition: driver.hh:366
Parametric base-class for scripts.
Definition: driver.hh:729
virtual void help(void)
Print help message.
virtual Space * copy(void)
Copy during cloning.
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
Use extensional constraints.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Use reified constraints.
Matrix-interface for arrays.
Definition: minimodel.hh:2087
virtual void help(void)
Print help text.
Definition: options.cpp:494
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:206
const int v[7]
Definition: distinct.cpp:259
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
LangfordNumber(const LangfordNumberOptions &opt)
Construct model.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: channel.cpp:41
Options taking two additional parameters.
RegSimpleA ra
IntVarArray y
Sequence variables.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
int n
Problem parameters.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:65