How to speak the problem? - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: How to speak the problem? (/thread-117053.html) |
How to speak the problem? - Olivier TREGER - 06-21-2007 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:
In each box a number (left to right, top to bottom) such as: 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 Re: How to speak the problem? - Monte Dalrymple - 06-21-2007 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? - Walter B - 06-21-2007 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? - Olivier TREGER - 06-21-2007 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? - Egan Ford - 06-21-2007 Is this what the problem looks like?
.---.---.---. Re: How to speak the problem? - Massimo Gnerucci (Italy) - 06-21-2007 I believe the solution is: 4 * 4 * 6 = 96 (2*2*2*2*2*3)
Re: How to speak the problem? - Olivier TREGER - 06-21-2007 Yes it does look like this
Re: How to speak the problem? - Olivier TREGER - 06-21-2007 That's one solution.
Mine was:
But my question was: how to create a model that would solve the problem?
Re: How to speak the problem? - Egan Ford - 06-21-2007 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? - Dave Shaffer (Arizona) - 06-21-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.
Re: How to speak the problem? - Olivier TREGER - 06-21-2007 Quote: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? - Egan Ford - 06-21-2007 Quote: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? - Olivier TREGER - 06-21-2007 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? - Egan Ford - 06-21-2007 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? - Olivier TREGER - 06-21-2007 Quote:I just tried: {a,b,c,d,f,g,h,i}<9with no success either Re: How to speak the problem? - Egan Ford - 06-21-2007 Needs to be >=, not just >. You also need to state somehow that each variable is unique.
Re: How to speak the problem? - Allen - 06-21-2007 Using this 48/49/50 program you can find the Divisors of each number:
So you can conclude that: Step 1
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? - Dave Shaffer (Arizona) - 06-21-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 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.
Multiplicative sudoku - Karl Schneider - 06-22-2007 Quote: 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? - Olivier TREGER - 06-22-2007 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.
|