| View previous topic :: View next topic |
| Author |
Message |
nataraj
Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria
|
 Posted: Thu Jul 23, 2009 8:21 pm Post subject: Nataraj's Simple World of Strong and Weak Links |
 |
|
Nataraj's Simple World of Strong and Weak Links
Simple? At least I hope so. No mathematics, no algebra.
Find some very basic relationships. Put them together.
Arrive at useful eliminations (hopefully).
Not magic at all. As simple as breathe in, breathe out. 
Part 1: links, shorthand, and chains.
(plus: a different look at box/line interaction and naked pairs)
Of strong-men and weak-lings
A "link" connects two statements about candidates in cells.
(Statements can be true or false. Most of the time, we don't know which)
Such a statement might be: r2c4 is "5", in shorthand notation: (5)r2c4
Another statement could be: r2c6 is "5", or in shorthand: (5)r2c6
Let us connect two such statements.
A "strong" link means, that at least one of the two statements is true.
In shorthand notation: statement_1 = statement_2 (the "=" symbol in this case has NOTHING to do with EQUAL)
A "weak" link means, that at most one of the two statements is true.
In shorthand: statement_1 - statement_2 (the "-" symbol has NOTHING to do with MINUS)
No, I did not invent the symbols.
An example:
| Code: | +----------+-----------+---------+
| 13 12 23 | 689 27 18 | 679 4 5 |
| 45 45 6 | 479 17 . | . . . |
| 7 8 9 | . . . | . . . |
+----------+-----------+---------+ |
Consider the two statements: "r2c1 is 4" and "r2c4 is 4".
Is it possible that they can both be true?
Nope. At most one of them can be true. There cannot be two "4"s in row 2.
This is what a weak link means.
Let's write it down in shorthand: (4)r2c1-(4)r2c4
How about "r1c4 is 6" and "r1c4 is 8" ?
Again, they cannot be both true. Another weak link: (6)r1c4-(8)r1c4
What about "1" in r1c1 and r1c2?
Clearly, they cannot both be true. Definitely a weak link (1)r1c1-(1)r1c2
But, since in box 1 there are no other cells with "1", one of them must be "1".
There is also a strong link between the two statements: (1)r1c1=(1)r1c2.
Another one:
"r2c1 is 4" and "r2c1 is 5". Clearly, again a weak link, they cannot both be true.
shorthand: (4)r2c1-(5)r2c1
But there are only two candidates in cell r2c1. So, at least one of the two statements must be true:
There is also a strong link: (4)r2c1=(5)r2c1.
Many times, in real sudokus, a strong link also is a weak link.
Like, for example, a cell with only two candidates, like r2c5 above,
or two occurences of one candidate in a house like the "7"s in row 1.
--------------------
Nifty things one can do with strong and weak links
A) direct elimination:
Every candidate that "sees" both ends of a strong link can be removed.
Wow, nice. But, what does "see" mean ?
For like candidates, it means: share a house (row, column, box)
For different candidates, it means: share a cell
In our example, "1" in r1c6 sees "1" in r1c1 and "1" in r1c2.
We have already found out that (1)r1c1=(1)r1c2.
Therefore, we can remove "1" from r1c6 (this box/line interaction is very common)
B) daisy chaining
Links that have one end in common can be chained together.
It is only useful to chain links of alternating type. Like this:
strong link,weak link, strong link, .... (like: breathe in, breathe out, breathe in ...)
If both ends of such a chain are of the same type, the two ends of the chain form a new link of exactly that type.
Again, it is only useful to look at chains with strong links at both ends.
(BTW, it is rather common to call the end statements "pincers")
Whoa, wait a minute ... run that by me again !
Let's look at our example again
| Code: | +----------+-----------+---------+
| 13 12 23 | 689 27 18 | 679 4 5 |
| 45 45 6 | 479 17 . | . . . |
| 7 8 9 | . . . | . . . |
+----------+-----------+---------+ |
Look at cell r2c1. We already know that there is a strong link (4)r2c1=(5)r2c1
By the same argument as before, we can verify that there is also a strong link in the neighbouring cell (4)r2c2=(5)r2c2
(Why? Since there are only two candidates, at least one of them must be true)
What about the "4"s in r2c1 and r2c2 ? Certainly, at most one of them can be true.
So, we have a weak link: (4)r2c1-(4)r2c2.
Let's daisy chain those links, and remember, links have no inherent direction, they can be reversed !
Why? We never talked about "first" or "second", but only about "one of them"
We have:
(5)r2c1=(4)r2c1
(4)r2c1-(4)r2c2
(4)r2c2=(5)r2c2
Together: (5)r2c1=(4)r2c1-(4)r2c2=(5)r2c2
strong, weak, strong.
Both end links are of the same type (strong), so we can make a new link (of type "strong") out of the end statements:
(5)r2c1=(5)r2c2
And, as with all strong links, we can remove all "5"s from those cells that see both ends  (this "naked pair" pattern is also very common)
One more example
Again, in this grid:
| Code: | +----------+-----------+---------+
| 13 12 23 | 689 27 18 | 679 4 5 |
| 45 45 6 | 479 17 . | . . . |
| 7 8 9 | . . . | . . . |
+----------+-----------+---------+ |
Look at row 1, more specifically: the sixes and nines.
There are only two "6"s in row 1, that means we have a strong link:
(6)r1c4=(6)r1c7
And, there are only two "9"s:
(9)r1c4=(9)r1c7
Within one cell, only one candidate can be true, therefore two weak links:
(6)r1c4-(9)r1c4 and
(6)r1c7-(9)r1c7
Shall we daisy-chain them? Remember to start with a strong link.
(6)r1c4=(6)r1c7-(9)r1c7=(9)r1c4
We can take out the middle and leave only the end statements. This gives
(6)r1c4=(9)r1c4
And all candidates that see both ends are toast. Is there such a candidate?
Sure: candidate "8" in r1c4.
We have found out, that r1c4 cannot be 8.
Very similar result, if we start with a different strong link:
(6)r1c7=(6)r1c4-(9)r1c4=(9)r1c7, shortened to:
(6)r1c7=(9)r1c7 and this means r1c7 cannot be "7".
This "hiddden pair" pattern is very common.
------
That's it for today.
My simple world, part 1. |
|
| Back to top |
|
 |
nataraj
Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria
|
| Posted: Sat Jul 25, 2009 9:29 am Post subject: Part 2: Connect the Dots - The Magic Appearing Act |
|
|
Part 2: Connect the Dots - The Magic Appearing Act
So far, the concept of links, be they strong or weak, has not helped us a lot.
"Hey, come on, the so called 'sorthand' is confusing as hell, '=' is not equal, gimme a break!
We know how to use naked pairs and hidden pairs, we know all about box/line interactions.
And, looking at the grid with pencilmarks and all, I cannot see any links or chains, let alone daisy chains..."
Right. Neither can I.
And when I solve sudokus, I never use the notation at all.
Bear with me for another 5 minutes, OK?
A picture is worth a thousand words.
This is the stage in the June 27, 2009 DB puzzle (from the "other puzzles" section), where there are no more basic moves.
| Code: |
+--------------------------+--------------------------+--------------------------+
| 6 249 7 | 5 3 89 | 248 1 28 |
| 58 259 1 | 6 7 4 | 3 259 258 |
| 458 3459 38 | 1 2 89 | 7 459 6 |
+--------------------------+--------------------------+--------------------------+
| 2 8 5 | 7 1 3 | 9 6 4 |
| 3 7 6 | 9 4 5 | 12 8 12 |
| 9 1 4 | 8 6 2 | 5 7 3 |
+--------------------------+--------------------------+--------------------------+
| 1457 345 9 | 24 8 6 | 124 2345 1257 |
| 78 45 2 | 3 9 1 | 6 45 78 |
| 148 6 38 | 24 5 7 | 1248 234 9 |
+--------------------------+--------------------------+--------------------------+
|
For the magic appearing act, draw a simple grid on a piece of paper, like this one (leftmost diagram:)
Then, concentrate on one candidate. Let's say "4".
In your grid, make a dot wherever there is a "4" in the pencil marks (middle diagram)
Then, try to spot those houses that contain exactly two such dots.
In this case, row 1, box 3, row 8 and column 4/box 8
Connect the two dots by a line. (rightmost diagram)
Somehow, almost effortlessly, the strong links have appeared on the paper. 
What we have just created, is a plot of all strong links that contain only statements about candidate "4":
(4)r1c2=(4)r1c7 (which reads: in row 1, "4" must be in column 2 or column 7)
(4)r8c2=(4)r8c8 (in row 8, "4" must be in column 2 or column 8 )
(4)r1c7=(4)r3c8
(4)r7c4=(4)r9c4
What about the "weak" links ?
Remember, we said that weak links connect statements that cannot both be true ?
In the diagram, this applies to all dots that "see" each other.
There are too many of them, so we will not draw lines for each weak link.
But, ...
since we need a chain of strong link, weak link, strong link, ... anyway,
lets look at the ends of our strong link lines in the diagram and find those that see each other.
In the first row, the left end of the line (col 2) "sees" the left end of the line in row 8.
Great!
"sees" can be written as a weak link: (4)r1c2-(4)r8c2
and the chain can be written like this (from now on, since we are looking only at candidate "4", we write the "4" in front of the chain)
4: r1c7=r1c2-r8c2=r8c8
which can be shortened to: (4)r1c7=(4)r8c8
This strong link means that at least one of r1c7 and r8c8 is "4", and therefore
all cells that see both r1c7 and r8c8 cannot contain "4".
We can remove "4" from r7c7, r9c7 and r3c8. Not bad at all ....
The pattern (two parallel lines that "see" each other) is so common that is has a name: "skyscraper".
We are not done yet. Just for completeness' sake, notice that the right end of the line in row 8 sees the lower end of the line in box 3.
(4)r3c8-(4)r8c8
The chain looks like this
4: r1c7=r3c8-r8c8=r8c2
which can be shortened to: (4)r1c7=(4)r8c2
this means that cell r2c2 cannot contain "4", since it sees both ends of the strong link
---------
What if we had selected candidate "5" instead of "4" ?
Let's prepare our diagram again. A dot for every "5" in the pencil marks:
Again, look for those houses that have exactly two fives.
These are: row 8 and column 9. Connect the dots.
Two strong links:
(5)r2c9=(5)r7c9
(5)r8c2=(5)r8c8
Look at the ends of the lines. Do they "see" each other?
Yes, the lower end of the line in column 9 sees the right end of the line in row 8. There is a weak link:
(5)r7c9-(5)r8c8
Daisy chain (remember, always start with a strong link)
5: r8c2=r8c8-r7c9=r2c9
shortened to:
(5)r8c2=(5)r2c9
Is there a cell that sees both ends of this strong link?
Yes. we can remove "5" from cell r2c2
This pattern - one horizontal line and one vertical line connected by a box - is common enough to have a name: "kite"
-------------------------------------------------------
There is one more interesting candidate.
Look at "8" and prepare the grid.
A dot for every "8".
Look at those houses that have exactly two eights.
Connect the dots.
This is how it should look like:
Two of those many strong links stand out:
they are parallel (like in a skyscraper) and of the same length, one exactly above the other:
rows 2 and 8. The strong links are:
(8)r2c1=(8)r2c9 (read: in row 2, "8" must be in col 1 or in col 9)
(8)r8c1=(8)r8c9 (read: in row 8, ....)
since both ends see each other, there are two weak links we can use:
(8)r2c1-(8)r8c1
(8)r2c9-(8)r8c9
There are two possibilities to chain the strong links, either by connecting the left ends or by connecting the right ends.
A:
8: r2c9=r2c1-r8c1=r8c9, shortened to (8)r2c9=(8)r8c9
B:
8: r2c1=r2c9-r8c9=r8c1, shortened to (8)r2c1=(8)r8c1
Those two newly created strong links eliminate all "8"s from cells r3c1,r9c1 and r1c9
This pattern - two parallel lines of equal length, perfectly aligned - is common enough to have a name: "x-wing"
_________________________________________________
Enough for now, next time we will look at longer chains. |
|
| Back to top |
|
|
|
|
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
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
