Message Boards Message Boards

What does the unequal constraint slow down solve so much?

I'm solving the SEND + MORE = MONEY problem where SEND and MORE are 4 digits numbers and MONEY is a 5 digit number, with each letter representing a different number. If I solve the problem without the constraint that all the numbers are different and then select the answer in which they are, the problem runs quickly. If I put the Unequal constraint into Solve, I don't get a result in any reasonable time.

In[1]:= vars = {s, e, n, d, m, o, r, y};

In[2]:= send = 10^Range[0, 3].{d, n, e, s}

Out[2]= d + 100 e + 10 n + 1000 s

In[3]:= more = 10^Range[0, 3].{e, r, o, m}

Out[3]= e + 1000 m + 100 o + 10 r

In[4]:= money = 10^Range[0, 4].{y, e, n, o, m}

Out[4]= 10 e + 10000 m + 100 n + 1000 o + y

In[5]:= AbsoluteTiming @ 
 Length[res = 
   Solve[{send + more == money, 
     Sequence @@ Thread[0 <= {e, n, d, o, r, y} <= 9], 
     Sequence @@ Thread[1 <= {s, m} <= 9]}, vars, Integers]]

Out[5]= {0.0435814, 155}

In[6]:= AbsoluteTiming @ 
 Select[res, Unequal[Sequence @@ (vars /. #)] &]

Out[6]= {0.00142582, {{s -> 9, e -> 5, n -> 6, d -> 7, m -> 1, o -> 0,
    r -> 8, y -> 2}}}

In[7]:= TimeConstrained[
 Solve[{send + more == money, 
   Sequence @@ Thread[0 <= {e, n, d, o, r, y} <= 9], 
   Sequence @@ Thread[1 <= {s, m} <= 9], Unequal[Sequence @@ vars]}, 
  vars, Integers], 100]

Out[7]= $Aborted
POSTED BY: Frank Kampas
3 Replies
Posted 3 years ago
In[18]:= AbsoluteTiming @ 
 Solve[(s 1000 + e 100 + n 10 + d) + (m 1000 + o 100 + r 10 + 
       e) == (m 10000 + o 1000 + n 100 + e 10 + y )
   && (And @@ Thread[(0 <= # <= 9 &)[{s, e, n, d, m, o, r, y}]])
   && m > 0
   && (And @@ (((#1 != #2) &) @@ # & /@ 
       Subsets[{s, e, n, d, m, o, r, y}, {2}]))
  , {s, e, n, d, m, o, r, y}, Integers]

Out[18]= {0.940472, {{s -> 9, e -> 5, n -> 6, d -> 7, m -> 1, o -> 0, 
   r -> 8, y -> 2}}}

Removing "m > 0" (which is part of the original formulation) causes the solver to wander around the space of solutions without finishing (probably the space is too large?)

I have the impression that the code provided by the OP is not correct.

POSTED BY: carlos aya

Someone also named Frank Kampas asked this once before.

POSTED BY: Daniel Lichtblau

I wanted to get your attention so I could point out that MiniZinc, which is free (using Gecode as the underlying solver), solves this problem, with an alldifferent constraint, in about 40 mSec. I didn't know that last time I asked the question.

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract