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());
00098 }
00100 virtual void
00101 print(std::ostream& os) const {
00102 os << "\t" << le << std::endl;
00103 }
00104
00106 Money(Money& s) : Script(s) {
00107 le.update(*this, s.le);
00108 }
00110 virtual Space*
00111 copy(void) {
00112 return new Money(*this);
00113 }
00114 };
00115
00119 int
00120 main(int argc, char* argv[]) {
00121 Options opt("SEND+MORE=MONEY");
00122 opt.model(Money::MODEL_SINGLE);
00123 opt.model(Money::MODEL_SINGLE, "single", "use single linear equation");
00124 opt.model(Money::MODEL_CARRY, "carry", "use carry");
00125 opt.solutions(0);
00126 opt.iterations(20000);
00127 opt.parse(argc,argv);
00128 Script::run<Money,DFS,Options>(opt);
00129 return 0;
00130 }
00131
00132
00133