# 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× DAGCH+ DFBADFH

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

blog comments powered by Disqus