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 

W-wing Meets Coloring: The W-link?

 
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: 3184
Location: near Detroit, Michigan, USA

PostPosted: Sat Aug 25, 2007 7:49 pm    Post subject: W-wing Meets Coloring: The W-link? Reply with quote

This puzzle is quite interesting:
Code:
Puzzle: DB082507  ******
+-------+-------+-------+
| . . . | . 9 . | . 6 . |
| . 8 . | 5 3 . | 7 . 9 |
| . 1 9 | . . 2 | 5 . . |
+-------+-------+-------+
| 1 2 . | . . . | 3 . . |
| . . . | 8 . 3 | . . . |
| . . 6 | . . . | . 8 4 |
+-------+-------+-------+
| . . 3 | 6 . . | 2 7 . |
| 7 . 1 | . 2 4 | . 9 . |
| . 9 . | . 8 . | . . . |
+-------+-------+-------+

Basic methods get you here.
Code:
+-------------+-------------+-------------+
| 235 357 257 | 14  9   8   | 14  6   23  |
| 246 8   24  | 5   3   16  | 7   12  9   |
| 36  1   9   | 47  67  2   | 5   34  8   |
+-------------+-------------+-------------+
| 1   2   8   | 9   4   67  | 3   5   67  |
| 459 57  457 | 8   167 3   | 169 12  267 |
| 39  37  6   | 2   17  5   | 19  8   4   |
+-------------+-------------+-------------+
| 8   4   3   | 6   5   9   | 2   7   1   |
| 7   6   1   | 3   2   4   | 8   9   5   |
| 25  9   25  | 17  8   17  | 46  34  36  |
+-------------+-------------+-------------+

There are two (not immediately useful) W-wings:


The first is that at least one of R3C1 and R9C9 is <6>.

The second is that at least one of R6C5 and R9C4 is <1>.

However, you can use coloring to "extend" the W-wing:

The coloring is to find cells that must have the same value as the W-wing candidate in one of the W-wing cells.

For example, if R3C1 is <6>, R5C5 is <6>.

If R9C4 is <1>, R1C7 is <1>.

Thus, R5C9 is not <6>, and R6C7 is not <1>.

Interestingly, the effective rule is that you can regard the two W-link cells as being a strong link in the W candidate. (Edit Oct 24, 2007: The W-link is not simply equivalent to a strong link. See the messages later in this thread - keith.) Then just do your simple coloring.

I suspect this is going to be a really useful concept. Maybe we can call the value W in the two W-cells a W-link? And, this technique is W-coloring?

Keith


Last edited by keith on Wed Oct 24, 2007 8:22 am; edited 3 times in total
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Sat Aug 25, 2007 10:57 pm    Post subject: Reply with quote

Warning: I may lose some folks in this message. It is a somewhat more formal way of restating what Keith has said above and deals with some slightly arcane logic. However, it may be helpful for those who are ready to absorb its content.

Whether or not a new "W-Link" term is needed depends upon whose terminology is being used, it seems. While I'm no authority, I have been reading up a bit on implication chain logic. In implication chaining, the term "strong link" is often defined differently from how it is used in common parlance on this Board. This is confusing at first (and certainly confused me), but makes a great deal of sense as one explores the logic further.

Given 2 cells that have a common candidate digit, there are 4 possible cases:

A: F F
B: T F
C: F T
D: T T

"T(rue)" means the puzzle solution has that digit in that cell. "F(alse)" means the puzzle solution has some other digit in that cell.

For the purposes of implication chaining:

A weak link means that at most one of the cells is True. So, Cases A, B and C comprise possible weak links.

A strong link means that at least one of the cells is True. So, Cases B, C and D comprise possible strong links.

Note that this definition of a "strong link" differs from the common usage on this Board. Commonly, we think of a "strong link" as Cases B and C: i.e. an exclusive either/or relationship. [This is probably because we normally limit ourselves to "buddie" cells when discussing links, in which case an implication strong link can only be Cases B and C.]

So, the "W-Link" is not a "strong link" in common parlance on this Board. But, it is a "strong link" in implication chain parlance. [Note that Case D can only occur between "remote" cells. In fact, a W-Wing is the only way of which I am aware to establish such a relationship between two remote cells.]

Finally, standard implication chains require that the links alternate strong and weak. So, the "W-Link" is acceptable in a chain (such as coloring) provided that it occurs at a point where a strong link is necessary (since it is actually an implication "strong link").

[Note: The common parlance either/or "strong link" is comprised of Cases B and C. This makes it a sort of "universal link" for implication chain purposes since it complies with both the "strong" and "weak" definitions and can thus occur anywhere in the chain.]

Using Eureka notation, one can write the <1> elimination from R6C7 as follows:

(1)R6C7-(1=1)R1C74-(1=7)R9C4-(7=7)R3C45-(7=1)R6C5-(1)R6C7; R6C7<>1

The red portion of the chain is the "external link activation of the W-Wing." If the red portion is omitted (and the cell references tidied up!), the chain is still valid since the resulting "1=1" "W-Link" is, in fact, an implication chain strong link (though reference to the W-Wing is necessary), as required by the alternating notation .

In conclusion, I'd say that a "W-Link" works in coloring provided that it occurs at a "strong link" point in the underlying AIC logic. Since basic/simple coloring relies only on strong links (as understood in the "universal" common parlance sense), this shouldn't pose any problems and Keith's approach works fine. However, beware of using a "W-Link" in a "Color Wing" (or "Multi-Coloring") or in some more general AIC unless you pay careful attention to the sequence of alternating links!
Back to top
View user's profile Send private message Visit poster's website
keith



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

PostPosted: Sun Aug 26, 2007 2:39 am    Post subject: Links Reply with quote

Asellus,

I have asked this question elsewhere:

Strong Link: One of two cells is A.


Weak link: One of two cells is not A.


OK so far. But, what is this, what I called the W-link? One or both of two cells is A.

The other place where this occurs is the two tips of a skyscraper (turbot fish). (And, I agree, I need to learn and to use, Nice Loop notation.)

The other cases are: Both of two cells are A.

Neither of two cells are A.


I agree with what I think you are saying: You cannot just use a W-link as a strong link in any established logic. But, yes, I really want to go there!
Best wishes,
Keith
Back to top
View user's profile Send private message
keith



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

PostPosted: Sun Aug 26, 2007 3:35 am    Post subject: Reply with quote

Asellus,

I have been contemplating your reply.

Quote:
A weak link means that at most one of the cells is True. So, Cases A, B and C comprise possible weak links.

A strong link means that at least one of the cells is True. So, Cases B, C and D comprise possible strong links.


Which are quite valid definitions, except I don't think they agree with usual terminology.

Not that I completely endorse Ruud's Sudopedia, but try:

http://www.sudopedia.org/wiki/Strong_link

In my terminology:

A "link" involves only two cells.

Weak link: One is false. The other may be true or false.

Strong link: One is true, the other must be false.

W-link: One is true, the other may be true or false.

There are two other cases (I think) which may or may not be useful:

Both are true.

Both are false.

Keith
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Sun Aug 26, 2007 7:10 pm    Post subject: Reply with quote

Keith,

The idea is actually much simpler than it seems from all the explanation. Ruud's strong link definition does not contradict the "at least one is true" definition. Ruud's definition is: If A is false, B is true AND if B is false, A is true. But, that does not logically preclude both being true.

When we normally consider a link between two cells, we are concerned only with "buddie" cells. In that instance, Case D (both are True) can never occur so the "strong link" becomes the "either/or" type as we usually think of it. But, if we extend the notion to remote cells, things are different.

For implication chaining we have the following requirement:

An "if A is False, B is True" link must be followed by an "If A is True, B is False" link, and so on in strict alternating fashion. The first is "Strong" and the second is "Weak".

The conventional buddie cell "either/or" notion of a strong link can satisfy either type of implication requirement and so can occur at any point in a chain.

The W-Wing cells are remote and so are capable of falling into Case D (both True). This means that they can satisfy the "Strong" implication requirement, but not the "Weak" requirement. Hence the need to be careful of their sequence in a complex chain. (As I mentioned before, in the case of simple or basic coloring, we can ignore this detail because we are otherwise using only the conventional "either/or" buddie cell strong links. However, if you got creative and tried to weave two separate W-Links into a chain, you would have to be careful of their sequence placement. Or, if your chain included a weak link, you would similarly need to attend to the sequence placement.)

This more generalized strong link notion is not something I dreamed up. I have read it elsewhere but didn't save any links to the reference. At the time, it didn't make much sense to me. But, it stuck in the back of my mind. Your W-Link made the light bulb turn on!

While confusion can easily result, there isn't really a terminology conflict. The "either/or" strong link is a special case in which remote cell links are excluded. The "at least one is true" strong link belongs to the more general case that does not have such a restriction.

Or, at least, that's how I see it.
Back to top
View user's profile Send private message Visit poster's website
keith



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

PostPosted: Sun Aug 26, 2007 9:07 pm    Post subject: Reply with quote

Asellus is correct. You cannot blindly use the W-link as a regular strong link.

If you write the W-link as
W=+=W

and a strong link as
W==w

then the coloring chain is something like
... W==w==W=+=W==w==W==w ...
and you can eliminate the candidate from any cell that sees two W's, one from each side of the +.

Or, if you write it as
... W1==w1==W1=+=W2==w2==W2==w2 ...
you can make the elimination from any cell that sees both a W1 and a W2.

w1 and w2 are not useful to make eliminations.

Keith
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Mon Aug 27, 2007 7:03 am    Post subject: Reply with quote

Keith wrote:
Asellus is correct. You cannot blindly use the W-link as a regular strong link.

As Keith's detail points out, I was not entirely correct. I suggested that if one was otherwise performing basic coloring limited entirely to the conventional "either/or" strong links, the presence of a single W-Link did not matter. But, as Keith points out, that is not correct.

The "W-Link" causes the elimination logic in coloring to work in a manner analogous to, but opposite of, how coloring with a weak link "Bridge" works in a "Color Wing" or "multi-coloring". Examples may clarify...

I learned "Color Wing" as follows (where "-" is the weak link Bridge):

...R=G=R=G=R-r=g=r=g..., the weak link connects R and r, so eliminations occur between G and g.

In the case of a "W-Link" ("=+=" to use Keith's notation):

...R=G=R=G-R=+=r-g=r=g..., the "W-Link" connects R and r, so eliminations occur between R and r. (Note: I deliberately wrote weak links, "-", on either side of the W-Link for two reasons: (1) at least one of them must, in fact, be a weak link or else we do not have a W-Link; and (2) it conforms with AIC logic as I explain below.)

If this approach seems unnatural, then one can conserve the alternating colors:

...R=G=R=G-R=+=g-r=g=r... The W-Link connects R and g, so eliminations occur between R and g (but not between G and r).


For those seeking to understand the connection between this and AIC logic more generally, it is important to understand that a "W-Link" can function only as a strong link. Similarly, a weak link (as commonly understood) can function only as a weak link. The "either/or" type of link between buddy cells that we commonly refer to as a strong link can serve either purpose.

In an AIC, the links must alternate: weak-strong-weak-strong-etc. In addition, the candidate cell(s) for elimination must be connected to both ends of the chain in weak link positions.

Since the "W-Link" is necessarily a strong link, the links immediately to either side are weak link positions (even if one of them is occupied by the "either/or" type of strong link). Using # to represent the elimination candidate cell and alternating the link notation:

#-R=G-R=+=g-r=g-r=g-#

we see that the polarities that link to the candidate cell must match those on the ends of the W-Link.

For comparison, the "Color Wing" would be notated as:

#-R=G-R=G-r=g-r=g-#

The weak link Bridge is "G-r" and the polarities that link to the candidate cell must be opposite those on the ends of the weak link Bridge.
Back to top
View user's profile Send private message Visit poster's website
Steve R



Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England

PostPosted: Wed Sep 05, 2007 4:01 pm    Post subject: Reply with quote

A comment on the terms used may be helpful.

To illustrate them A, B, .... stand for sets of cells (treat them as individual cells if you like) and x, y, … stand for the symbols to be entered in the puzzle.

In terms of chains a strong link, written A =x= B, means x must be an entry in a cell of A or a cell of B. Thus it implies that x is a candidate for both A and B. Also it permits x to be entered in both A and B. This seems to be the meaning that Keith desires.

A weak link, written A -x- B, means that x is a candidate for both A and B and can be entered into at most one of them. It permits neither A nor B to have x as an entry. As an aside the definition is exactly that of “restricted common candidate,” a term introduced by bennys in relation to almost locked sets but applicable more widely.

As “strong” is used in other contexts to mean that A and B are conjugate with respect to x, the term “strongly inferential” is sometimes used for the link described as strong above. In chain terms conjugates A and B with respect to x give rise to two different links: A =x= B and A -x- B. There is no link meaning “x is an entry for precisely one of A and B,” that is for conjugacy, because so far no one has come up with a scheme incorporating it which can transport useful information along the chain.

There is one other useful link (mixed), written A =x- B. The strong and weak links read identically from left to right and right to left. The mixed does not:
- (from left to right) x is a candidate for both A and B and, if x is not an entry for A, it is not an entry for B
- (from right to left) x is a candidate for both A and B and, if x is an entry for B, it is an entry for A.
However, if you think about it, these are two ways of saying the same thing. This type of link is most commonly associated with near fish. Take an x-wing based on rows for example. If B is a cell in one of the transverse columns which has x as a candidate, x may be eliminated from B. Now go one step further and suppose the bottom row has a third cell, A, open to x. There is no x-wing but, if x is excluded from A, the x-wing reappears and the elimination from B is sound. That is, a link A =x- B becomes available for constructing a chain.

I have used nice loop notation. The principles underlying AICs are identical though I think those unfamiliar with AIC notation find it less intuitive.

Steve
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Thu Sep 06, 2007 3:44 am    Post subject: Reply with quote

Steve,

Interesting and helpful post.

I have notice the "mixed" sort of link, but never tried to express it explictly or notate it. (I generally don't follow implications to that level of depth... yet.)

"Strongly inferential" does capture the essential nature of the "remote" strong link of this thread.

I would reiterate that the "conjugacy" link (the common sort of either/or "strong" link) is certainly useful in implications, since it can satisfy both strong and weak inferences. It is a sort of inferential "wild card." What doesn't seem to be useful is having a special symbol for it in chain notations. I assume this was your meaning.
Back to top
View user's profile Send private message Visit poster's website
Steve R



Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England

PostPosted: Thu Sep 06, 2007 11:13 am    Post subject: Reply with quote

Thank you for your kind remark.

As to the question, it was indeed, though I think it goes a little deeper than that.

Let me bore you with the parable of the intelligent baby – please forgive the oxymoron. Its parents are teaching it simple colouring. These cells are conjugate so, if the first does not contain x, the second must. The second cell is conjugate to a third so, if the second contains x, the third cannot. Thus it continues with +/-, red/green or whatever until a conclusion is reached. Being intelligent, the baby thinks “Aha. My parents are unduly restrictive, like all parents the whole world over. It is not necessary for all these pairs to be conjugate and to be coloured. Every other time they need only be associates and eliminations can still be made.”

The baby has split the conjugacy into its two meanings and proceeds to solve more puzzles than its parents with exactly the same effort.

Steve
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sat Sep 15, 2007 2:16 pm    Post subject: Reply with quote

Asellus wrote:
(Note: There is no W-Wing type of coloring logic, as discussed recently on another thread, involved here.)


I knew I didn't understand a lot of what was being said in this thread but didn't know this was the conclusion that was reached.

The W-wing tells us that at least one of the bi-value cells must be the value not in the strong link. Why is it not possible to construct a coloring chain or two based on that information?

(Click here for the thread from which this quote is taken.)
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Sun Sep 16, 2007 2:43 am    Post subject: Reply with quote

Tracy,

It seems you understood more than you gave yourself credit for. I have posted a correction on the other thread.

This "strong inferential" link exists on the ends of XY Wings/Chains as well as on W-Wings. The same sort of coloring results. I suppose we could call it an "inverse color wing" or "inverse multi-coloring" since the polarities used for elimination are the opposite of those in the weak link based "color wing"/"multi-coloring".
Back to top
View user's profile Send private message Visit poster's website
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sun Sep 16, 2007 12:50 pm    Post subject: Reply with quote

Asellus wrote:
(Note: There is no W-Wing type of coloring logic, as discussed recently on another thread, involved here.)


I entirely misunderstood the meaning of this sentence.

I read it as "There is no W-Wing type of coloring logic, a conclusion recently reached on another thread after much discussion" and not as "There is a W-wing type of coloring logic, which was discussed recently on another thread, but it is not involved here."

Anyway, thanks for the clarification.
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