Here are answers + commentary to the number puzzle I posted yesterday, which was, fill in the digits:

ABC

+__DEF__

GHI

OR prove it’s impossible.

I originally moderated the answers but have now gone back and published them all. My conclusion is that the folks who read this blog are way smarter than I am.

**So it is indeed possible**, and the general consensus from comments is that there are 336 solutions.

Solutions generally fell into 3 categories:

**Adhoc**.

Brute force manually experiment to find a success case. I only had a baby-scribble pad available at the time, which works for scribbling a few numbers, but is impractical for writing more complex mathematical rigorous stuff. Hence I pursued an adhoc solution and found (218+439=657). For the record, I had a solution before I posted the question :). Lots of folks posted other random adhoc solutions.

**Mathematical rigor**.

Use more fancy math + number theory to get results. David Srbecky had a great demonstration of this in his comment.

**Computer searches**.

This sort of question screams for an automated search. I believe you only need to check (9 pick 6 = 60480) possible inputs, which is a very easily searched space. A few folks posted code snippets to do the search. Folks posted C# (1, 2), Python, Haskell solutions. It’s easy enough that the C# snippet ran within seconds, and they weren’t even optimized.

**Proving it’s impossible?**

One interesting catch is that you need a carry bit (2 digits that add to over 10). In my case, (218+439 = 657), that was the 8+9=17. You can easily prove that you need a carry-bit with simple number theory (such as by inspecting even + odds). There are 5 odd numbers in 1…9 and 4 even numbers. The carry bit gives you an extra odd number (a one) in the mix. (See Korn1699‘s comment for further explanation). Once I noticed that, I used it to prune the search space in my adhoc search.

This sort of thing is another cute example of “impossible” vs. “insufficiently clever”. If you forget about carry bits and just look at the numbers straight up, you can easily come up with a flawed proof that this is impossible.

PingBack from http://blogs.msdn.com/jmstall/archive/2007/06/12/number-puzzle.aspx

The search space of 9! is small enough that it’s a waste of time to worry about checking only 9 pick 6. With simply the "print" line removed from my solution:

03:36 PM ~/code$ time python abc.py

real 0m2.065s

user 0m0.107s

sys 0m0.046s

This was my verbose solution:

class Program

{

static void Main(string[] args)

{

for (int one = 123; one <= 987; one++)

for (int two = 123; two <= 987; two++)

{

int three = one + two;

if (three > 987)

continue;

for (int digit = 1; digit <= 9; digit++)

if (!HasDigit(one, digit) && !HasDigit(two, digit) && !HasDigit(three, digit))

goto keep_checking;

Answer(one, two, three);

keep_checking:;

}

}

static bool HasDigit(int value, int digit)

{

if (value % 10 == digit) return true;

if ((value % 100 – value % 10) / 10 == digit) return true;

if ((value % 1000 – value % 100) / 100 == digit) return true;

return false;

}

static void Answer(int one, int two, int three)

{

Console.WriteLine(" {0}n+{1}n—–n {2}n", one, two, three);

}

}

Here a similar example program in the funtional/logic language Mercury.

http://www.cs.mu.oz.au/research/mercury/tutorial/book/book.pdf Page 19