Generated on Sat Feb 7 2015 02:01:11 for Gecode by doxygen 1.8.9.1
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: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
15  * $Revision: 13820 $
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 
54 public:
55  int k, n;
56  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;
88 
89 public:
91  enum {
94  PROP_EXTENSIONAL_CHANNEL
95  };
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 
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);
199  "reified");
201  "extensional");
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 
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: arithmetic.cpp:218
void propagation(int v)
Set default propagation value.
Definition: options.hpp:181
int n
Problem parameters.
Regular expressions over integer values.
Definition: minimodel.hh:1401
LangfordNumber(bool share, LangfordNumber &l)
Constructor for cloning l.
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:212
Integer variable array.
Definition: int.hh:741
Computation spaces.
Definition: core.hpp:1362
Use extensional constraints.
Parametric base-class for scripts.
Definition: driver.hh:622
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Options taking two additional parameters.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Options opt
The options.
Definition: test.cpp:101
int main(int argc, char *argv[])
Main-function.
virtual Space * copy(bool share)
Copy during cloning.
Example: Langford's number problem
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Use reified constraints.
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:181
Less ( )
Definition: int.hh:907
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntConLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
Passing integer variables.
Definition: int.hh:636
virtual void print(std::ostream &os) const
Print solution.
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:331
const int v[7]
Definition: distinct.cpp:207
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition: extensional.cpp:45
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:78
Use extensional and channel constraints.
LangfordNumber(const LangfordNumberOptions &opt)
Construct model.
IntVarArray y
Sequence variables.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
virtual void help(void)
Print help message.
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
Matrix-interface for arrays.
Definition: minimodel.hh:1924
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:187
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
Options for scripts
Definition: driver.hh:326
void icl(IntConLevel i)
Set default integer consistency level.
Definition: options.hpp:194
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Domain propagation or consistency.
Definition: int.hh:940
virtual void help(void)
Print help text.
Definition: options.cpp:284