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 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037
00038 using namespace Gecode;
00039
00049 class Money : public Script {
00050 protected:
00052 static const int nl = 8;
00054 IntVarArray le;
00055 public:
00057 enum {
00058 MODEL_SINGLE,
00059 MODEL_CARRY
00060 };
00062 Money(const Options& opt) : Script(opt), le(*this,nl,0,9) {
00063 IntVar
00064 s(le[0]), e(le[1]), n(le[2]), d(le[3]),
00065 m(le[4]), o(le[5]), r(le[6]), y(le[7]);
00066
00067 if (opt.trace()) {
00068 trace(*this, le, opt.trace());
00069 trace(*this, opt.trace());
00070 }
00071
00072 rel(*this, s, IRT_NQ, 0);
00073 rel(*this, m, IRT_NQ, 0);
00074
00075 distinct(*this, le, opt.ipl());
00076
00077 switch (opt.model()) {
00078 case MODEL_SINGLE:
00079 rel(*this, 1000*s+100*e+10*n+d
00080 + 1000*m+100*o+10*r+e
00081 == 10000*m+1000*o+100*n+10*e+y,
00082 opt.ipl());
00083 break;
00084 case MODEL_CARRY:
00085 {
00086 IntVar c0(*this,0,1), c1(*this,0,1), c2(*this,0,1), c3(*this,0,1);
00087 rel(*this, d+e == y+10*c0, opt.ipl());
00088 rel(*this, c0+n+r == e+10*c1, opt.ipl());
00089 rel(*this, c1+e+o == n+10*c2, opt.ipl());
00090 rel(*this, c2+s+m == o+10*c3, opt.ipl());
00091 rel(*this, c3 == m, opt.ipl());
00092 }
00093 break;
00094 default: GECODE_NEVER;
00095 }
00096
00097 branch(*this, le, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), nullptr,
00098 [](const Space&, const Brancher&, unsigned int a,
00099 IntVar, int i, const int& n,
00100 std::ostream& o) {
00101 static char name[8] = {'s','e','n','d',
00102 'm','o','r','y'};
00103 o << name[i]
00104 << ((a == 0) ? " = " : " != ")
00105 << n;
00106 });
00107 }
00109 virtual void
00110 print(std::ostream& os) const {
00111 os << "\t" << le << std::endl;
00112 }
00113
00115 Money(Money& s) : Script(s) {
00116 le.update(*this, s.le);
00117 }
00119 virtual Space*
00120 copy(void) {
00121 return new Money(*this);
00122 }
00123 };
00124
00128 int
00129 main(int argc, char* argv[]) {
00130 Options opt("SEND+MORE=MONEY");
00131 opt.model(Money::MODEL_SINGLE);
00132 opt.model(Money::MODEL_SINGLE, "single", "use single linear equation");
00133 opt.model(Money::MODEL_CARRY, "carry", "use carry");
00134 opt.solutions(0);
00135 opt.iterations(20000);
00136 opt.parse(argc,argv);
00137 Script::run<Money,DFS,Options>(opt);
00138 return 0;
00139 }
00140
00141
00142