Generated on Sun Aug 26 2012 08:42:32 for Gecode by doxygen 1.8.1.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: 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 
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;
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