# <jack>

## If it’s too hard you’re doing it wrong.

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

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|