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.

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.

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