Solving a Math Puzzle with Ruby

On page 212 of the excellent book The Art of Game Design by Jesse Schell, the author presents the following puzzle as a negative example of the puzzle principle of “make it easy to get started”. The problem is to find the value of all the letters.

   CEI
 ×  DA
   GCH
+ DFB 
  ADFH

Next the author has to say that “most players are at a complete loss as to how to begin solving a puzzle like this”. After reading this I had to prove that I could beat it. I started on what turned into a quest of seven hours spread over two days.

Some initial examination of the equation yields a few clues. To start with, a zero would not typically be written on the leftmost digit of a multiplier. So C and D cannot be zero. Furthermore, D×C=D. This means that either C or D must be 1. Since D×I does not equal D we can prove that C is 1. I continued on the path of slowly narrowing done the possible values of each letter until, in theory, I should have arrived at the solution. It did not work out this way in practice. Three times I reached a point where I had a logical contradiction such as having both proved that D was 6 and that D must be less than 5.

After this, I really started to wonder if the problem had a solution. After all, the author had previously discussed player frustration and unfair challenges, and the puzzle was a negative example. Maybe there was no solution. On the other hand, my attack on the problem had been based on a great number of small assertions that built on all previous assertions. One inaccurate assertion would break the whole chain. At this point, I had put four hours into this puzzle and I was not about to stop until I had solved it, or I had proved there is no solution.

It was time to bring the big guns into play and just brute-force the problem. It should be a simple matter to write a script in Ruby that tests every combination of values for a solution. Either I would have the answer, or I would prove there was no answer. As it turned out it, took about three hours to get the script right. Some of that was due to the fact that I decided to try some new features of Ruby 1.9 such as chaining iterators together, but most of it was due to difficulties perfecting a function that would yield every combination of values. But finally I built a solver for this type of puzzle.

def chars_to_number( digits, char_values )
  digits.reverse.chars.each_with_index.inject(0) do |sum, char_and_place|
    char, place = char_and_place 
    sum + char_values[char] * (10**place)
  end
end

def valid_multiplication?( char_mult1, char_mult2, char_product, char_values )
  mult1 = chars_to_number( char_mult1, char_values )
  mult2 = chars_to_number( char_mult2, char_values )
  product = chars_to_number( char_product, char_values )
  mult1 * mult2 == product
end

def valid_addition?( char_add1, char_add2, char_sum, char_values )
  add1 = chars_to_number( char_add1, char_values )
  add2 = chars_to_number( char_add2, char_values )
  sum = chars_to_number( char_sum, char_values )
  add1 + add2 == sum
end

def each_combination( char_set, value_set, char_values={}, &block )
  char_set = char_set.clone
  value_set = value_set.clone
  char_values = char_values.clone
  
  char = char_set.pop
  if char_set.size > 0
    value_set.each do |value|
      char_values[char] = value
      value_set_without_current_value = value_set.clone
      value_set_without_current_value.delete( value )
      each_combination( char_set, value_set_without_current_value, char_values, &block )
    end
  else
    value_set.each do |value|
      char_values[char] = value
      block.call( char_values.clone )
    end
  end
end

mult1 =   "cei"
mult2 =    "da"
add1 =    "gch"
add2 =   "dfb "
answer = "adfh"

char_set = (mult1 + mult2 + add1 + add2 + answer).chars.to_a.uniq.sort
char_set.delete(" ") # space is hard-coded to 0
value_set = (0..9).to_a

each_combination char_set, value_set, " " => 0 do |char_values|
 if valid_multiplication?( mult1, mult2, answer, char_values ) && valid_addition?( add1, add2, answer, char_values ) 
    puts char_values
  end
end

You can download the final code for this solver. The library code is split from the runner for this specific problem and it also includes a test suite.

As it turns out the puzzle did have a solution. Select the space below to reveal the solution.

A = 4
B = 7
C = 1
D = 3
E = 2
F = 8
G = 5
H = 6
I = 9

I would be interested in hearing about any other approaches to this type of puzzle.