00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00049 class LangfordNumberOptions : public Options {
00050 public:
00051 int k, n;
00052
00053 LangfordNumberOptions(const char* s, int k0, int n0)
00054 : Options(s), k(k0), n(n0) {}
00056 void parse(int& argc, char* argv[]) {
00057 Options::parse(argc,argv);
00058 if (argc < 3)
00059 return;
00060 n = atoi(argv[1]);
00061 k = atoi(argv[2]);
00062 }
00064 virtual void help(void) {
00065 Options::help();
00066 std::cerr << "\t(unsigned int) default: " << n << std::endl
00067 << "\t\tparameter n" << std::endl
00068 << "\t(unsigned int) default: " << k << std::endl
00069 << "\t\tparameter k" << std::endl;
00070 }
00071 };
00072
00080 class LangfordNumber : public Script {
00081 protected:
00082 int k, n;
00083 IntVarArray y;
00084
00085 public:
00087 enum {
00088 PROP_REIFIED,
00089 PROP_EXTENSIONAL,
00090 PROP_EXTENSIONAL_CHANNEL
00091 };
00093 LangfordNumber(const LangfordNumberOptions& opt)
00094 : Script(opt), k(opt.k), n(opt.n), y(*this,k*n,1,n) {
00095
00096 switch (opt.propagation()) {
00097 case PROP_REIFIED:
00098 {
00099
00100 IntVarArgs pv(*this,k*n,0,k*n-1);
00101 Matrix<IntVarArgs> p(pv,n,k);
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113 for (int i=0; i<n; i++)
00114 for (int j=0; j<k-1; j++)
00115 rel(*this, p(i,j)+i+2 == p(i,j+1));
00116
00117 distinct(*this, pv, opt.ipl());
00118
00119
00120 for (int i=0; i<n; i++)
00121 for (int j=0; j<k; j++)
00122 element(*this, y, p(i,j), i+1);
00123 }
00124 break;
00125 case PROP_EXTENSIONAL:
00126 {
00127 IntArgs a(n-1);
00128 for (int v=2; v<=n; v++)
00129 a[v-2]=v;
00130 for (int v=1; v<=n; v++) {
00131
00132 if (v > 1)
00133 a[v-2]=v-1;
00134 REG ra(a), rv(v);
00135 extensional(*this, y, *ra+rv+(ra(v,v)+rv)(k-1,k-1)+*ra);
00136 }
00137 }
00138 break;
00139 case PROP_EXTENSIONAL_CHANNEL:
00140 {
00141
00142 BoolVarArgs bv(*this,k*n*n,0,1);
00143 Matrix<BoolVarArgs> b(bv,k*n,n);
00144
00145
00146 for (int i=0; i<n*k; i++)
00147 channel(*this, b.col(i), y[i], 1);
00148
00149
00150
00151
00152 REG r0(0), r1(1);
00153 for (int v=1; v<=n; v++)
00154 extensional(*this, b.row(v-1),
00155 *r0 + r1 + (r0(v,v) + r1)(k-1,k-1) + *r0);
00156 }
00157 break;
00158 }
00159
00160
00161 rel(*this, y[0], IRT_LE, y[n*k-1]);
00162
00163
00164 branch(*this, y, INT_VAR_SIZE_MIN(), INT_VAL_MAX());
00165 }
00166
00168 virtual void print(std::ostream& os) const {
00169 os << "\t" << y << std::endl;
00170 }
00171
00173 LangfordNumber(LangfordNumber& l)
00174 : Script(l), k(l.k), n(l.n) {
00175 y.update(*this, l.y);
00176
00177 }
00179 virtual Space*
00180 copy(void) {
00181 return new LangfordNumber(*this);
00182 }
00183 };
00184
00185
00189 int
00190 main(int argc, char* argv[]) {
00191 LangfordNumberOptions opt("Langford Numbers",3,9);
00192 opt.ipl(IPL_DOM);
00193 opt.propagation(LangfordNumber::PROP_EXTENSIONAL_CHANNEL);
00194 opt.propagation(LangfordNumber::PROP_REIFIED,
00195 "reified");
00196 opt.propagation(LangfordNumber::PROP_EXTENSIONAL,
00197 "extensional");
00198 opt.propagation(LangfordNumber::PROP_EXTENSIONAL_CHANNEL,
00199 "extensional-channel");
00200 opt.parse(argc, argv);
00201 if (opt.k < 1) {
00202 std::cerr << "k must be at least 1!" << std::endl;
00203 return 1;
00204 }
00205 if (opt.k > opt.n) {
00206 std::cerr << "n must be at least k!" << std::endl;
00207 return 1;
00208 }
00209 Script::run<LangfordNumber,DFS,LangfordNumberOptions>(opt);
00210 return 0;
00211 }
00212
00213
00214