Puzzle...

One of my managers, who also happens to be a pretty smart guy, and I were having a discussion today. We were talking about various interesting subjects including Engineering subjects like Natural Language Processing (NLP) and AI. And he asked me, "How do we make a computer smart enough to be able to solve a puzzle?" Now the puzzle could be a mathematical puzzle, a logical puzzle or even a language puzzle. And just to give me an example he asked me a puzzle.

What is a 2 digit number, that, when multiplied with 9, gives a 3 digit number. Now the first digit of the 3 digit answer is the same as the first digit of the original 2 digit number and the last digit of the 3 digit answer is the same as the 2nd digit of the original 2 digit number and the 2nd digit of the 3 digit answer is 0.

so if XY * 9 = X0Y, what is X and Y?

Now the problems is quite simple and I could solve it in the time required by me to leave from my desk to my bike parked below. And that's like less than 2 minutes. The issue here is how did you approach this problem and how do you make a computer arrive to the best approach.

So this is a question to all readers. Please solve this problem and tell me how you solved it and what approach you took.

Comments

• Anonymous
  January 02, 2008
  Solving a problem like this in prolog is fairly straight forward. The only real challenge is turning a two or three digit number into a series of symbols and back, and that isn't particularly difficult.   A bigger challenge would be a program that would read the description you provided above and would write the prolog application that would solve the problem.  Now, that's more interesting.   (Of course, NLP is a strong suit for Prolog as well). Solving puzzles is not a very good Turing test.  Determining the emotional context of a description of a character in a short story, and being able to answer questions about alternative choices that the character could have made... now that would be a much better test of artificial intelligence.

• Anonymous
  January 02, 2008
  Not being a uber math type I had a guess. I started with 12, knowing it would yeild a 3 digit number, then went to 19, at twenty the first digit is different to the yielded result.  Then realising I'd read the question wrong started again.  But this gave me a rough idea of what I was dealing with, kinda set up my brain for math really.  Odd but true. Figure out the "units" value that gives 9*Y=(n)Y   knowing the 9 times table told me that any number ending in 5 will satisfy this, then I just tried each one of the tens + 5 15,25,35,    45 Knowing that I was only dealing with a possible 9 combinations after the initial calculation led me to brute force it rather than brute force my way through 89 of them. Unless I read the qestion wrong again of course. Hence the anon.

• Anonymous
  January 03, 2008
  The answer is x = 4 and y = 5. xy9 = x0y [using same notation as problem statement] xy(10 - 1) = x0y xy0 - xy = x0y This implies 0 - y mod 10 = y; or 2y = 0 or y = 5   [using last digit of x0y] This also implies that y - 1 - x = 0 mod 10 [using the 0 in x0y]  i.e 4 - x = 0 mod 10 or x = 4 The approach I would suggest is translating the puzzle from natural language to a satisfiability problem and use a SAT solver.

• Anonymous
  January 03, 2008
             //   mi            //      *            //    9            //  ----            //  m0i            //              then...            //  i * 9 = zi            //  m * 9 = (m-1)(10-z)            int i;            for (i = 1; i < 9; i++)                if (((i * 9) - i) % 10 == 0)                    break;            int z = i * 9 / 10;            int tenMinasZ = 10 - z;            int firstDigit,secondDigit;            int m;            for (m = 1; m < 9; m++)            {                firstDigit = (m * 9) % 10;                secondDigit = (m * 9) / 10;                if ((firstDigit == tenMinasZ) && (secondDigit == m-1))                    break;            }            int number = i + (m * 10);            Console.WriteLine("The Number is : " + number + "n" + "Multiply by 9 Result is: " + number * 9);

• Anonymous
  January 03, 2008
  Well, it's easy to see that 9XY=X0Y can be represented as 90X + 9Y = X0Y. From that, there are only two cases where 9Y has Y as the second digit, Y=0 and Y=5 For the Y=0 case, 90X = X00 does not have an integer solution. For the Y= 5 case, 90X + 45 = X05, so 90X = (X-1)60, leaving X=4 So, XY = 45 and 9*45 = 405

• Anonymous
  January 05, 2008
  I solved it by breaking the problem apart in 2 different pieces:

1. Y * 9 = ?Y -> there's only 1 candidate: 5 and 5 * 9 = 45
2. X * 9 = ?6 -> there's only 1 candidate: 4 Took about 30 secs. 20 to figure out the approach and 10 to actually calculate.