Posts: 120
Threads: 19
Joined: Nov 2006
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
Posts: 297
Threads: 25
Joined: Nov 2006
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
Posts: 4,587
Threads: 105
Joined: Jul 2005
Bonjour Olivier,
je pense que ... you need two more constraints. You wrote "kinda sudoku", so was there anything further required implicitely?
Posts: 120
Threads: 19
Joined: Nov 2006
I'm completely sorry...
Please replace "+" by "x"
I thought I was unable to count. I can't type either...
Posts: 1,619
Threads: 147
Joined: May 2006
Is this what the problem looks like?
....
 a  b  c  = 96
++
 d  e  f  = 315
++
 g  h  i  = 12
''''
\ \ \
\ \ \> = 126
\ \> = 40
\> = 72
Posts: 882
Threads: 23
Joined: Jan 2005
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
Posts: 120
Threads: 19
Joined: Nov 2006
Yes it does look like this
Posts: 120
Threads: 19
Joined: Nov 2006
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?
Posts: 1,619
Threads: 147
Joined: May 2006
Was one of the constraints that you can only used each digit once (like sudoku)? If so I think you have the correct answer.
Posts: 776
Threads: 25
Joined: Jun 2007
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.
Posts: 120
Threads: 19
Joined: Nov 2006
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.
Posts: 1,619
Threads: 147
Joined: May 2006
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.
Posts: 120
Threads: 19
Joined: Nov 2006
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?
Posts: 1,619
Threads: 147
Joined: May 2006
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?
Posts: 120
Threads: 19
Joined: Nov 2006
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
Posts: 1,619
Threads: 147
Joined: May 2006
Needs to be >=, not just >. You also need to state somehow that each variable is unique.
Posts: 562
Threads: 27
Joined: Oct 2006
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.
Posts: 776
Threads: 25
Joined: Jun 2007
"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.
Posts: 1,792
Threads: 62
Joined: Jan 2005
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 moreintelligent means was discussed in this recent thread:
http://www.hpmuseum.org/cgisys/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 linearalgebra techniques can't be used to simplify the problem, because the problem isn't linear (whereas a standard sudoku puzzle is).
 KS
Posts: 120
Threads: 19
Joined: Nov 2006
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.
