eve/did=.talktalktalk...

I've stumbled across this problem recently: http://www.jimloy.com/puzz/evedid.htm

It is very much like the SEND + MORE = MONEY problem, but I thought it would be more interesting (=harder to solve). Nope, not at all.

OK, the problem is the following:

Find the digits E,V,D,I,T,A,L,K such that this equation holds: EVE/DID=.TALKTALKTALK...
EVE and DID are 2 numbers with 3 digits each, and .TALKTALKTALK... is a floating point number.

After exploiting the following property, the problem gets simpler:

0.TALKTALKTALK... = TALK/9999 (try it with a 4 digit number, if you want to see it in action: http://lmgtfy.com/?q=1234/9999)

Thus, the equation turns into EVE/DID = TALK/9999 and then to EVE*9999 = DID*TALK.

Now it is easy to write this as a constraint model. If we choose to model in Essence Prime, use Tailor[1] to generate a Minion[2] input file from it, and then use Minion to actually solve the problem, it is solved almost instantaneously. Thanks to these two great tools!

The model I used is the following:

ESSENCE' 1.0
    find E : int(1..9)
    find V : int(0..9)
    find D : int(1..9)
    find I : int(0..9)
    find T : int(0..9)
    find A : int(0..9)
    find L : int(0..9)
    find K : int(0..9)
such that
    (E*100 + V*10 + E*1) * 9999 = (D*100 + I*10 + D*1) * (T*1000 + A*100 + L*10 + K*1),   
    alldiff([E,V,D,I,T,A,L,K])

If you have tailor and minion installed, just run the following commands to solve the problem.

java -jar tailor.jar -aux-info -out evedidtalk.minion evedidtalk.eprime

minion evedidtalk.minion -findallsols

It only takes less than 1 sec (both commands together) to find all two possible solutions.

[1] http://www.cs.st-andrews.ac.uk/~andrea/tailor
[2] http://sourceforge.net/projects/minion