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 

xy-x chain, can I avoid it here?

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



Joined: 10 Jun 2008
Posts: 472
Location: Brampton, Ontario, Canada.

PostPosted: Sat Jul 19, 2008 6:11 am    Post subject: xy-x chain, can I avoid it here? Reply with quote

I generated this puzzle using software that Kyrkios posted at Sudoku programmers. It can generate puzzles quickly and with a fair spread of options.

Code:
. . 1|. 6 3|. . .
5 . .|. 7 .|. . 4
. 8 .|5 4 9|. . .
-----+-----+-----
. . .|. 3 .|7 5 9
. . .|. . .|. . .
8 7 5|. 1 .|. . .
-----+-----+-----
. . .|4 9 7|. 3 .
1 . .|. 8 .|. . 2
. . .|2 5 .|9 . .

Simple stuff to here.
Code:
.---------------------.---------------------.---------------------.
| 2479   249    1     | 8      6      3     | 25     279    57    |
| 5      369    369   | 1      7      2     | 368    689    4     |
| 2367   8      2367  | 5      4      9     | 1236   1267   1367  |
:---------------------+---------------------+---------------------:
| 24     1      24    | 6      3      8     | 7      5      9     |
| 369    369    369   | 7      2      5     | 148    148    18    |
| 8      7      5     | 9      1      4     | 236    26     36    |
:---------------------+---------------------+---------------------:
| 26     256    268   | 4      9      7     | 1568   3      1568  |
| 1      459    479   | 3      8      6     | 45     47     2     |
| 3467   346    34678 | 2      5      1     | 9      4678   678   |
'---------------------'---------------------'---------------------'


Hidden UR removes 6 from r3c6.
Code:
.---------------------.---------------------.---------------------.
| 2479   249    1     | 8      6      3     | 25     279    57    |
| 5      369    369   | 1      7      2     | 368    689    4     |
| 2367   8      2367  | 5      4      9     |*123-6  1267  *1367  |
:---------------------+---------------------+---------------------:
| 24     1      24    | 6      3      8     | 7      5      9     |
| 369    369    369   | 7      2      5     | 148    148    18    |
| 8      7      5     | 9      1      4     |*236    26    *36    |
:---------------------+---------------------+---------------------:
| 26     256    268   | 4      9      7     | 1568   3      1568  |
| 1      459    479   | 3      8      6     | 45     47     2     |
| 3467   346    34678 | 2      5      1     | 9      4678   678   |
'---------------------'---------------------'---------------------'


JSudoku eliminates the 5 in r7c2 with an xy-x chain.
This is the step where I want something else. xy-x chains, I don't want to use.
(And I don't want to learn them yet.)

Code:
.---------------------.---------------------.---------------------.
| 2479   249    1     | 8      6      3     | 25     279    57    |
| 5      369    369   | 1      7      2     | 368    689    4     |
| 2367   8      2367  | 5      4      9     | 123    1267   1367  |
:---------------------+---------------------+---------------------:
| 24     1      24    | 6      3      8     | 7      5      9     |
| 369    369    369   | 7      2      5     | 148    148    18    |
| 8      7      5     | 9      1      4     | 236    26     36    |
:---------------------+---------------------+---------------------:
| 26     256    268   | 4      9      7     | 1568   3      1568  |
| 1      459    479   | 3      8      6     | 45     47     2     |
| 3467   346    34678 | 2      5      1     | 9      4678   678   |
'---------------------'---------------------'---------------------'


Anyone see something more fun? Thanks.
Back to top
View user's profile Send private message
keith



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

PostPosted: Sat Jul 19, 2008 7:21 am    Post subject: Reply with quote

I do not see anything other than chains.

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



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Sat Jul 19, 2008 9:16 am    Post subject: Reply with quote

My newfound friend, the extended m-wing, comes to the rescue:

One m-wing pincers (5) "a":r1c7,r8c2 via strong link # in (2):r1c2-r7c2.
It removes 5 from r8c7

Another extended m-wing "b" pincers (2) r4c1,r7c2 via strong link * (4):r1c1-r1c2.
Removes 2 from r7c1

Code:

+--------------------------+--------------------------+--------------------------+
| 24*79   2#4*9   1        | 8       6       3        | 25a     279     57       |
| 5       369     369      | 1       7       2        | 368     689     4        |
| 2367    8       2367     | 5       4       9        | 1236    1267    1367     |
+--------------------------+--------------------------+--------------------------+
| 2b4     1       24       | 6       3       8        | 7       5       9        |
| 369     369     369      | 7       2       5        | 148     148     18       |
| 8       7       5        | 9       1       4        | 236     26      36       |
+--------------------------+--------------------------+--------------------------+
|-26      2#b56   268      | 4       9       7        | 1568    3       1568     |
| 1       45a9    479      | 3       8       6        | 4-5     47      2        |
| 3467    346     34678    | 2       5       1        | 9       4678    678      |
+--------------------------+--------------------------+--------------------------+


How to find these?
In order to find coloring and/or m/w-wing eliminations, I draw little sketches:

Code:

'2':                       '4':                       '5':
+·····+·····+·····+        +·····+·····+·····+        +·····+·····+·····+
·o *  ·     ·5 o  ·        ·*-*  ·     ·     ·        ·     ·     ·2---7·
·  |  ·     ·     ·        ·     ·     ·     ·        ·     ·     ·    |·
·  |  ·     ·     ·        ·     ·     ·     ·        ·     ·     ·    |·
·  |  ·     ·     ·        ·     ·     ·     ·        ·     ·     ·    |·
·o | o·     ·o o  ·        ·     ·     ·     ·        ·     ·     ·    |·
+··|··+·····+·····+        +·····+·····+·····+        +·····+·····+····|+
·4---4·     ·     ·        ·2---2·     ·     ·        ·     ·     ·    |·
·  |  ·     ·     ·        ·     ·     ·     ·        ·     ·     ·    |·
·  |  ·     ·     ·        ·     ·     ·*-*  ·        ·     ·     ·    |·
·  |  ·     ·     ·        ·     ·     ·|    ·        ·     ·     ·    |·
·  |  ·     ·*-6  ·        ·     ·     ·|    ·        ·     ·     ·    |·
+··|··+·····+·····+        +·····+·····+|····+        +·····+·····+····|+
·6 * o·     ·     ·        ·     ·     ·|    ·        ·  *  ·     ·o   *·
·     ·     ·     ·        ·     ·     ·|    ·        ·  |  ·     ·     ·
·     ·     ·     ·        ·  o o·     ·5 7  ·        ·  *---------4    ·
·     ·     ·     ·        ·     ·     ·     ·        ·     ·     ·     ·
·     ·     ·     ·        ·o o o·     ·  o  ·        ·     ·     ·     ·
+·····+·····+·····+        +·····+·····+·····+        +·····+·····+·····+

In these sketches, I mark the positions of cells that contain a certain candidate.
Here, I've shown the drawings for "2", "4" and "5".
Whenever there is a bi-value cell, I write the other candidate into the grid,
when there is a strong link between two cells (e.g. "2" in col 2), I draw a line.
When there is no strong link, the cells are marked "o"

Looking for w-wings or (extended) m-wings:


1) First step:

look for bi-value cells that "see" a strong link
.

That is very easy (if you are a visual person like myself)
Let us look at the drawing for "2":

5 in r1c7 sees the link in col 2 ending r7c2 and the link in row 6 ending in r6c8
6 in r7c1 sees the link in col 2 ending in r1c2
6 in r7c1 sees the link in row 4 ending r4c3.

2a) second step (w-wing)

If there are two bi-value cells with the same other candidate that see the opposite ends of a strong link,
we have a w-wing.


No w-wing can be found in these drawings (the two sixes in the "2" diagram do not see the same link)

2b) second step (m-wing)

If we have found a bi-value cell that sees a strong link,
check if there is a strong link in that candidate starting in the other end of the strong link
:

e.g. that 5 in r1c7 sees the strong link col 2 (r1c2-r7c2),
the other end of the strong link is r7c2,
and indeed in the drawing for "5" we find a strong link (on 5) r7c2-r8c2. This is our first extended m-wing.
It removes 5 from r8c7.

The complete chain:
-(5=2)r1c7-r1c2=(2-5)r7c2=r8c2-;r8c7<>5

The other 3 possible m-wings are a dead end:

r6c8 has no "5" in it
r1c2 has no "6"
r4c3 has no "6"

--------

In the drawing for "4" we find:

2 in r4c1 sees strong link (4) r1c1-r1c2, there is a strong link (2) from there (r1c2-r7c2) and we have

a winner: extended m-wing -(2=4)r4c1-r1c1=(4-2)r1c2=r7c2-;r7c1<>2

The other possible m-wings are dead ends:
5 in r8c7 and 7 in r8c8 both seeing strong link (4) row 5,
4 in r8c7 seeing strong link (5) in col 2 and strong link (5) in row 1,
and 2 in r1c7 seeing strong link (5) in col 9

______

P.S. near the end, there is again a difficult position , which I solved using a possible DP 27-24-47 in cols 1 and 3. Either r3c1 or r9c1 must be 3 and that means r5c1=9.

A bit later, a UR type 1 (36) solves the puzzle
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Asellus



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

PostPosted: Sat Jul 19, 2008 9:50 am    Post subject: Reply with quote

I agree that it appears that there are only chain solutions at this point, though it looks as if some clever person might be able to find some sort of DP.

That chain elimination is interesting, however. One way to see it is as a sort of modified Skyscraper and an ER. The <2>s in c2 (at r17c2) are conjugate. And the <2> in r1c7 is conjugate with the <5> with which it shares that bivalue cell. This is like a Skyscraper on 2 but with a twist: there is a <2> pincer in r7c2; but in c7, the other pincer is the <5> in r1c7. The trick is to notice that there is an ER of <5>s in box 9.

So, the <5> in r7c2 sees the <2> pincer in the same cell and it sees the <5> pincer in r1c7 via the ER in box 9. Thus, it is eliminated.

(The <5> in r1c7 can also be "transported" or colored to r7c9 via the conjugate <5> links in r1 and c9.)

Finding these chains is what is tricky. The easiest way to find this one is with Medusa multi-coloring. Here is the grid with the coloring marked:
Code:
.--------------------.-------.-------------------.
| 2479  2b49   1     | 8 6 3 | 2a5A  279   5a7A  |
| 5     369    369   | 1 7 2 | 368   689   4     |
| 2367  8      2367  | 5 4 9 | 123   1267  1367  |
:--------------------+-------+-------------------:
| 24    1      24    | 6 3 8 | 7     5     9     |
| 369   369    369   | 7 2 5 | 148   148   18    |
| 8     7      5     | 9 1 4 | 236   26    36    |
:--------------------+-------+-------------------:
| 26    2B-56  268   | 4 9 7 | 1568  3     15A68 |
| 1     459    479   | 3 8 6 | 45    47    2     |
| 3467  346    34678 | 2 5 1 | 9     4678  678   |
'--------------------'-------'-------------------'

We have two small clusters: Aa and Bb. The weakly linked <2>s in r1 provide the weak link "ab" "bridge" between the clusters and create the strong "AB" pair. The <5> in r7c2 is trapped by the 2B in the same cell and the 5A in r7c9. All we had to do is color mark the conjugate pairs and then find that the two clusters are bridged. (Medusa multi-coloring doesn't always offer up eliminations this easily!)

Another way you might notice this chain elimination is to note the strongly linked <2>s in c2 and the strongly linked <5>s in r8, one end of each of which can see the 25 bivalue in r1c7, within which the <2> and <5> are strongly linked. These 3 strong links are weakly linked together, providing the alternating link logic:
(2)r7c2=(2)r1c2 - (2=5)r1c7 - (5)r8c7=(5)r8c2; r7c2<>5


There is an ALS elimination in the grid which doesn't appear to be very helpful: ALS1 is the 34569 of r2589c2 and ALS2 is the 45 of r8c7. The shared exclusive digit is <5>. The <4> in r8c3 is eliminated because it can see the 3 shared common <4>s in r89c2 and r8c7. (This can also be seen as APE: the <4> in r8c3 cannot form an acceptable pair with any of the digits in r8c2.)
Back to top
View user's profile Send private message Visit poster's website
wapati



Joined: 10 Jun 2008
Posts: 472
Location: Brampton, Ontario, Canada.

PostPosted: Sat Jul 19, 2008 6:10 pm    Post subject: Reply with quote

Whew, hard slogging! I have printed out this thread, up to here, and will go over it with care.

Thanks for the efforts, all of you. Very Happy
Back to top
View user's profile Send private message
keith



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

PostPosted: Sat Jul 19, 2008 7:36 pm    Post subject: Reply with quote

Quote:
Whenever there is a bi-value cell, I write the other candidate into the grid,
when there is a strong link between two cells (e.g. "2" in col 2), I draw a line.
When there is no strong link, the cells are marked "o"


nataraj,

What is "*"? It seems to me it is the same as "o, except it is on an end of a strong link. If so, why use "*" and not just "o"?"

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



Joined: 18 Oct 2007
Posts: 1741

PostPosted: Sat Jul 19, 2008 7:41 pm    Post subject: Reply with quote

Quote:
though it looks as if some clever person might be able to find some sort of DP.



I was thinking the same thing, lots of cells with similar candidates. I went and read over myth's tutorial on MUGs. still scratching my head over this puzzle. hopefully Myth has some insight.

I know Keith posts the susser steps sometimes... sudocue (rudd's site solver) has a medusa bridge as a first move, then its
UR
xy-wing
2 xy-chains.
Back to top
View user's profile Send private message
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Sat Jul 19, 2008 8:25 pm    Post subject: Reply with quote

keith wrote:
nataraj,

What is "*"? It seems to me it is the same as "o, except it is on an end of a strong link. If so, why use "*" and not just "o"?"


On P&P, I mark the multi-candidate cells with a simple dot, but the ends of a strong link with a big dot (like a filled circle). Don't know why..., to make them stand out more ? The "*" and "o" seemed to be a good representation of the two markings. But, as I said, don't know why I use different marks...

Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



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

PostPosted: Sat Jul 19, 2008 8:33 pm    Post subject: Reply with quote

Quote:
But, as I said, don't know why I use different marks...


Let me guess that it helps when you are looking across the diagrams for different candidates. If there is a "*" in the same place in two different candidate grids, it may be a place where the chained candidate flips. So, the * rather than o might help in recognizing patterns that connect across diagrams.

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 -> 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