Step by step analytical solution of a 9x9 “very difficult”
Author 
Message 
clm
Posted on: Fri Apr 20, 2012 10:00 pm
Posts: 668 Joined: Fri May 13, 2011 6:51 pm

Step by step analytical solution of a 9x9 “very difficult”
Step by step analytical solution of a 9x9 “very difficult”. The tuesday’s 9x9 is usually the more difficult calcudoku during the week. They come with different shapes requiring different techniques.This is the 9x9 difficult (tuesday Apr 17, 2012), Puzzle id: 449057, solving rate 117.4. Our purpose is using only the analysis. The strategy we will apply in this model will consist of determining the four cells coloured in blue (graphic 1, in some way these cells behave like 4 simultaneous “gravity centers”, deciding the solution, and we will see how as soon as these cells are determined there will be no need of obtaining the possible combinations for the cages “23+”, “20+”, “25+”, “19+” or “24+”, even the cage “1296x” will not be relevant in the solution process, and no “guessing” or many “trial and error” will be necessary, everything will come straight forward): First (graphic 2) we write all known numbers and candidates. The cage “4“ must contain the 7 of column “i” since 7 is not a divisor of 3456 or 240; initially “5” could be [2,7] or [4,9] but we will see inmediately that it must be [2,7]. We determine the “parity” of the cage “3456x”. This cage has two possibilities: [1,6,8,8,9] and [2,4,6,8,9] (combinations containing a 3 are not considered due to d1 and e2). Looking to the four upmost rows, applying the parity rule, we find that this cage must be odd, then: “3456x” = [2,4,6,8,9] with a sum of 29 (the other combination has a sum of 32). In these conditions, naming s1 and s2, respectively, the “addition value” of the cages “5” and “2” we have: s1 + s2 = 180 (4 rows)  23  20  3  5  6  13  7  17  29  25  9 = 23. Now we see the reason for “5” = [2,7], because [4,9] >>> “2” (+) = 23  13 = 10, being the maximum value inside the cage 6, but [1,3,6] or [2,2,6] are both invalid. With “5” = [2,7] (a sum of 9), “2” (+) = 23  9 = 14 so “2” = [1,5,8], [2,4,8] (the maximum number inside is an 8, and there are two valid possibilities, shown in the graphic). We will now obtain the possible combinations for the other products (as commented, to solve the puzzle we would not really need the combinations for “1296x” but having them will be useful just to “verify” the product of the numbers found during the solution process) (in parentheses the “addition value”, the sum of each combination): “40x” = [1,5,8] (14), [2,4,5] (11); “112x” = [2,7,8] (17), [4,4,7] (15); “240x” = [1,1,5,6,8] (21), [1,2,3,5,8] (19), [1,2,4,5,6] (18), [1,3,4,4,5] (17), [2,2,3,4,5] (16); “1296x” = [2,8,9,9] (28), [3,6,8,9] (26), [4,4,9,9] (26), [4,6,6,9] (25). Let’s start with “112x” = [4,4,7]. This combination is quickly analyzed as non valid because it forces two 9’s in row 5 (graphic 3, numbers in red colour): “112x” = [4,4,7] >>> “40x” = [1,5,8] >>> g7 = 8 >>> f7f8 = [1,5] >>> f5 = 9; and “112x” = [4,4,7] >>> “2” = [1,5,8] >>> c3 = 1 >>> d2d3 = [5,8] >>> d5 = 9. Note 1: There is another easy way (if we do not “see” that double 9 produced in row 5) of concluding that d (= g7) can not be an 8: The cage “240x” = [1,1,5,6,8] (21), [1,2,3,5,8] (19), [1,2,4,5,6] (18), [1,3,4,4,5] (17), [2,2,3,4,5] (16). The first two combinations can be supressed because they contain an 8 (due to e8 = 8 and f9 = 8); [1,3,4,4,5] would require g8 = 4, h9 = 4 and there is no way of placing a 1 in the cage due to the 1’s in d9 and i3i4; so we are left with [1,2,4,5,6] (18) and [2,2,3,4,5] (16). But, considering the three righmost columns which sum must be 135: b + d + “240x” (+) = 135  29  25  9  9  4  19  10 = 30, then, if “240x” (+) = 18 >>> b + d = 12, now if d = 8 >>> b = 4 (impossible, there are already three 4’s in the involved columns); and, if “240x” (+) = 16 >>> b + d = 14, then if d = 8 >>> b = 6 in conflict with the 6 in e3.
Note 2: An alternative way to start the analysis is seeing that [2,2,3,4,5] (16) is not possible in any case. The reason is: b + d = 14 >>> d = 5, b = 9 (since d = 6, b = 8, obviously, is not valid) but d = 5 >>> f7f8 = [2,4] and now “112x” becomes impossible, either the [4,4,7] or the [2,7,8], this last because three 2’s would be present in rows 7, 8 and 9, one in “40x” and the other two in [2,2,3,4,5] according to the hypothesis. This means that, necessarily, “240x” = [1,2,4,5,6] (18) with b + d = 12 (later we will easily determine b and d). It’s easy to verify that this alternative way quickly drives to the main line we have followed. Consequently “112x” = [2,7,8]. Now, since there is an 8 in c7 or d7, “40x” = [2,4,5], being now impossible the combination [1,5,8]. The combinations for the cages “112x” and “40x” have been defined, though the position of the numbers is still pending. From this point we can extract a simple and interesting equation (see graphic 4). Let’s look to the area shadowed in yellow, which is composed of the three central columns plus the cells c3 (that we have named “a” for simplicity), g3 (named “b”), c7 (named “c”) and g7 (named “d”); being 135 (3 x 45) the sum of all numbers in the three central columns, we have: a + b + c + d + 135 = 3 + 5 + 7 + 14 + 6 + 17 + 13 + 15 + 15 + 17 + 9 + 11 + 1 + 15 + 8; that is: a + b + c + d + 135 = 156; then a + b + c + d = 21where a, b, c, d are initially unknown, though our strategy would be to determine each of those values “a”, “b”, “c” and “d”, or in other words, determining the cells c3, g3, c7 and g7. An inmediate consequence (graphic 4) of “112x” = [2,7,8] and “40x” = [2,4,5], and as explained in Notes 1 and 2, is that we can define the only valid combination for the cage “240x” = [1,2,4,5,6] (18) (two additional 2‘s would not be possible in three rows). This permits, as explained, to calculate b + d, considering the three righmost columns, which total sum is 135; we find: b + d + 29 + 25 + 9 + 9 + 4 + 19 + 10 + 18 = 135 >>> b + d = 12 >>> a + c = 9. * * * * * * Comment: If we like so, we can also calculate the addition value of “1296” considering the four bottom rows which total sum must be 180. That is: “1296x” (+) = 180  7  24  15  17  1  9  15  11  8  19  10  18 = 26. Only [3,6,8,9] and [4,4,9,9] have a sum of 26, but the second is not valid with that Lshape so it follows that “1296x” = [3,6,8,9]. Additionally, and considering the three leftmost columns, which total sum must be 135, we would again obtain: a + c = 135  23  20  9  8  9  7  26  24 = 9. * * * * * * Let’s continue with the graphic 5 (below): For a + c = 9 we would have the pairs [1,8], [2,7], [3,6] and [4,5]. We can see that a = 2, c = 7 (and not inversely) is not valid (this would generate two 8’s in column d, since we are assuming “2” = [2,4,8]); clearly a = 3, c = 6 is impossible; also a = 5, c = 4 (and not inversely) is not valid because d2d3 cann’t be [1,8] due to d9 = 1 (in this case we would be assuming “2” = [1,5,8]). We have arrived to the pair 18 with a = 1 and c = 8. For b + d = 12 we have the pairs [3,9], [4,8] and [5,7]. The pairs [3,9] (3 or 9 cann’t go in “40x”) and [4,8] (now 8’s in rows 3 and 7 in addition to the fact that there are already three 4’s in the three righmost columns) are not valid so we are left with the pair [5,7] with b = 7 and d = 5. In this moment, with those four “key cells” determined, we could say that the puzzle is practically solved since the rest is very easy. However we will complete the process. Next (graphic 6, in light green colour): d2 = 8, d3 = 5; f2f3 can only be [1,9] (f2 =1, f3 = 9) >>> f5 = 5 >>> d5 = 9 >>> e5= 1 and then d4d6 = [4,6]. Also, g8 = 1 (due to d9 and i4). Another interesting thing to observe now is that considering the two upmost rows, which sum must be 90, we have: p (cell b2) + q (cell h2) = 90  23  3  8  5  7  1  29 = 14 >>> b2h2 = [5,9]. Now the 9 of column i must go to i1 (it’s not a divisor of “240x”). Then a 9 (and simultaneously a 3) cann’t be in a1 or a2 (column a) so a8a9 = [3,9] >>> a1a2 = [4,5] and because of b2h2 = [5,9] >>> a1 = 5, a2 = 4. And we observe that the 4 and the 8 present in row 2 and column i force the pair g1h1 = [4,8] required inside the cage “3456x”. We can complete row 1 with b1 = 1, c1 = 6. Also, in cage “23+”, c2 = 7 (c2 is anyway the only free place for the 7 in row 2). It is clear that g3 = 7 >>> a4 = 7, a3 =2. To continue from this point (graphic 7, in dark green) we see, i.e., that d4 = 4 is not valid since the difference of 9 for the cage “13+” can not be done with 18, 27, 36 or obviously 45 so d4 = 6 >>> d6 = 4 >>> e4 = 4 >>> e6 = 5; also f6 = 6 and f4 = 3. Continuing with the numbers in dark green: a6 = 1, a7 = 6; c5 = 2, b5 = 7; the 4 in i5 forces the 4 in “240x” to be in g9 or h9 consequently the 4 of column c must go to c8 >>> f8 = 2, f7 = 4 and inmediately d8 = 7, d7 = 2. In row 3 we need a 3 and a 4 but we know that a 4 is not possible in h3 (4‘s in “3456x”, i5 and “240x”) >>> h3 = 3, b3 = 4; h3 = 3 >>> g5 = 3, h5 = 6. Numbers in orange colour. Since b9 + c9 = 24  3  9  4 = 8 and since [1,7] and [2,6] are not possible (this last because the 2 and the 6 should go “together” to i8 in “240x”) we conclude that b9c9 = [3,5] >>> a8 = 3, a9 = 9 and, additionally, i8 = 5. Numbers in violet colour. Row 7: the 1’s in b1 and i4 force h7 = 1; additionaly, even without knowing that a 7 is not a divisor of “1296”, b7 = 3 (because of b5 = 7) and i7 = 7 >>> i6 = 3. Row 8: h5 = 6 >>> b8 = 6, h8 = 9. As a consequence h2 = 5 and b2 = 9. Row 9: b7 = 3 >>> b9 = 5, c9 = 3. The rest is straight forward. Numbers in red colour. Row 4: b4 + c4 = 7 = [2,5] >>> b4 = 2, c4 = 5; g4 + h4 = 17 = [8,9] >>> g4 = 9, h4= 8; Row 6: g6 + h 6 = 9 = [2,7] >>> g6 = 2, h6 = 7. And we finish with the numbers in light blue. Row 1: h4 = 8 >>> g1 = 8, h1 = 4; Row 2: g6 = 2 >>> g2 = 6, i2 = 2; Row 6: b2 = 9 >>> b6 = 8, c6 = 9. Finally g9 = 4, h9 = 2, i9 = 6. Obviously “1296” = [3,6,8,9] is among the obtained combinations but we have not used this. The “official” solution:




arjen
Posted on: Sat Apr 21, 2012 10:03 am
Posts: 48 Joined: Sun Oct 16, 2011 10:58 am

Re: Step by step analytical solution of a 9x9 “very difficul
Excellent, I restarted 2 times.
I'm curious to see statistics. A graph of the last month with the lines started / finished / solver rating.
@Patrick, when you are bored .... :)




pnm
Posted on: Sat Apr 21, 2012 10:30 am
Posts: 1910 Joined: Thu May 12, 2011 11:58 pm

Re: Step by step analytical solution of a 9x9 “very difficul
arjen wrote: I'm curious to see statistics. A graph of the last month with the lines started / finished / solver rating.
@Patrick, when you are bored .... :) Interesting though. But at the moment I'm not logging when a puzzle is started (I can see of course when it's loaded, but not if/when someone starts entering numbers)(so I maybe I should log that fact :)




jomapil
Posted on: Sat Apr 21, 2012 1:58 pm
Posts: 246 Location: Lisbon, Portugal Joined: Sun Sep 18, 2011 5:40 pm

Re: Step by step analytical solution of a 9x9 “very difficul
Clm, a pretty and clean analytical solution. In short, we must " transform " the products in sums and calculate a,b,c,d values. Thanks for your solution.
_________________Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.




jomapil
Posted on: Sat May 12, 2012 12:31 pm
Posts: 246 Location: Lisbon, Portugal Joined: Sun Sep 18, 2011 5:40 pm

Re: Step by step analytical solution of a 9x9 “very difficul
At the beginning it looked like I must do many "trial and error" to solve the 9x9 of today (12May2012). But, after all, as far as I remember it was the first time I solved a 9x9 puzzle 100 % analytically. Has anyone any explanation about some characteristic of this puzzle that permitted that? ( It's only a curiosity of mine ).
_________________Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.




jomapil
Posted on: Wed May 16, 2012 12:33 pm
Posts: 246 Location: Lisbon, Portugal Joined: Sun Sep 18, 2011 5:40 pm

Re: Step by step analytical solution of a 9x9 “very difficul
Clm: For the second time in less than a week I solved the 9x9 puzzle of today, exclusively by analytic and logical means ( in part due to your advices ). But the 9x9 of yesterday ( 15May2012 ) I used many trials and errors and it took many hours to complete ( with many restarts due to the mistakes ). So, it looks like many diagrams are not possible to use only analytical methods, isn't it?
_________________Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.




clm
Posted on: Wed May 16, 2012 6:09 pm
Posts: 668 Joined: Fri May 13, 2011 6:51 pm

Re: Step by step analytical solution of a 9x9 “very difficul
jomapil wrote: Clm: For the second time in less than a week I solved the 9x9 puzzle of today, exclusively by analytic and logical means ( in part due to your advices ). But the 9x9 of yesterday ( 15May2012 ) I used many trials and errors and it took many hours to complete ( with many restarts due to the mistakes ). So, it looks like many diagrams are not possible to use only analytical methods, isn't it? First of all congratulations for the two analytical solutions, on May 12 and May 16, we are in the good way. But I think that probably all diagrams, though difficult, can be solved with analytical methods, according to my previous assertion of: "If a calcudoku has a unique solution, it can be solved using only analytical means" (thread "A 6x6: Is the analysis enough to solve a calcudoku?"). This is not a theorem (it must be demonstrated and this demonstration is still pending). The yesterday's case, May 15, 2012, is not an exception, in my opinion. It's more difficult than usual, as every tuesday, of course. As it's a large 9x9 it will require several graphics and some time. I will try to send the step by step solution in the following days, opening a separate thread (in this same section "Solving strategies and tips"), in order to separate the discussion from this thread, which is more related to the 9x9 on tuesday Apr 17, 2012.




jotempe
Posted on: Thu May 17, 2012 12:03 am
Posts: 31 Joined: Mon Mar 05, 2012 12:45 pm

Re: Step by step analytical solution of a 9x9 “very difficul
clm, as I have already written elsewhere, the validity of your assertion depends on your definition of "analytical solution". Look e.g. at "Note 1" and "Note 2" in the solution that you started the thread with. They essentally say someting like: 'it could be either x or y. However if this were x, then we would have a, and ths would lead to b, which is contradictory, because of c. So it must be y'. Now, a purist will tell you, that this is a reductio ad absurdum proof, or, in plain English, a trial and error method, only that you performed the entire trial "in your mind", without putting any numbers in the diagram  as you have good enough memory to "see" the diagram with them in. So, the question is "how many numbers can be put in the diagram when considering a hypothesis, before you stop calling it anaytical solution?"




jomapil
Posted on: Thu May 17, 2012 8:56 am
Posts: 246 Location: Lisbon, Portugal Joined: Sun Sep 18, 2011 5:40 pm

Re: Step by step analytical solution of a 9x9 “very difficul
Jotempe, in the end it looks like there will be ALWAYS " trial and error " ( TAE ). But what Clm intends to say is that we can reduce this TAE at a minimum of times. And the remaining few times we use TAE we can use them in a smarter way so as to mask that TAE component. Will it be so?
_________________Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.




clm
Posted on: Thu May 17, 2012 4:24 pm
Posts: 668 Joined: Fri May 13, 2011 6:51 pm

Re: Step by step analytical solution of a 9x9 “very difficul
jotempe wrote: clm, as I have already written elsewhere, the validity of your assertion depends on your definition of "analytical solution". Look e.g. at "Note 1" and "Note 2" in the solution that you started the thread with. They essentally say someting like: 'it could be either x or y. However if this were x, then we would have a, and ths would lead to b, which is contradictory, because of c. So it must be y'. Now, a purist will tell you, that this is a reductio ad absurdum proof, or, in plain English, a trial and error method, only that you performed the entire trial "in your mind", without putting any numbers in the diagram  as you have good enough memory to "see" the diagram with them in. So, the question is "how many numbers can be put in the diagram when considering a hypothesis, before you stop calling it anaytical solution?" I understand by "analytical" solution when the known "analytical" tools are being used once "studied" and "understood". Clearly it is not possible to enterely "read" the puzzle (i.e., a 9x9) from the beginning so you must use methods to define the correct things and advance step by step, in this context there is no big difference if you use your memory (keeping the possibilities in mind) until some point (like in chess) or if you write the numbers in the paper or the screen. And if you make a "failure" in a written exposition, something that looks like a "guessing", that is mainly your fault, but it does not invalidate the original assertion. I think that as a puzzler uses more and more analytical tools probably will use less TAE. I am not against TAE, of course, by definition the "reductio ad absurdum" (or the TAE) is part of the "scientifical method" (in exact or empiric sciences ) and it's very good if it permits to find the solution since finding the solution is the target and it's always better than not arriving to any conclusion. What I say (in the line of the jomapil's explanation) is that it is possible (because the calcudoku, if it has a unique solution, should be like an "exact science", with a finite number of equations or relationships) to arrive to the solution using "only" analytical means; but this "only", here in the Forum, has always opened the debate. What is the meaning of "only"?. Logically, we must take decisions all the time among several possibilities, but this is analysis, if we base them in the logic, no matter the number of branches or possibilities (let's say within some reasonable limit, of course) being considered. For the practical situations, with the calcudokus, I understand by pure TAE when, let's say, we just proceed in this way: "OK, let's put a 5 here and see what happens; then if after 20 or 25 numbers entered everything crashes, we start again", we can loose hours with this procedure and we will never be sure where we are. I insist that it is better not using numbers "randomly" and without a base, but instead using the known tools and building logic hypothesis "from the beginning" of the solution process (and during the full process as well) and get accustomed to this method. As the puzzler is more skilled in these analytical tools they will become more clear and useful, I think.






You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum

