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 

Clarification or confirmation

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
Nwohio



Joined: 12 May 2007
Posts: 9

PostPosted: Sat Jul 28, 2007 12:51 am    Post subject: Clarification or confirmation Reply with quote

Code:

+--------------+------------+-------------+
| 7    4   18  | 2   6  3   | 18  5  9    |
| 1358 589 2   | 45  14 19  | 6   7  1348 |
| 1356 569 135 | 457 8  179 | 134 2  134  |
+--------------+------------+-------------+
| 4    7   9   | 6   3  8   | 5   1  2    |
| 13   58  13  | 9   57 2   | 478 48 6    |
| 58   2   6   | 1   57 4   | 9   3  78   |
+--------------+------------+-------------+
| 2    568 458 | 78  9  167 | 13  48 135  |
| 568  3   7   | 48  14 16  | 2   9  15   |
| 9    1   48  | 3   2  5   | 478 6  478  |
+--------------+------------+-------------+

Play this puzzle online at the Daily Sudoku site

I was able to solve the above by the following.

Placing 8 in r7c8 would result in an 8 in r9c3. Placing 4 in r7c8 in an 8 in r1c7. Since r1c3 "sees" both r9c3 and r1c7, I removed the 8 and the puzzle broke. Is this an example of an XY-chain or did I just get lucky?
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sat Jul 28, 2007 3:49 pm    Post subject: Reply with quote

I'm not really qualified to answer since XY-Chains are not my forte. But most definitions of that term say it involves a chain of bivalue cells, which is not the case in your example. I would call it a form of a forcing chain, but I hope someone else weighs in. Perhaps since it does involve pincers it can loosely be considered an XY-Chain.

"A XY-Chain is a chain of cells which each contain only 2 candidates.

Because the chain is entirely made up by bivalue cells, the link between the 2 candidates in each cell cause strong inference, which allows us to use weak inference between the cells.

The shortest XY-Chain is an XY-Wing with only 3 cells.

A XY-Chain is both a Double Implication Chain and a Alternating Inference Chain."
Back to top
View user's profile Send private message
Nwohio



Joined: 12 May 2007
Posts: 9

PostPosted: Sat Jul 28, 2007 4:29 pm    Post subject: Reply with quote

Thanks for your input. I think you are right. It is a forcing chain, although the use of the pincers does cause it to act similarly to an XY-Chain.
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Mon Jul 30, 2007 7:09 pm    Post subject: Reply with quote

This is basically an ALS Chain, though it has a little twist in Box 6. An XY Chain is just the simplest form of an ALS (Almost Locked Sets) Chain since a bivalue cell is the simplest ALS (N+1 candidates for N cells). Once the XY Chain technique is understood, it is not too difficult to start using the more general ALS Chain, which is handy for very tough puzzles. When you have many bivalues but can't quite make an XY Chain link up, then it is a good idea to scan for 2-cell ALS as well since they are quite easy to spot and may provide the missing links. 3-cell ALS are a bit more difficult to see and aren't often needed.
Code:
+--------------+------------+----------------+
| 7    4  #18  | 2   6  3   | H18   5   9    |
| 1358 589 2   | 45  14 19  |  6    7   1348 |
| 1356 569 135 | 457 8  179 | G134  2   134  |
+--------------+------------+----------------+
| 4    7   9   | 6   3  8   |  5    1   2    |
| 13   58  13  | 9   57 2   | F478 D48  6    |
| 58   2   6   | 1   57 4   |  9   3   E78   |
+--------------+------------+----------------+
| 2    568 458 | 78  9  167 | G13  C48  135  |
| 568  3   7   | 48  14 16  |  2    9   15   |
| 9    1  A48  | 3   2  5   | B478  6  B478  |
+--------------+------------+----------------+

The Chain sequence is marked A through H. All the letters identify an ALS except for F. In the case of F, it is a double elimination of 87 by the DE sequence. (You can also see DEF as a locked set that "collapses" sequentially.)

If A is <8>, the Target (#) <8> is eliminated. If A is <4>, ALS B becomes the locked set 78, C is <4>, etc., to F as <4>, the ALS G becomes the locked set 13 forcing the other pincer, H, to <8>, also eliminating the Target.

Note that it is possible to chain directly from C to F by "box-line" elimination. In other words, there are other ways to form a chain link than ALS.

There are notation systems that have been worked out for such chains but I have not yet learned them. (It is on my "To Do" list.)
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Tue Jul 31, 2007 8:04 am    Post subject: Reply with quote

To see the ALS elimination more formally:



ALS A in green {4,7,8} n = 3 so 2 squares
ALS B in pink {1,3,4,7,8} n = 5 so 4 squares

restricted common is 7 (ie will exist in A or B but not both}

The other common candidate 8 (orange) can be seen by both sets and is eliminated.
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Tue Jul 31, 2007 5:44 pm    Post subject: Reply with quote

Mogulmeister,

While those are indeed a pair of ALS, I don't see how they eliminate <8> in the orange target. For the shared common elimination, the target cell(s) must be able to "see" all instances of the shared common digit in both ALS. In this case, the target can see R1C7 and R9C3. But, it cannot see the <8>s in R59C7.

Am I not seeing something?

In my prior post, the implication chain involving multiple ALS avoids this by using R1C7 and R9C3 as "pincers". Perhaps I should attempt to notate the chain:
8-A-4-B-8-C-4-DEF-4-G-1-H-8
The pincer <8>s are on the ends. The linking digits are shown. "DEF" is the "collapsing" locked triple.
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Tue Jul 31, 2007 6:06 pm    Post subject: Reply with quote

Quite right A, it's the heat - I must have fallen asleep at the wheel and I like ALS too!

Have a squint at Eureka notation and you should be able to write down your chain.
Back to top
View user's profile Send private message
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Tue Jul 31, 2007 6:24 pm    Post subject: Reply with quote

We'll have to ask Ruud or Myth how they might notate this.
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Thu Aug 02, 2007 12:33 am    Post subject: Reply with quote

I perused Ruud's notes on Eureka notation at sudocue.net and have constructed what I believe is a valid notation for the chain, with the following proviso: Cell "E" is omitted and the strong link on <4> in Box 6 connects D and F in sequence.

(8)R1C3-(8=4)R9C3-(4=8)R9C79-(8=4)R7C8-(4)R5C8=(4)R5C7-(4=1)R37C7-(1=8)R1C7-(8)R1C3
=> R1C3<>8

Ruud's example contained only bivalue cells, so I'm not certain that I have notated the 2-cell ALS nodes properly. However, it makes sense to me. Also, the chain works in either direction which, frankly, surprised me. So, it is a Double Implication Chain.

In some places where a weak link, "-", is indicated, a strong link, "=", actually exists. However, this makes no difference for the chain logic. The essential thing is that every other link must be a strong link.

Anyway... I hope this post is of interest to any others who, like me, are curious about implication chains and their notation.
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Thu Aug 02, 2007 3:41 am    Post subject: Reply with quote

That looks fine to me. E can be bypassed as we're talking with reference to 4 ("r5c8 can't be 4 so r5c7 must be 4"). As a variant I have seen multiple cells notated as:

(4)r7c7 - (4=1)r3c7|r7c7-(etc etc) with each cojoint cell separated by a Bayesian type "|".

Alternatively I have seen notation which brackets the cell references rather than the candidate values. What is nice about Eureka is that it abbreviates the xx between candidates eg (4=1) which would otherwise necessitate something like:

4[r7c7]-4[r3c7|r7c7]=1[r3c7|r7c7]

With the Extreme puzzles I find very often I have to use Nice Loops or Alternating Inference Chains (AIC).

Just to round off, notice this can also be referred to as a Discontinuous (Alternating) Nice Loop. It has two weak links ( -8 ) at the discontinuity (r1c3) so that candidate is eliminated.
Back to top
View user's profile Send private message
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Thu Aug 02, 2007 4:48 am    Post subject: Reply with quote

Quote:
Also, the chain works in either direction which, frankly, surprised me


Well it depends what we call "exotic" Smile (see below)

Quote:
(Ruud) Any forcing chain requires strong links for every second node to work, which means that you cannot avoid alternating inference. And, as long as we do not include any exotic patterns in the chain, alternating inference always operates in both directions.


That was from this thread

http://www.sudoku.org.uk/discus/messages/29/2642.html?1160055686
Back to top
View user's profile Send private message
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Thu Aug 02, 2007 5:13 am    Post subject: Reply with quote

While warming to the subject, here is a bit from another Mepham/Stuart extreme (notice the behaviour of the pink block):



Notates as:

(4)r2c1-(4)r2c7=(4)r1c8|r2c8|r3c8-(4)r6c8=(4)r6c1-(4)r2c1

so r2c1<> 4
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Thu Aug 02, 2007 6:39 am    Post subject: Reply with quote

Mogulmeister,

So much response! That's good.

1: With regard to my chain... The "discontinuity" isn't actually two weak links. As I hinted before, I could rewrite my Eureka notation as:

(8)R1C3-(8=4)R9C3=(4=8)R9C79=(8=4)R7C8=(4)R5C8=(4)R5C7-(4=1)R37C7=(1=8)R1C7=(8)R1C3

I believe that that would be equally valid since the relationships shown by "=" are all strong, IMHO. But, it makes it harder to see that the alternating links are strong. So, I alternated for the sake of clarity.

As this alternate (as opposed to alternating) notation makes clear, R1C3 involves one weak link and one strong link. In any case, it doesn't matter: the effect is the same... there is a contradiction.

2: Regarding the pipe character, "|"... Ruud's brief notes say that this is only valid at the chain ends for "branching eliminations" (my paraphrase). That implies that it is not valid within the chain. Your example isn't that helpful to me since Ruud says (though in a slightly different context) that, if multiple cells share a row or column, the "RC" notation can be collapsed. So, those pink cells can be notated as "R123C8" rather than as "R1C8|R2C8|R3C8".

It seems to me that if "|" is used for branched eliminations at the chain ends, then some other symbol is needed for non-colinear sets within the chain. Perhaps "|" when used in non-terminal nodes is understood differently. I would be tempted to use "/" for such cases. For instance, a 3-cell ALS node located in R2C2, R3C2 and R3C3 could be notated "R2C2/R3C23" or "R2C23/R3C3". But, that's just me.

We can all breathe a sigh of relief that I didn't have any such nodes in my chain! But, just wait!!

3. I don't know what Ruud means by "exotic" inferences. But, I'm sort of disappointed that mine weren't! In any case, I followed the "Alternating Rule" and found that I was "Bidirectional." Isn't that exotic enough?

4: In your Mepham/Stuart example, it might be clearer to others if R6C1 were also pink. But, I myself am beyond colors. What I find interesting about that example isn't the behavior of the pink 3-cell set. It is that the weak link between R2C1 and R2C7 serves a useful purpose. It is a good example of that "Alternating Rule." But, that leads to "Bidirectionality." Don't say you weren't warned!
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Thu Aug 02, 2007 8:23 am    Post subject: Reply with quote

Quote:
=(1=8)R1C7=(8)R1C3


Is how you rewrote your chain end. This cannot be - you are effectively saying r1c7 must be 8 and so must r1c3.

Start as you did originally at r1c3 with ..."if 8 then r9c3 cannot be 8" etc this is weak link 1

(follow the chain of events (sorry pun)) and eventually you arive at "If r1c7 is not 1 it must be 8 and r1c3 cannot be 8 (1=8)R1C7-(8)R1C3. This is weak link 2 and causes the discontinuity.

I wasn't sure what he meant either by "exotic" which is why there was a smilie next to that quote. The bidirectional is a given if you have a valid AIC.
.

2)The pink was used to show that the trigroup was being addressed (for the purposes of notation) and not to do with the candidate polarity. I underscored this in the notation which was also the same colour.

I'm not tethered to any specific notational norm - just wanted to show how these multiple cells are written by some folk.
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Thu Aug 02, 2007 8:21 pm    Post subject: Reply with quote

Quote:
=(1=8)R1C7=(8)R1C3


Is how you rewrote your chain end. This cannot be - you are effectively saying r1c7 must be 8 and so must r1c3.


I believe you may be confusing the "=" used for Eureka strong link implications with the arithmetic "equals". In the Eureka chain, the link ends alternate True-False beginning with True at the chain start. Here is my chain with the True-False sequence indicated:
Code:
(8)R1C3-(8=4)R9C3=(4=8)R9C79=(8=4)R7C8=(4)R5C8=(4)R5C7-(4=1)R37C7=(1=8)R1C7=(8)R1C3
 T       F T       F T        F T       F       T       F T        F T       F
 

A strong link works in either direction (hence the double line):
T=F or
F=T
are both valid.

A weak link is unidirectional (hence the single line):
T-F

The implication "F-T" is invalid.

When a chain is reversed, so are the True-False conditions. If you consider this, then it is obvious why weak links must be restricted to alternate positions (those with True conditions) for the chain to be bidirectional. However, any or all of the weak links can be replaced with strong links, including those at the chain ends.
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Fri Aug 03, 2007 9:12 am    Post subject: Reply with quote

I'm quite aware of the difference between the equals sign and its use as a strong link.

a=b strong inference "if not a MUST be b"

a-b weak inference "if a can not be b"

As for alternate inference chains:

From Sudopedia (on Eureka)

Quote:
There can be no 2 adjacent dashes or equal signs, whether or not they are placed inside the parenthesis.
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Fri Aug 03, 2007 8:52 pm    Post subject: Reply with quote

Mogulmeister,

I think we are talking past each other here.

Yes, the Eureka convention requires that the chain be notated with alternating "-" and "=". I first wrote my chain per the convention. This convention then provides that eliminations occur when the common ends are connected by the weak link symbols.

Then, I pointed out that where the notation indicates a strong link, a strong link must actually exist in the puzzle grid. However, where the notation indicates a weak link, the puzzle may contain either a strong or a weak link. I rewrote the chain to indicate the actual nature of the links in this particular puzzle example. It is not following the Eureka notation convention.

Eliminations occur regardless. The essential requirement is that each link following an "even-numbered" node be strong and that the common terminal end be at an even-numbered node. Every link in the chain can in fact be strong and the elimination is valid just the same.

I took your initial response to suggest that actual weak links are required in the puzzle and was trying to make clear that this isn't so.

PS:
The strong link logic is more completely stated as "if not a MUST be b AND if not b MUST be a". When explaining Eureka basics, the first part is stressed. But the second part is essential to the chain's bidirectionality.
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 1151

PostPosted: Thu Aug 09, 2007 7:33 pm    Post subject: Reply with quote

Quote:
I took your initial response to suggest that actual weak links are required in the puzzle


No that is not what I meant which you realised. Smile

The second part of the strong link inference (bidirectionality) is implicit.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles 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