Message Boards Message Boards

What does the unequal constraint slow down solve so much?

GROUPS:

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
Answer
11 months ago

Someone also named Frank Kampas asked this once before.

POSTED BY: Daniel Lichtblau
Answer
11 months ago

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
Answer
11 months ago

Group Abstract Group Abstract