View unanswered posts | View active topics It is currently Fri Aug 01, 2014 7:47 am



← Back to the Calcudoku puzzle page




Reply to topic  [ 10 posts ] 
 The parity 
Author Message

Posted on: Thu Jun 09, 2011 6:37 am




Posts: 576
Joined: Fri May 13, 2011 4:51 pm
Post The parity
Basic strategies (perhaps trivial but may be useful to someone).
Second rule: The parity (a powerful tool for puzzles like the difficult 7x7 only subtractions on wednedays, etc.).

The addition of all numbers in any row or column can be even (10, 28, 36, 78 for the 4x4, 7x7, 8x8 and 12x12) or odd (15, 21, 45, 55, 153 for the 5x5, 6x6, 9x9, 10x10 and 17x17).
If we have a cage with n- the addition of all numbers inside must be even if n is even (we will call it “cage even”) and odd if n is odd (we will call it “cage odd”). For instance, in a cage of two cells with result 2-, both numbers inside must be even or both odd, and then the addition is even (7 and 5, 2 and 4, etc.). In a cage of two cells with result 3-, the two numbers inside must be of different parity, one odd and the other even, and the addition of both will be odd. Let’s now think in a three cells cage odd-, that is, a - b - c is odd; since a - b - c = a - (b+c), then “a” and “(b+c)” must be of different parity and consequently “a” + “(b+c)” = a + b + c is odd (for instance, 9-2-4 produces 3-, odd, 9+2+4=15, odd). Same demonstration applies to a three cells cage even-. Larger cages behave similarly since a - b – c – d… = a – (b+c+d…), etc.
Next step: The additon of all numbers inside two “cages odd” is even (and obviously if the two cages are even). Iterating this procedure and by comparing the result with the parity of the line or the “rectangle”, etc., we can determine the parity of individual cells (also knowing the parity of some subareas, like those with the x sign, we can eliminate combinations, etc.).
For instance, in the Jun 08 7x7 easy, the parity of the rectangle of the top 4 rows (excluding the cell d5) (observe that the 30x is an odd cage) is odd, so to complete the even parity (4x28) of the four rows, the cell d5 must be odd and “1” is the only possible value; e5 will then be 2. And now, checking the parity of the three bottom rows, the 12x in f1-g1 must be 4x3 (cage odd) and not 6x2 (cage even).


Profile

Posted on: Sat Jun 25, 2011 3:25 am




Posts: 8
Joined: Thu May 12, 2011 11:15 pm
Post Re: The parity
Thanks for this tip. I have put it use and has been a definite help.


Profile

Posted on: Mon Jun 27, 2011 5:50 pm




Posts: 576
Joined: Fri May 13, 2011 4:51 pm
Post Re: The parity
larryb33 wrote:
Thanks for this tip. I have put it use and has been a definite help.


Welcome. I arrived to that conclusion when looking for some "error detection" applicable to the lines (rows or columns) (as in the computer's world) but I quickly observed that it was an all-purpose tool that could eliminate combinations in cages of the type "x" or the ":". For me many times is the key in the 9x9's. The parity rule can be combined with the "maximums and minimums in the sum of cages"; for instance, if you have s1 + s2 + s3 = 50 (where s1, s2 and s3 can be of any type of cage including "x" or ":") and you are analyzing a combination of s3 = 19, then s1 + s2 is odd and equals 31, and s1 and s2 have of course opposite parity between them, and also the only possibilities are those "pairs" of combinations for s1 and s2 that give that total of 31, and we can proceed analyzing the effect over the rest of the puzzle.


Profile

Posted on: Mon Sep 19, 2011 4:50 pm




Posts: 248
Location: Lisbon, Portugal
Joined: Sun Sep 18, 2011 3:40 pm
Post Re: The parity
Hi, clm.

In your explanation you refer to the puzzle (Jun 08 7x7 easy).

How can I obtain this historic puzzle to better understand your explanation?

Thank you. Cheers.

_________________
Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.


Profile
User avatar

Posted on: Mon Sep 19, 2011 5:28 pm




Posts: 1480
Joined: Thu May 12, 2011 9:58 pm
Post Re: The parity
jomapil wrote:
In your explanation you refer to the puzzle (Jun 08 7x7 easy).

How can I obtain this historic puzzle to better understand your explanation?

clm wrote:
For instance, in the Jun 08 7x7 easy, the parity of the rectangle of the top 4 rows (excluding the cell d5) (observe that the 30x is an odd cage) is odd, so to complete the even parity (4x28) of the four rows, the cell d5 must be odd and “1” is the only possible value; e5 will then be 2. And now, checking the parity of the three bottom rows, the 12x in f1-g1 must be 4x3 (cage odd) and not 6x2 (cage even).

Here it is:
Image


Last edited by pnm on Thu Sep 22, 2011 12:46 pm, edited 1 time in total.



Profile

Posted on: Mon Sep 19, 2011 5:31 pm




Posts: 248
Location: Lisbon, Portugal
Joined: Sun Sep 18, 2011 3:40 pm
Post Re: The parity
Thank you, pnm.

Cheers.

_________________
Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.


Profile

Posted on: Mon Sep 19, 2011 5:42 pm




Posts: 248
Location: Lisbon, Portugal
Joined: Sun Sep 18, 2011 3:40 pm
Post Re: The parity
Excuse me, pnm, but I think you made a mistake. If I'm right that puzzle refers to 7x7medium20110608.

Cheers.

_________________
Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.


Profile

Posted on: Mon Sep 19, 2011 7:16 pm




Posts: 576
Joined: Fri May 13, 2011 4:51 pm
Post Re: The parity
jomapil wrote:
Excuse me, pnm, but I think you made a mistake. If I'm right that puzzle refers to 7x7medium20110608.

Cheers.


Hi, jomapil. The graphic is the correct one, the one I was referring to. I cann't remember now if it was the 7x7 easy or medium for that date, but sure Patrick found the correct one. It is not possible for the moment to recall an old puzzle using the Puzzle id (identification introduced "recently" by Patrick), only the last week's puzzles can be directly seen. When I sent the post we had not defined yet the labelling for the cells (actually agreed as in Excel, after the discussion in the Forum, that is, letters for the columns and numbers for the rows, although this has not been implemented yet in the page, ... perhaps in the future upon Patrick's time availability), so I used letters for the rows and numbers for the columns in that post. And at that time I was not yet uploading graphics (sorry for that) because for me the procedure was not clear, and only after a few e-mails with Patrick, I was able to do it.

This was a very easy example for "the parity" rule. The parity of that cell must be odd, and since a cage "2:" has only (in a 7x7) the combinations 1-2, 2-4 and 3-6, that cell must contain a "1" (there is a 3 already in the column) and the roommate is a "2". Now that you know the even parity of this second cell you may determine the parity of the cage "12x" = odd (so 3-4 and not 2-6), considering the parity of the three bottom rows (even, 3 x 28 = 84; here we must be careful because, i.e., three rows will have odd parity in the case of a 5x5, 6x6, 9x9, 10x10, ..., respectively 3 x 15, 3 x 21, 3 x 45, 3 x 55, ...).

We can apply "the parity rule" to practically all puzzles, in many situations, eliminating possibilities and focusing the candidates for the cells and/or cages. The utility will be more evident with the use.


Profile

Posted on: Mon Sep 19, 2011 8:18 pm




Posts: 248
Location: Lisbon, Portugal
Joined: Sun Sep 18, 2011 3:40 pm
Post Re: The parity
Thank you, clm, for your explanation and for the parity rule. At first sight it seems useful lowering the number of possibilities. I go to explore this concept in the next days and in the next puzzles.

Cheers and till the next.

_________________
Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.


Profile

Posted on: Mon Dec 02, 2013 7:51 pm




Posts: 576
Joined: Fri May 13, 2011 4:51 pm
Post Re: Some additional clarifications with respect to the parit
Some additional clarifications with respect to the parity rule.

Around two years and a half have elapsed since this concept was first introduced here in the Forum. Later, one year and a half ago, I sent another post to the section “Solving strategies and tips” named “5x5 **: The parity rule for children/beginners” with an example of how this rule could be applied to a 5x5 difficult. However, many new puzzlers have joined the site since then so my intention now is to refresh a little bit that initial idea and to help a little those who are not still using this concept either because they do not consider it useful or perhaps because they have not fully understood its meaning.

Ok, the idea is as follows: We start with a 2-cell cage “n-” where “n” is even, for instance, “4-”, in a 9x9 puzzle. To get an even difference you need both numbers to be simultaneously even or simultaneously odd, in this example [1,5], [2,6], [3,7], [4,8] or [5,9] (because if one is even and the other is odd the difference will be odd). Then if both have the same parity its sum will be even, either if they are both even or if they are both odd, in this example, for the cage “4-”, the sum would be 6, 8, 10, 12 or 14, respectively. And we say that this is an “even cage” (we define this as an “even cage”) because the sum of all numbers inside is even. We may not know the final numbers yet but we know that necessarily its sum will be even.

Now, lets consider a 2-cell cage “n-” where “n” is odd, for instance, “3-”, in a 9x9 puzzle. The numbers inside this cage must have different parity, one must be even and the other must be odd, because if both were even or both odd simultaneously the difference would be always even (but not odd). In this example the possibilities are [1,4], [2,5], [3,6], [4,7], [5,8] and [6,9], that is, one even number and one odd number. And being of different parity its sum will be odd, in our example, the sum would be 5, 7, 9, 11, 13 or 15, respectively. And we say that this is an “odd cage” because the sum of all numbers inside is odd. We may not know the final numbers yet but we can affirm that necessarily its sum will be odd.

This is the heart of the idea and soon we will see its utility. How is the sum of all numbers included in two “even” cages, for instance, “2-” and “4-”?: even plus even equals even. And the sum of all numbers contained in two “odd” cages, for instance, “1-” and “5-”?: it will be even since odd plus odd equals even. And if one of the cages is even and the other is odd, for instance, “6-” and “7-”?: the sum of all numbers within those two cages will be odd since even plus odd is odd.

Before applying this rule to any real situation we need to demonstrate something else: that the previous conclusions for the 2-cell cages can be extended to cages of any size. Really, this is quite simple: Suppose that we have a 4-cell cage “2-” in a 9x9 puzzle: a possibility would be, for instance, [1,2,4,9] because 9 - 4 - 2 - 1 = 2. Observe that we always depart from the higher number in the cage, 9 in this case, and we subtract the other numbers, but 9 - 4 - 2 - 1 = 9 - (4 + 2 + 1) (the introduction of the parenthesis is simply an arithmetic valid operation but in this way we convert the 4 numbers into 2 numbers by grouping all the small numbers in one), 9 and the value of the parenthesis must be of the same parity to get an even difference as exposed above (in this case both are odd, 9 and 7), consequently 9 and the value of the parenthesis have an even sum, that is, 9 + (4 + 2 + 1) must be even or, from another point of view, the sum of all numbers inside the cage is even (16 in this particular case) [since 9 + (4 + 2 + 1) = 9 + 4 + 2 + 1 removing now the parenthesis]; in summary, we say that “2-” is an “even” cage whichever is the number of cells; another possibility for that “2-” 4-cell cage, for instance, the combination [1,1,4,8]: 8 - 4 - 1 - 1 = 2 = 8 - (4 + 1 + 1), 8 and the value of the parenthesis must be of the same parity, both are even in this case (8 and 6) and, being of the same parity, its sum is even.

Lets go now with a 4-cell cage “n-”, where “n” is odd, to see that the sum of all numbers contained in the cage must be odd: a - b - c - d = a - (b + c + d), where “a” represents the higher number in the cage and “b”, “c” and “d”, the other numbers in the cage. Observe that “a” and “(b + c + d)” must necessarily be of different parity to produce an odd result and, consequently, a + (b + c + d) is odd, and this amount is equal to a + b + c + d (now removing the parenthesis) so the sum of all numbers within the cage is odd, and we say that we have an odd cage. An example with real numbers (just in case the use of letters may sound abstract): for a “3-” 4-cell cage, in a 10x10 puzzle, a possibility is the combination [2,2,3,10]: here 10 - 3 - 2 - 2 = 3, but 10 - 3 - 2 - 2 = 10 - (3 + 2 + 2) in which expression we see that 10 and the parenthesis (with a value of 7) have different parity what is a mandatory requirement to arrive to an odd difference, in this case the subtraction of 10 and 7 equals 3; consequently, if the parity of both things is different, when adding 10 and the parenthesis we will obtain an odd sum, 17 in this particular case. Another example, the combination [1,1,2,7] is another possibility for the cage “3-”: 7 - 1 - 1 - 2 = 3 = 7 - (1 + 1 + 2) where we see that 7 and the parenthesis (which value is 4) have different parity and its sum is odd: 7 + (1 + 1 + 2) = 7 + 4 = 7 + 1 + 1 + 2 = 11.

We have then arrived to the final conclusion: A cage “n-” is even if “n” is even and it is odd when “n” is odd (this happens always regardless of the numbers used to comply with the subtraction); or, expressed with different words, if “n” is even the sum of all numbers in the cage is even and if “n” is odd the sum of all numbers in the cage is odd.

Now the question is: What is the utility of all this?. Ok: because it can be applied to “innies”, “outies”, “multiplication” or “divison” cages, … , and to any number of rows or columns or areas (for instance, if the parity of the “inner area” is known, like in those 6x6’s when the corners are given, and we have a 4x4 "inner area", …), etc..

Applying the parity rule.

First example: Suppose, for instance, that in a 7x7 puzzle, like the subtraction only puzzle on Wednesdays, you have an “innie” cell in a line (row or column), you can determine the parity of this individual cell in this way: if you have in that line, for instance, three 2-cell cages, lets say “1-”, “2-” and “3-”, you know that the sum of the six numbers contained in these three cages is even, just by "adding" the parity of the three cages, even in this case, and, since the sum of all numbers in any line is 28 (addition rule in a 7x7 puzzle, 28 is the sum for evey row or column), the “alone” (innie) cell must be even = 28 - even. And this is very helpful, for instance, if the cage that contains this cell is “4-” you inmediately know that the cage must be [2,6] and you can write the candidates since [1,5] or [3,7] would always produce an odd number in that position and that‘s impossible.

Second example: Suppose that you have two columns (in a patterned 7x7) with individual cells and addition/subtraction cages (or, i.e., some well defined multiplication cages like a 3-cell “10x” or a 3-cell L-shape “25x”, “32x”, …) plus one “72x” 3-cell L-shape cage. Our purpose is to determine the parity of this last cage. You "iterate" the parity rule to the sum of the individual cells and those cages, consequently determining the parity of the sum of all the numbers involved and, since the parity of two complete columns is even in this case (in a 7x7 the sum of two columns is 2 x 28 = 56) you find the parity of the pending cage, the targeted multiplication cage “72x”: if that result is even the only valid combination is [2,6,6] and, if it is odd, the only valid combination is [3,4,6]. And now you can continue looking at or extending the procedure to the two rows (the perpendicular lines to the previous lines) containing that “72x” cage.

******

The parity rule will solve you many uncertainties in the day by day "Calcudoku job" and you will gain a lot of time not only when dealing with small puzzles but also with large puzzles. You will find its utility as soon as you start using it, specially in the 9x9's, the 7x7 subtraction only on Wednesday's, the actual 10x10 on Fridays to define, i.e., if "40x" is [4,10] or [5,8], that is, an even or an odd cage, the actual 8x8 medium on Sundays, most 5x5 difficult, etc..


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 10 posts ] 

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

Search for:
Jump to:  
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.