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
00053 class Money : public Script {
00054 protected:
00056 static const int nl = 8;
00058 IntVarArray le;
00059 public:
00061 enum {
00062 MODEL_SINGLE,
00063 MODEL_CARRY
00064 };
00066 Money(const Options& opt) : Script(opt), le(*this,nl,0,9) {
00067 IntVar
00068 s(le[0]), e(le[1]), n(le[2]), d(le[3]),
00069 m(le[4]), o(le[5]), r(le[6]), y(le[7]);
00070
00071 if (opt.trace()) {
00072 trace(*this, le, opt.trace());
00073 trace(*this, opt.trace());
00074 }
00075
00076 rel(*this, s, IRT_NQ, 0);
00077 rel(*this, m, IRT_NQ, 0);
00078
00079 distinct(*this, le, opt.ipl());
00080
00081 switch (opt.model()) {
00082 case MODEL_SINGLE:
00083 rel(*this, 1000*s+100*e+10*n+d
00084 + 1000*m+100*o+10*r+e
00085 == 10000*m+1000*o+100*n+10*e+y,
00086 opt.ipl());
00087 break;
00088 case MODEL_CARRY:
00089 {
00090 IntVar c0(*this,0,1), c1(*this,0,1), c2(*this,0,1), c3(*this,0,1);
00091 rel(*this, d+e == y+10*c0, opt.ipl());
00092 rel(*this, c0+n+r == e+10*c1, opt.ipl());
00093 rel(*this, c1+e+o == n+10*c2, opt.ipl());
00094 rel(*this, c2+s+m == o+10*c3, opt.ipl());
00095 rel(*this, c3 == m, opt.ipl());
00096 }
00097 break;
00098 default: GECODE_NEVER;
00099 }
00100
00101 branch(*this, le, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
00102 }
00104 virtual void
00105 print(std::ostream& os) const {
00106 os << "\t" << le << std::endl;
00107 }
00108
00110 Money(bool share, Money& s) : Script(share,s) {
00111 le.update(*this, share, s.le);
00112 }
00114 virtual Space*
00115 copy(bool share) {
00116 return new Money(share,*this);
00117 }
00118 };
00119
00123 int
00124 main(int argc, char* argv[]) {
00125 Options opt("SEND+MORE=MONEY");
00126 opt.model(Money::MODEL_SINGLE);
00127 opt.model(Money::MODEL_SINGLE, "single", "use single linear equation");
00128 opt.model(Money::MODEL_CARRY, "carry", "use carry");
00129 opt.solutions(0);
00130 opt.iterations(20000);
00131 opt.parse(argc,argv);
00132 Script::run<Money,DFS,Options>(opt);
00133 return 0;
00134 }
00135
00136
00137