langford-number.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * Mikael Lagerkvist <lagerkvist@gecode.org> 00006 * Christian Schulte <schulte@gecode.org> 00007 * 00008 * Copyright: 00009 * Patrick Pekczynski, 2004 00010 * Mikael Lagerkvist, 2006 00011 * Christian Schulte, 2007 00012 * 00013 * Last modified: 00014 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00015 * $Revision: 11473 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 #include <gecode/driver.hh> 00043 #include <gecode/int.hh> 00044 #include <gecode/minimodel.hh> 00045 00046 using namespace Gecode; 00047 00053 class LangfordNumberOptions : public Options { 00054 public: 00055 int k, n; 00056 00057 LangfordNumberOptions(const char* s, int k0, int n0) 00058 : Options(s), k(k0), n(n0) {} 00060 void parse(int& argc, char* argv[]) { 00061 Options::parse(argc,argv); 00062 if (argc < 3) 00063 return; 00064 n = atoi(argv[1]); 00065 k = atoi(argv[2]); 00066 } 00068 virtual void help(void) { 00069 Options::help(); 00070 std::cerr << "\t(unsigned int) default: " << n << std::endl 00071 << "\t\tparameter n" << std::endl 00072 << "\t(unsigned int) default: " << k << std::endl 00073 << "\t\tparameter k" << std::endl; 00074 } 00075 }; 00076 00084 class LangfordNumber : public Script { 00085 protected: 00086 int k, n; 00087 IntVarArray y; 00088 00089 public: 00091 enum { 00092 PROP_REIFIED, 00093 PROP_EXTENSIONAL, 00094 PROP_EXTENSIONAL_CHANNEL 00095 }; 00097 LangfordNumber(const LangfordNumberOptions& opt) 00098 : k(opt.k), n(opt.n), y(*this,k*n,1,n) { 00099 00100 switch (opt.propagation()) { 00101 case PROP_REIFIED: 00102 { 00103 // Position of values in sequence 00104 IntVarArgs pv(*this,k*n,0,k*n-1); 00105 Matrix<IntVarArgs> p(pv,n,k); 00106 00107 /* 00108 * The occurences of v in the Langford sequence are v numbers apart. 00109 * 00110 * Let \#(i, v) denote the position of the i-th occurence of 00111 * value v in the Langford Sequence. Then 00112 * 00113 * \f$ \forall i, j \in \{1, \dots, k\}, i \neq j: 00114 * \forall v \in \{1, \dots, n\}: \#(i, v) + (v + 1) = \#(j, v)\f$ 00115 * 00116 */ 00117 for (int i=0; i<n; i++) 00118 for (int j=0; j<k-1; j++) 00119 rel(*this, p(i,j)+i+2 == p(i,j+1)); 00120 00121 distinct(*this, pv, opt.icl()); 00122 00123 // Channel positions <-> values 00124 for (int i=0; i<n; i++) 00125 for (int j=0; j<k; j++) 00126 element(*this, y, p(i,j), i+1); 00127 } 00128 break; 00129 case PROP_EXTENSIONAL: 00130 { 00131 IntArgs a(n-1); 00132 for (int v=2; v<=n; v++) 00133 a[v-2]=v; 00134 for (int v=1; v<=n; v++) { 00135 // Construct regular expression for all symbols but v 00136 if (v > 1) 00137 a[v-2]=v-1; 00138 REG ra(a), rv(v); 00139 extensional(*this, y, *ra+rv+(ra(v,v)+rv)(k-1,k-1)+*ra); 00140 } 00141 } 00142 break; 00143 case PROP_EXTENSIONAL_CHANNEL: 00144 { 00145 // Boolean variables for channeling 00146 BoolVarArgs bv(*this,k*n*n,0,1); 00147 Matrix<BoolVarArgs> b(bv,k*n,n); 00148 00149 // Post channel constraints 00150 for (int i=0; i<n*k; i++) 00151 channel(*this, b.col(i), y[i], 1); 00152 00153 // For placing two numbers three steps apart, we construct the 00154 // regular expression 0*100010*, and apply it to the projection of 00155 // the sequence on the value. 00156 REG r0(0), r1(1); 00157 for (int v=1; v<=n; v++) 00158 extensional(*this, b.row(v-1), 00159 *r0 + r1 + (r0(v,v) + r1)(k-1,k-1) + *r0); 00160 } 00161 break; 00162 } 00163 00164 // Symmetry breaking 00165 rel(*this, y[0], IRT_LE, y[n*k-1]); 00166 00167 // Branching 00168 branch(*this, y, INT_VAR_SIZE_MIN, INT_VAL_MAX); 00169 } 00170 00172 virtual void print(std::ostream& os) const { 00173 os << "\t" << y << std::endl; 00174 } 00175 00177 LangfordNumber(bool share, LangfordNumber& l) 00178 : Script(share, l), k(l.k), n(l.n) { 00179 y.update(*this, share, l.y); 00180 00181 } 00183 virtual Space* 00184 copy(bool share) { 00185 return new LangfordNumber(share, *this); 00186 } 00187 }; 00188 00189 00193 int 00194 main(int argc, char* argv[]) { 00195 LangfordNumberOptions opt("Langford Numbers",3,9); 00196 opt.icl(ICL_DOM); 00197 opt.propagation(LangfordNumber::PROP_EXTENSIONAL_CHANNEL); 00198 opt.propagation(LangfordNumber::PROP_REIFIED, 00199 "reified"); 00200 opt.propagation(LangfordNumber::PROP_EXTENSIONAL, 00201 "extensional"); 00202 opt.propagation(LangfordNumber::PROP_EXTENSIONAL_CHANNEL, 00203 "extensional-channel"); 00204 opt.parse(argc, argv); 00205 if (opt.k < 1) { 00206 std::cerr << "k must be at least 1!" << std::endl; 00207 return 1; 00208 } 00209 if (opt.k > opt.n) { 00210 std::cerr << "n must be at least k!" << std::endl; 00211 return 1; 00212 } 00213 Script::run<LangfordNumber,DFS,LangfordNumberOptions>(opt); 00214 return 0; 00215 } 00216 00217 // STATISTICS: example-any 00218