# Solving a Math Puzzle with Ruby

Posted on 08/08/2009

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
```

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

sum = chars_to_number( char_sum, char_values )
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"

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|
puts char_values
end
end
``````

You can view the final code for this solver on Github. 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.