send+most=money

Problem

   send
 + most
 ------
  money

Given the above equation, assign digits to each letter so that the equation holds when the letter are substituted with the assigned digits. No two letter may be assigned the same digit and the first letter of a word is not allowed to be assigned 0 (i.e. a number may not start with 0 in the equation). There are multiple valid assignments, the one which maximizes the value of “money” is sought.

Code

 1 require 'rubygems'
 2 require 'gecoder'
 3 
 4 # Solves the cryptarithmetic send+most=money problem while maximizing the value
 5 # of "money".
 6 class SendMostMoney
 7   include Gecode::Mixin
 8 
 9   attr :money
10 
11   def initialize
12     # Set up the variables, 9 letters with domain 0..9.
13     s,e,n,d,m,o,s,t,y = letters_is_an int_var_array(9, 0..9)
14     # Express the quantity we are optimizing, in this case money.
15     # This utilises that any operand can be converted into a variable.
16     @money = equation_row(m,o,n,e,y).to_int_var
17     
18     # Set up the constraints.
19     # The equation must hold.
20     (equation_row(s, e, n, d) + equation_row(m, o, s, t)).must == 
21       equation_row(m, o, n, e, y) 
22     
23     # The initial letters may not be 0.
24     s.must_not == 0
25     m.must_not == 0
26     
27     # All letters must be assigned different digits.
28     letters.must_be.distinct
29 
30     # Set the branching.
31     branch_on letters, :variable => :smallest_size, :value => :min
32   end
33 
34   private
35 
36   # A helper to make the linear equation a bit tidier. Takes a number of
37   # variables and computes the linear combination as if the variable
38   # were digits in a base 10 number. E.g. x,y,z becomes
39   # 100*x + 10*y + z .
40   def equation_row(*variables)
41     variables.inject{ |result, variable| variable + result * 10 }
42   end
43 end
44 
45 solution = SendMostMoney.new.maximize! :money
46 puts 's e n d m o s t y'
47 puts solution.letters.values.join(' ')
48 puts "money: #{solution.money.value}"

Output

s e n d m o s t y
3 7 8 2 1 0 9 4 6
money: 10876