dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Grouped Coloring, and Grouped Strong Links

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
keith



Joined: 19 Sep 2005
Posts: 3150
Location: near Detroit, Michigan, USA

PostPosted: Sun Oct 26, 2008 8:10 pm    Post subject: Grouped Coloring, and Grouped Strong Links Reply with quote

When Marty asked the question about a definition of grouped coloring I looked, and was surprised to find very little. Here is my effort to write something down. This is a first draft. As always, comments and further contributions are welcome. Keith

If a candidate occurs only twice in a row, column, or box, the two cells in which it occurs are said to be a "strong link" in that candidate. Strong links are a fundamental building block of many Sudoku techniques. An excellent guide has been written by Havard: Strong Links for Beginners

Code:
Notation:  In the following,
.  Cell may be anything
*  Cell contains the candidate
/  Cell does not contain the candidate
@  Candidate is eliminated from this cell


Two strong links can be used to make an elimination. For example:

Code:
Diagram 1
/ * / |/ / / |/ * /
* / / |. . . |. . .
/ / / |. . . |. . .
------+------+------
/ . . |. . . |. . .
/ . . |. . . |. . .
/ . . |. . . |. . .
------+------+------
* . . |. . . |. @ .
/ . . |. . . |. . .
/ . . |. . . |. . .


Suppose * marks the only occurrences of a candidate in R1, C1, or B1. Then, that candidate can be eliminated in the cell marked @.

This is simple coloring. We can label the cells as "a" and "A":

Code:
Diagram 2
. A . |. . . |. a .
a . . |. . . |. . .
. . . |. . . |. . .
------+------+------
. . . |. . . |. . .
. . . |. . . |. . .
. . . |. . . |. . .
------+------+------
A . . |. . . |. @ .
. . . |. . . |. . .
. . . |. . . |. . .


In each strong link, either "a" or "A" is true. The sequence of cells aAaA is a "chain". Any cell that sees both a and A cannot be true (cannot contain the candidate).

Now, let's take a look at B1. What patterns are possible that still make the elimination in @? Well, you could have this:

Code:
Diagram 3
/ * * |/ / / |/ * /
* / / |. . . |. . .
* / / |. . . |. . .
------+------+------
/ . . |. . . |. . .
/ . . |. . . |. . .
/ . . |. . . |. . .
------+------+------
* . . |. . . |. @ .
/ . . |. . . |. . .
/ . . |. . . |. . .


The logic is: The candidate in B1 must lie in either R1 or C1. Either way, one of the candidates in B3 or B7 is true, and @ can be eliminated.

This is "grouped" coloring. The candidates in B1 can be grouped into those in R1 or those in C1. (in the last sentence, "or" rather than "and" is very important. The groups do not share candidates.) For the purposes of this chain, the cells in R1B1 and C1B1 act like a strong link.

It is important to note that "grouped" links only apply in the context of a particular chain.

In our coloring diagram, we can add two more strong links in R2 and C2, making an elimination in the cell labelled #:

Code:
Diagram 4
. A . |. . . |. a .
a . . |. . A |. . .
. . . |. . . |. . .
------+------+------
. a . |. . # |. . .
. . . |. . . |. . .
. . . |. . . |. . .
------+------+------
A . . |. . . |. @ .
. . . |. . . |. . .
. . . |. . . |. . .


If we add in the cells that make the grouped coloring elimination in @:

Code:
Diagram 5
/ * * |/ / / |/ * /
* / / |/ / * |/ / /
* / / |. . . |. . .
------+------+------
/ * . |. . # |. . .
/ / . |. . . |. . .
/ / . |. . . |. . .
------+------+------
* / . |. . . |. @ .
/ / . |. . . |. . .
/ / . |. . . |. . .

Edited to correct R3C3;  should be "/", not ".".


Simple coloring (grouped or not) no longer eliminates #. The groups for the elimination of @ are not relevant for the elimination of #.

Yes, # can still be eliminated by a skyscraper / kite / Turbot fish, because there is a weak link in B1. But, there is not a strong link.

The "Empty Rectangle" is a pattern very similar to what has been discussed above. It also uses groups.

Code:
Diagram 6
* * * |. . . |. @ .
* / / |. . . |. . .
* / / |. . . |. . .
------+------+------
. . . |. . . |. . .
. . . |. . . |. . .
. . . |. . . |. . .
------+------+------
* / / |/ / / |/ * .
. . . |. . . |. . .
. . . |. . . |. . .


The ER starts when the candidates in a box lie only in one row and one column. In Diagram 6, the logic is:

R7C8 is true; R1C8 is false, or:

R7C8 is false; R7C1 is true; the candidate in B1 must be in R1; R1C8 is false.

Either way, R1C8 is false.


Last edited by keith on Mon Oct 27, 2008 9:16 pm; edited 1 time in total
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3150
Location: near Detroit, Michigan, USA

PostPosted: Sun Oct 26, 2008 8:10 pm    Post subject: Some Examples Reply with quote

This post is out of chronological sequence: It is reserved to be edited, to provide examples at later dates.

March 1, 2009:
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=3303
I think this is a great example.

Keith


Last edited by keith on Mon Mar 02, 2009 7:02 am; edited 3 times in total
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5123
Location: Rochester, NY, USA

PostPosted: Sun Oct 26, 2008 9:36 pm    Post subject: Reply with quote

Thanks Keith. I appreciate the time it must've taken to put this together.

Quote:
In our coloring diagram, we can add two more strong links in R2 and C2, making an elimination in the cell labelled #:


Diagram 4
Code:
. A . |. . . |. a .
a . . |. . A |. . .
. . . |. . . |. . .
------+------+------
. a . |. . # |. . .
. . . |. . . |. . .
. . . |. . . |. . .
------+------+------
A . . |. . . |. @ .
. . . |. . . |. . .
. . . |. . . |. . .



If we add in the cells that make the grouped coloring elimination in @:


Diagram 5
Code:
/ * * |/ / / |/ * /
* / / |/ / * |/ / /
* / . |. . . |. . .
------+------+------
/ * . |. . # |. . .
/ / . |. . . |. . .
/ / . |. . . |. . .
------+------+------
* / . |. . . |. @ .
/ / . |. . . |. . .
/ / . |. . . |. . .



Simple coloring (grouped or not) no longer eliminates #. The groups for the elimination of @ are not relevant for the elimination of #.

In diagram 4, # is eliminated by what I would call strong links/kite/multi-coloring/turbot fish or whatever other terms are used.

In diagram 5, the cells that made up the group are added and you say that simple coloring (grouped or not) no longer eliminates #. That I don't understand since it looks like the same logic eliminates # in both diagrams 4 and 5.
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Oct 27, 2008 7:51 am    Post subject: Reply with quote

Marty,

Diagram 4 does not require multi-coloring for the # elimination; it is accomplished by "basic" (single cluster) coloring, which is what I believe Keith meant by simple coloring. All of the links connecting the "pincers" are conjugate. Diagram 5 requires ("non-simple") multi-coloring due to the weak (only) link in Box 1.
Back to top
View user's profile Send private message Visit poster's website
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Oct 27, 2008 9:09 am    Post subject: Reply with quote

Regarding the ER, I will attempt to provide additional explanation according to my understanding of such things:

Yes, the ER, too, uses groups. To understand how requires a bit of preliminary clarification of definitions. The strong links discussed by Keith are conjugate links, meaning that one side is true and the other false. It is true that conjugate links are strong links. However, conjugate links are also weak links. Conjugate links satisfy the logical requirements of both strong and weak links (which is why they are so easy to use). [See below if you need more explanation of strong and weak inferences.]

There also exist strong links that are only strong links. The ER shown above in Diagram 6 is an example of one. But first, let's look at the ER structure in Box 1 of Diagram 5. It can be expressed as a grouped conjugate link between r1c23 on the one side and r23c1 on the other. As such, it is both a grouped strong link and a grouped weak link. (When it functions as an ER, it is functioning as a grouped strong link. For the elimination at @, it is functioning as a grouped weak link, not as an ER.)

[To be precise, the grouped link is between the grouped candidate digit in cells r1c23 and the grouped candidate digit in cells r23c1. Saying that the link is between the grouped cells is a shorthand for this.]

Since Keith was considering only weak links and conjugate strong links, his statement that the groups on either side of a link cannot share a candidate is true. To understand the grouped link of the ER in Diagram 6, we must consider the case where this restriction does not apply. Here, the grouped link is between r1c123 and r123c1. Notice that both sides of the link contain the candidate in r1c1. Thus, if r1c1 is true, then both sides of the link are true. Still, since this link includes all instances of the candidate in Box 1, it is impossible for both sides to be false. This is a "strong only" link, sometimes called a "strong inference" link. But, really "strong link" is a perfectly fine description provided it is understood that strong link is not a synonym for conjugate link.
__________

True and False as applied to groups:

It might help to explain what it means for a group to be true or false. A group is true if at least one member of the group is true. A group is false if all members of the group are false.
__________

Strong and Weak Inferences:

For those not familiar with strong and weak inference concepts, this might be a good place to provide a quickie explanation. A strong inference exists between two things if when one of those things is assumed to be false the other must be true. The minimum requirement for this occurs when it is impossible for both things to be false. A conjugate link, such as exists between two candidates in a House which are the only two instances of that candidate in that House, meets this requirement: if they were both false, then the House would lack that candidate, which is not possible. A grouped link that encompases all of the instances of a candidate in a House does the same. Note that a link in which both sides can be true also satisfies this requirement as long as it is impossible for both sides to be false.

A weak inference exists between two things if when one of those things is assumed to be true the other must be false. The minimum requirement for this occurs when it is impossible for both things to be true. A conjugate link satisfies this requirement and is thus also a weak link. Any two candidates within a House that contains more than two of those candidates is also a weak link; both sides might be false, but both sides cannot be true. And, a grouped link within a House that does not share a candidate on both sides of the link is also a weak link, whether or not it includes all instances of the candidate digit within that House.

The examples given for strong and weak links do not exhaust the possibilities. But, more some other time!
Back to top
View user's profile Send private message Visit poster's website
Marty R.



Joined: 12 Feb 2006
Posts: 5123
Location: Rochester, NY, USA

PostPosted: Mon Oct 27, 2008 4:27 pm    Post subject: Reply with quote

Asellus wrote:
Marty,

Diagram 4 does not require multi-coloring for the # elimination; it is accomplished by "basic" (single cluster) coloring, which is what I believe Keith meant by simple coloring. All of the links connecting the "pincers" are conjugate. Diagram 5 requires ("non-simple") multi-coloring due to the weak (only) link in Box 1.

Thanks, I just missed that chain in diagram 4. But I deserve a dozen lashes with a wet noodle because the fact that there were just two possibilities in box 1 meant there was a simple chain.
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Mon Oct 27, 2008 7:51 pm    Post subject: Reply with quote

I deliberately avoided using the full Empty Rectangle pattern in another post on grouped strong links because I knew that it would be difficult to explain. However, since Pandora's Box (pun intended) has been opened here, I would like to add my opinion.

An ER pattern contains two usable grouped strong links.

Code:
 [r789c2]=X=[r8c13]   and   [r8c123]=X=[r79c2]
 +-----------------------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | / X / | . . . | . . . |
 | X X X | . . . | . . . |
 | / X / | . . . | . . . |
 +-----------------------+

An ER pattern in the classic ER technique can be written as an AIC without confusion.

Code:
 [r2c8]=X=[r2c2]-X-[r789c2]=X=[r8c13] => [r8c8]<>X   (AIC)
 +-----------------------+
 | . . . | . . . | . . . |
 | / X / | / / / | / X / |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | / X / | . . . | . . . |
 | X X X | . . . | . * . |
 | / X / | . . . | . . . |
 +-----------------------+

The two ER patterns in this loop can not be included in an AIC without some confusion.
(Often, the ER pattern is replaced with a macro to conceal the confusion.)

Code:
 [r2c2]=X=[r2c8]-X-[r789c8]=X=[r8c7 9]-X-[r8c123]=X=[r7 9c2]-X-[r2c2]   left-to-right
 [r2c2]=X=[r2c8]-X-[r7 9c8]=X=[r8c789]-X-[r8c1 3]=X=[r789c2]-X-[r2c2]   right-to-left
 +-----------------------------------+
 |  .  *  .  |  .  .  .  |  .  *  .  |
 |  /  X  /  |  /  /  /  |  /  X  /  |
 |  .  *  .  |  .  .  .  |  .  *  .  |
 |-----------+-----------+-----------|
 |  .  *  .  |  .  .  .  |  .  *  .  |
 |  .  *  .  |  .  .  .  |  .  *  .  |
 |  .  *  .  |  .  .  .  |  .  *  .  |
 |-----------+-----------+-----------|
 |  /  X  /  |  .  .  .  |  /  X  /  |
 |  X *X  X  |  *  *  *  |  X *X  X  |
 |  /  X  /  |  .  .  .  |  /  X  /  |
 +-----------------------------------+
_____________________________________________________________________________________

Boxes [b7] & [b9] are initially an ER pattern, but [r8c28]<>X are among the eliminations. They are only present when you review common eliminations in the AIC sub-chains.

===== ===== =====

As for strong/weak inference and strong/weak link, this is from my notes on chains.
(Examples of grouped strong links are not present.)

Code:
Strong Inference (SI):  ~A =>  B
Weak   Inference (WI):   A => ~B

Code:
Strong Link (SL):  e.g., ( bilocation  []=n=[] ) or ( bivalue cell  m-[]-n )
Weak   Link (WL):  e.g., ( peers       []-n-[] ) or ( ?-value cell  m=[]=n )

Code:
bilocation   [a]=n=[b]:  if [a] is not 'n', then [b] is     'n'
bivalue cell  m-[c]-n :  if [c] is not 'm', then [c] is     'n'

peers        [d]-n-[e]:  if [d] is     'n', then [e] is not 'n'
?-value cell  m=[f]=n :  if [f] is     'm', then [f] is not 'n'

Code:
Sudopedia:  a SL can be used for SI or WI, but a WL can only be used for WI

Code:
Alternating Inference Chain (AIC):  SI, WI, (alternating until) SI
   -- bidirectional   (a chain consisting of an odd number of SLs is an AIC)
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Oct 27, 2008 8:49 pm    Post subject: Reply with quote

daj95376 wrote:
The two ER patterns in this loop can not be included in an AIC without some confusion.

This is true only if you want to insist that "strong link" is synonymous with "conjugate link". And, if that is your opinion, then fine. I was careful to explain that I do not adhere to that restriction. In my opinion, this limitation of strong link to conjugate links is an understandable accident of sudoku history: conjugate links are naturally the first sort of strong links to have gained attention. But, they are called strong because they can be used for strong inferences, which the also-initially-obvious weak (only) links cannot be.

The statement that "a strong link can be used as both a weak and strong inference" is, to me, a syntactical muddle. However, the statement "a conjugate link can be used as both a weak and strong inference" is not only coherent, it is informative and makes things clearer. There is a universe of strong links and a universe of weak links; the overlap of these two universes is the universe of conjugate links.

If one defines strong link (as I do ... and I am certainly not the only one) as a link with a strong inference, then there is no need to worry about including the ERI digit on both sides of the grouped link and the two consecutive ERs can be written in an AIC without any problem whatsoever.

Similar strong (only) links are used in AICs all the time. For instance, the strong links induced by Deadly Patterns are such strong links: it is possible that both sides of the link are true. Are all the AICs that include such DP-induced strong links also "problematic"?

[Note: I should point out that this entire discussion is concerned only with bidirectional links.]
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3150
Location: near Detroit, Michigan, USA

PostPosted: Mon Oct 27, 2008 9:31 pm    Post subject: Reply with quote

Marty, you may already have your answer, but here is my spin:

Marty R. wrote:
it looks like the same logic eliminates # in both diagrams 4 and 5.


Marty: Yes, and no.

Let me redo the diagrams so only the cells relevant to "#" are marked:

Diagram 4a
Code:

. A . |. . . |. . .
a . . |. . A |. . .
. . . |. . . |. . .
------+------+------
. a . |. . # |. . .
. . . |. . . |. . .
. . . |. . . |. . .
------+------+------
. . . |. . . |. . .
. . . |. . . |. . .
. . . |. . . |. . .


This is simple coloring: Any cell that sees both a and A can be eliminated. Yes, it looks like a kite / skyscraper / Turbot fish, but it is not.

Now, Diagram 5a
Code:

/ A * |. . . |. . .
B / / |/ / b |/ / /
* / / |. . . |. . .
------+------+------
. a . |. . # |. . .
. / . |. . . |. . .
. / . |. . . |. . .
------+------+------
. / . |. . . |. . .
. / . |. . . |. . .
. / . |. . . |. . .


This is multicoloring; it is also a kite / skyscraper, etc. The logic is: Either A and/or B is false. Therefore, given the strong links, either a and/or b is true. So, # is eliminated.

You are correct: The same multicoloring logic can be applied in both diagrams, to make the same elimination. But, suppose you wanted to use the pincer cells in some other pattern. The logic following simple coloring (One of a and A is true, the other is false, Diagram 4a) is (subtly) different than the logic following multicoloring (One, or both, of a and b are true, Diagram 5a).

Best wishes,

Keith
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
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