The Museum of HP Calculators

HP Forum Archive 17

[ Return to Index | Top of Index ]

How to speak the problem?
Message #1 Posted by Olivier TREGER on 21 June 2007, 12:19 p.m.

Hello all,

Despite my now decent collection of HP calcs, I must admit that, having left school quite early, I miss the necessary basis to figure out how to spell the following problem.

my daughter Agathe was asked to solve the following kinda sudoku by her teacher: let's say a square 3x3 boxes.

In each box a number (left to right, top to bottom) such as: a+b+c=96 d+e+f=315 g+h+i=12 but also a+d+g=72 b+e+h=40 c+f+i=126 PLEASE NOTE: e=5

I suspect there's something to do with matrices but I ain't sure. I've tried to use Mathematica (don't laugh...) to modelize (?) a formula with no success.

I'm sure somebody around will tell me in three words where to dig.

Thanks for help Olivier

      
Re: How to speak the problem?
Message #2 Posted by Monte Dalrymple on 21 June 2007, 12:40 p.m.,
in response to message #1 by Olivier TREGER

There appears to be no solution.

The first three equalities say a+b+c+d+e+f+g+h+i = 423

The last three equalities say a+b+c+d+e+f+g+h+i = 238

... or is there a typo in your post?

Monte

      
Re: How to speak the problem?
Message #3 Posted by Walter B on 21 June 2007, 12:42 p.m.,
in response to message #1 by Olivier TREGER

Bonjour Olivier,

je pense que ... you need two more constraints. You wrote "kinda sudoku", so was there anything further required implicitely?

            
Re: How to speak the problem?
Message #4 Posted by Dave Shaffer (Arizona) on 21 June 2007, 3:25 p.m.,
in response to message #3 by Walter B

I agree with Walter: there are 9 unknowns, so you need nine equations or constraints to determine a unique solution. If this is a true sudoku, then each digit (1 through 9) should be used only once. That, plus the equations and constraint you gave provide only 8 of the necessary 9 conditions.

      
Re: How to speak the problem?
Message #5 Posted by Olivier TREGER on 21 June 2007, 1:22 p.m.,
in response to message #1 by Olivier TREGER

I'm completely sorry...

Please replace "+" by "x"

I thought I was unable to count. I can't type either...

            
Re: How to speak the problem?
Message #6 Posted by Massimo Gnerucci (Italy) on 21 June 2007, 2:06 p.m.,
in response to message #5 by Olivier TREGER

I believe the solution is:

4	*	4	*	6	=	96	(2*2*2*2*2*3)
*		*		*			
9	*	5	*	7	=	315	(3*3*5*7)
*		*		*			
2	*	2	*	3	=	12	(2*2*3)
=		=		=			
72		40		126			
(2*2*2*3*3)	(2*2*2*5)		(2*3*3*7)

Greetings,
Massimo

                  
Re: How to speak the problem?
Message #7 Posted by Olivier TREGER on 21 June 2007, 2:41 p.m.,
in response to message #6 by Massimo Gnerucci (Italy)

That's one solution.

Mine was: 8*4*3 9*5*7 1*2*6

But my question was: how to create a model that would solve the problem?

                        
Re: How to speak the problem?
Message #8 Posted by Egan Ford on 21 June 2007, 2:51 p.m.,
in response to message #7 by Olivier TREGER

Was one of the constraints that you can only used each digit once (like sudoku)? If so I think you have the correct answer.

                              
Re: How to speak the problem?
Message #9 Posted by Olivier TREGER on 21 June 2007, 4:36 p.m.,
in response to message #8 by Egan Ford

Quote:
Was one of the constraints that you can only used each digit once (like sudoku)? If so I think you have the correct answer.
Yes. I forgot to mention it (again).

But still, I can't figure out what method to be used to solve it as a generic problem.

                                    
Re: How to speak the problem?
Message #10 Posted by Egan Ford on 21 June 2007, 5:16 p.m.,
in response to message #9 by Olivier TREGER

Quote:
But still, I can't figure out what method to be used to solve it as a generic problem.
I can think of a few.

1. Brute force. There are only 40320 possible outcomes. Try them all. If you have access to a quantum calculator you can test all possible outcomes simultaneously.

2. Random guesses. Could be faster or slower than #1.

Both #1 and #2 can be easily parallelized across multiple calculators. #1 would need a unique domain for each calculator. #2 would just use different random seeds.

3. Search. Start with the column or row with the least number of possibilities (pairs) that meets the condition of the row/column with the most knowns (5 in this case). Push that on a stack, remove the 2 digits from a list of possibilities. E.g. start with def, it can only be 9,5,7 or 7,5,9, then beh, then abc, adh, etc... once you get to a point where none of the pairs will work, pop off the stack the last working pair, and try a different pair, move forward, etc... you may have to pop off multiple pairs. Eventually you'll end up with an answer.

#1 and #3 will allow you to predict the worse case number of operations.

                                          
Re: How to speak the problem?
Message #11 Posted by Olivier TREGER on 21 June 2007, 5:27 p.m.,
in response to message #10 by Egan Ford

That doesn't look like an industrialized method :)

What I don't understand is that when I push the 6 equations in Mathematica, it gives me back, it says: 

Equations may not give solutions for all "solve" variables.
although a solution can be found by simple guessing.

Ain't there no way to build a standard algorithm to find out?

                                                
Re: How to speak the problem?
Message #12 Posted by Egan Ford on 21 June 2007, 5:44 p.m.,
in response to message #11 by Olivier TREGER

Can you also tell Mathematica a!=b!=c!=d!=e!=f!=g!=h!=i, a through i belongs to the set of positive integers, and e=5?

                                                      
Re: How to speak the problem?
Message #13 Posted by Olivier TREGER on 21 June 2007, 5:59 p.m.,
in response to message #12 by Egan Ford

Quote:
Can you also tell Mathematica a!=b!=c!=d!=e!=f!=g!=h!=i, a through i belongs to the set of positive integers, and e=5?
I just tried: 
{a,b,c,d,f,g,h,i}<9
{a,b,c,d,f,g,h,i}>1
with no success either
                                                            
Re: How to speak the problem?
Message #14 Posted by Egan Ford on 21 June 2007, 6:09 p.m.,
in response to message #13 by Olivier TREGER

Needs to be >=, not just >. You also need to state somehow that each variable is unique.

                                          
Multiplicative sudoku
Message #15 Posted by Karl Schneider on 22 June 2007, 1:29 a.m.,
in response to message #10 by Egan Ford

Quote:
Brute force. There are only 40320 possible outcomes. Try them all. If you have access to a quantum calculator you can test all possible outcomes simultaneously.

An arithmetical problem solved by brute force (i.e., testing all possible arrangements of input values for solutions) and by more-intelligent means was discussed in this recent thread:

http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv017.cgi?read=112157#112157

As Walter pointed out, the problem cannot be solved directly, because there are eight "degrees of freedom" for the nine inputs, but only six equations. Standard linear-algebra techniques can't be used to simplify the problem, because the problem isn't linear (whereas a standard sudoku puzzle is).

-- KS

      
Re: How to speak the problem?
Message #16 Posted by Egan Ford on 21 June 2007, 2:01 p.m.,
in response to message #1 by Olivier TREGER

Is this what the problem looks like?

.---.---.---.
| a | b | c |   = 96
|---+---+---|
| d | e | f |   = 315
|---+---+---|
| g | h | i |   = 12
'---'---'---'
   \   \   \
    \   \   \-> = 126
     \   \----> = 40
      \-------> = 72
            
Re: How to speak the problem?
Message #17 Posted by Olivier TREGER on 21 June 2007, 2:39 p.m.,
in response to message #16 by Egan Ford

Yes it does look like this

                  
Re: How to speak the problem?
Message #18 Posted by Allen on 21 June 2007, 8:39 p.m.,
in response to message #17 by Olivier TREGER

Using this 48/49/50 program you can find the Divisors of each number: 


<<
{ } OVER SQRT 2 SWAP
  FOR N                        ' SETS UP RANGE TO RUN 2 TO SQRT(N)
     IF OVER N /                
     FP 0 == THEN N+ END       ' APPEND TO LIST IF DIVISIBLE
  NEXT
DUP2 / +                       ' APPEND LIST ALL DIVISORS > SQRT(N) 
SORT 
DUP 10 < *                     ' CRUDE MASK TO HIDE ALL VALUES <=9
>>

 YIELDS THE POSSIBLE DIVISORS FOR EACH ROW:  

.---.---.---.             step1         step 2
| a | b | c6|   = 96  = [2 3 4 6 8]    [2 8]
|---+---+---|
| d9| e5| f7|   = 315 = [3 5 7 9]      [solved]
|---+---+---|
| g | h | i3|   = 12  = [2 3 4 6]      [1 4] 
'---'---'---'
   \   \   \
    \   \   \-> = 126 = [2 3 6 7 9]    [3 6]
     \   \----> = 40  = [2 4 5 8]      [1 2 4 8] 
      \-------> = 72  = [2 3 4 6 8 9]  [1 2 4 8]

So you can conclude that: 

Step 1
1. e must be 5 (given)
2. f must be 7 (no other common divisors except 126 and 315)
3. d must be 9 (=315/(5*7))

Step 2
4. i must be 3 (only CD with 126 and 12 (step 2))
5. eliminate [1 2 4 8] as divisors of 126 b/c must be for 40 and 72
6. c must be 6  (=126/(7*3)

7. either a or b must be 8. 
Try a: 
     g must be 1 , leaving 96=8*2*6 works
Try b: 
     g must be 4, leaving 2*8*6 ALSO WORKS.

Is there more than one possible solution? perhaps I am missing something

Edited: 21 June 2007, 8:47 p.m.

                        
Re: How to speak the problem?
Message #19 Posted by Dave Shaffer (Arizona) on 21 June 2007, 11:09 p.m.,
in response to message #18 by Allen

"4. i must be 3 (only CD with 126 and 12 (step 2))"

No - a 6 works, too (to give Olivier's solution)!

(I had already prepared the following):

Actually, if we read between the lines, there ARE other constraints.

If this is a sudoku of the normal type, perhaps the most compelling constraint is that the values must be (positive) integers. And, as noted by others, they must lie between 1 and 9 and in fact include ALL the integers from 1 to 9.

So, let’s try some educated guess work. First, note that abc=96, def=315, and cfi=126 tell us that none of a, b, c, d, e, f, i can be a 1. (If one of the variables in a triple product was one, the maximum product would be 8x9=72.) Thus, we know already that either g or h must be 1. ghi=12 tells us that the other two (the pair g and i or the pair h and i) must be either the pair 2 and 6 or the pair 3 and 4. (Turns out, both work.)

Now, since beh = 40 and e=5, we know that bh = 8. If b and h are positive integers (between 1 and 9!), then b and h must be the pair 1 and 8 or the pair 2 and 4. Similarly, def = 315 leads to the conclusion that df = 63 and thus d and f are the pair 7 and 9. Since adg = 72, d must be a 9 (and f a 7), because if d was a 7, it would not divide evenly into 72.

We now have for sure: e = 5 (given), d = 9, and f = 7.

Also, from adg = 72, and d = 9, we get ag = 8. We already ascertained that g must be 1, or 2 or 6, or 3 or 4. Since all numbers must be integers, ag = 8 rules out g = 6 or 3, so g must be 1 or 2 or 4.

Note, too, that cfi = 126 gives ci = 18 (because f = 7). So, c and i are either the pair 2 and 9 or the pair 3 and 6. Because d = 9, c and i must be the pair 3 and 6.

At this point, try b = 1 or 2 or 4 or 8, using abc = 96. Look for inconsistencies with the known values. Do the same for other possible pairs.

When you are done, I think you will find that there are at least two solutions consistent with all the triple product conditions:

a b c d e f g h i = 8 4 3 9 5 7 1 2 6 (as reported by Olivier)

a b c d e f g h i = 8 2 6 9 5 7 1 4 3 (my alternate solution)

Edited: 21 June 2007, 11:09 p.m.

                              
Re: How to speak the problem?
Message #20 Posted by Olivier TREGER on 22 June 2007, 2:36 a.m.,
in response to message #19 by Dave Shaffer (Arizona)

So...

If I read well all the answers, there seem to be no way to automate the search for a solution. Right?

Oh, by the way, many thanks to all of you for these explanations. It happens that I found a solution but it seemed to be a matter of chance.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall