Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles

Postby Havard » Sat Apr 22, 2006 5:53 pm

ronk wrote:
Havard wrote:Unique Rectangle with 1 Strong Link not connecting the in-line extras: (Mike Barkers discovery)

Your example has a conjugate link between the same two cells for each UR digit.
Code: Select all
 
 .    ab   .   | .    ab   .   
      ||       |               
 .   a||b  .   | .    .    .   
      ||       |               
 .    ab+X .   | .    ab+Y .
         
 Excludes UR digits a and b from the ab+Y cell

Therefore, both the 1 and 6 may be excluded from r4c1.


crazy! Well spotted ronk!:)
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Sat Apr 22, 2006 10:27 pm

There are actually 3 flavors of Type 5 (UR+3/2strong links). The first Havard presented:
Code: Select all
 ab====abX
 |  a  ||
 |    b||
 |     ||
abY----abZ

Allows elimination of "a" from "abY". The second
Code: Select all
 ab====abX
 |  a   |
 |      |
 |  b   |
abY====abZ

also allows elimination of "a" from "abY". And lastly
Code: Select all
 ab====abX
 |  a   |
 |      |
 |  a   |
abY====abZ

allows elimination of "b" from "abZ". I'll modify the type descriptions to distinguish these (only because when I went to implement Type 5 I missed the last two options at first). I'll also take a cut at adding Myth's nomenclature so we can decide which we prefer
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Sat Apr 22, 2006 10:58 pm

Mike Barker wrote:There are actually 3 flavors of Type 5 (UR+3/2strong links). The first Havard presented:
Code: Select all
 ab====abX
 |  a  ||
 |    b||
 |     ||
abY----abZ

Allows elimination of "a" from "abY". The second
Code: Select all
 ab====abX
 |  a   |
 |      |
 |  b   |
abY====abZ

also allows elimination of "a" from "abY". And lastly
Code: Select all
 ab====abX
 |  a   |
 |      |
 |  a   |
abY====abZ

allows elimination of "b" from "abZ". I'll modify the type descriptions to distinguish these (only because when I went to implement Type 5 I missed the last two options at first). I'll also take a cut at adding Myth's nomenclature so we can decide which we prefer


Now this is exactly why I love this forum so much! Great work Mike!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Sun Apr 23, 2006 9:05 pm

Keith has written anIntroduction to Unique Rectangles. Here's a shot at all of the UR options based on Myth's nomenclature. Because the descriptions of the different types are important, I've added some additional labeling which isn't strictly necessary, for example the "X" in UR2X/1SL to distinguish where the strong link is located. In addition, "Type x" refer to the historical typing definitions.

UR+1 (Type 1): one UR cell with extra candidates => "ab" can be removed from "abX"
Code: Select all
ab     ab
ab     abX

UR+2: two UR cells with extra candidate(s)
--- UR+2x (Type 2/2b): two cells with the same one extra candidate in a line => "x" can be removed from all cells common to the "abx"
Code: Select all
ab     ab
abx    abx

--- UR+2d (Type 5): two cells with the extra candidate diagonal to each other => "x" can be removed from all cells common to the "abx" (given the rightmost "abx" and "ab" share a box, then at the "*")
Code: Select all
 * * ab  |  abx
     abx |  ab  * *

--- UR+2X (Type 3/3b): two cells with one or more, not necessarily equivalent, extra candidates => treat "abX" as "X+Y" and "abY" as "abX+Y" and perform naked and hidden set reductions in the unit(s) containing these cells except for these cells.
Code: Select all
ab      ab
abX     abY

--- UR+2D: two cells with extra candidates diagonal to each other such that "X+Y"="xy" and a naked "xy" common the "abX" and "abY" => eliminate "xy" from the cell common to all three (given "abX" and the rightmost "ab" share a box then at the "*")
Code: Select all
ab   |  abX
abY  |  ab  xy *

UR+2/1SL: two UR cells with extra candidates, strong link between two cells
--- UR+2X/1SL (Type 4): link between both cells with extra candidates, both cells with extra candidates in a line which forms an X-wing => X-wing eliminations if not previously performed (a strong link on "a" removes "a" in cells common to the rightmost "ab" and "abX" and "a" in cells comon to the leftmost "ab" and "abY"), and "b" from "abX" and "abY"
Code: Select all
 ab     ab


     a     
abX-----abY

--- UR+2B/1SL: link between one cell with extra candidates and one bivalue cell, both cells with extra candidates in a line => a strong link on "a" removes "b" from "abY" - repeat for each strong link
Code: Select all
 ab     ab
 |
 |a
 |
abX     abY

--- UR+2D/1SL: cells with extra candidates diagonal to each other => strong link on "a" removes "a" from "abY" - repeat for each strong link
Code: Select all
 ab     abY
 |
 |a
 |
abX     ab

UR+3: three UR cells with extra candidate(s)
--- UR+3x: three cells with the same one extra candidate => "x" can be removed from all cells common to the "abx" (given the rightmost "abx" share a box, then at the "*")
Code: Select all
ab   |  abx
abx  |  abx * *

--- UR+3X: three cells with extra candidates diagonal to each other such that "X+Y+Z"="xy" and a naked "xy" common the "abX", "abY", and "abZ" => eliminate "xy" from the cell common to all four (given "abX" and "abZ" share a box then at the "*")
Code: Select all
ab   |  abX
abY  |  abZ xy *

UR+3/1SL: two or three UR cells with extra candidates (Z is optional), plus one strong link and at least one extra cell
--- UR+3x/1SL: "Y" is a single candidate "y", the extra cell "(ab)y" can include "a", and/or can include "b" if it shares a house with "abX" => "b" can be removed from "abX". Similarly, the extra cell "(ab)y" can include "b", and/or can include "a" if it shares a house with "abX" => "b" can be removed from "ab(Z)".
Code: Select all
 ab     abX
         |
         |a
         |
aby     ab(Z)  (ab)y

--- UR+3X/1SL: includes the extra cell "(ab)U..." such that "U" is a locked set which includes "Y", "abY" is seen by all of the cells of "(ab)U..." which contain elements of "Y", "(ab)U..." can contain "a", and "(ab)U..." can contain "b" if all of its cells which contain "b" are seen by "abX" => "b" can be removed from "abX". Similarly, "(ab)U..." can contain "b", and "(ab)U..." can contain "a" if all of its cells which contain "b" are seen by "abX" => "b" can be removed from "ab(Z)".
Code: Select all
 ab     abX
         |
         |a
         |
abY     ab(Z)  (ab)U...

UR+3/2SL: three UR cells with extra candidates, plus two strong links, at most one of which includes the bivalue cell
--- UR+3X/2SL: both strong links share a node, do not include the bivalue cell and have different labels which forms a continuous nice loop => strong links as shown remove "a" in cells common to "ab" and "abY", "b" in cells comon to "ab" and "abX", and "Z" in "abZ" which reduces the problem to UR+2D/1SL so "b" can be removed from "abY" and "a" can be removed from "abX"
Code: Select all
 ab     abX
         |
        b|
     a   |
abY-----abZ

--- UR+3C/2SL: both strong links share a node, do not include the bivalue cell and have equal labels => "b" can be removed from "abZ"
Code: Select all
 ab     abX
         |
        a|
     a   |
abY-----abZ

--- UR+3N/2SL: both strong links share a node, have different labels and one link includes the bivalue cell => "a" can be removed from "abY", and treat "abY" as "Y+Z" and "abZ" as "abY+Z" and perform naked and hidden set reductions in the unit(s) containing these cells except for these cells.
Code: Select all
 ab-----abX
     a   |
        b|
         |
abY     abZ

--- UR+3U/2SL: the strong links are disjoint with different labels => "a" can be removed from "abY"
Code: Select all
 ab-----abX
     a   
         
     b   
abY-----abZ

--- UR+3E/2SL: the strong links are disjoint with the same labels which forms an X-wing => X-wing eliminations if not previously performed (strong links as shown remove "a" from cells common to "ab" and "abY" and "a" in cells common to "abX" and "abZ"), and "b" from "abZ"
Code: Select all
 ab-----abX
     a   
         
     a   
abY-----abZ

UR+4/1SL: four UR cells with extra candidates, plus one strong link and at least two extra cells
--- UR+4x/1SL: "Y" and "Z" are single candidates "y" and "z", the extra cell "(ab)y" can contain "a" if it shares a house with "abW" and/or "b" if it shares a house with "abX", similarly the extra cell "(ab)z" can contain "a" if it shares a house with "abW" and/or "b" if it shares a house with "abX" => "b" can be removed from "abX".
Code: Select all
abW-----abX
     a
aby     abz  (ab)y (ab)z

--- UR+4X/1SL: includes the extra cell(s) "(ab)U..." such that "U" is a locked set which includes "Y", "abY" is seen by all of the cells of "(ab)U..." which contain elements of "Y", and "(ab)U..." can contain "a" if all of its cells which contain "a" are seen by "abW" and/or can contain "b" if all of its cells which contain "b" are seen by "abX" and similarly for "(ab)V..." where "V" is a locked set which includes "Z" => "b" can be removed from "abX".
Code: Select all
abW-----abX
     a
abY     abZ  (ab)U... (ab)V...

UR+4/2SL: three or four UR cells with extra candidates (Z is optional), plus two strong link and at least one extra cell
--- UR+4x/2SL: "Y" is a single candidate "y", the extra cell "(ab)y" can include "a", and/or can include "b" if it shares a house with "abX" => "b" can be removed from "abX".
Code: Select all
abW-----abX
     a   |
         |a
         |
aby     ab(Z)  (ab)y

--- UR+4X/2SL: includes the extra cell "(ab)U..." such that "U" is a locked set which includes "Y", "abY" is seen by all of the cells of "(ab)U..." which contain elements of "Y", "(ab)U..." can contain "a", and "(ab)U..." can contain "b" if all of its cells which contain "b" are seen by "abX" => "b" can be removed from "abX".
Code: Select all
abW-----abX
     a   |
         |a
         |
abY     ab(Z)  (ab)U...

UR+4/3SL: all four UR cells with extra candidates, plus three strong links
--- UR+4X/3SL: the links with equal labels are disjoint which forms a continuous nice loop => X-wing eliminations if not previously performed ("a" can be removed from cells common to "abX" and "abY" and cells common to "abZ" and "abW"), "Z" can be removed from "abZ", "W" can be removed from "abW" which reduces the problem to UR+2B/1SL so "b" can be removed from "abX" and "abY"
Code: Select all
abX-----abZ
     a   |
        b|
     a   |
abY-----abW

--- UR+4C/3SL: the links with equal labels share a node => "b" can be removed from "abZ"
Code: Select all
abX-----abZ
     a   |
        a|
     b   |
abY-----abW


[ronk-moderator 20110330 edit: See addendum here.]
Last edited by Mike Barker on Sat Jun 03, 2006 5:23 pm, edited 22 times in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sun Apr 23, 2006 9:11 pm

Mike Barker wrote:
Code: Select all
 ab-----ab
 |       |
 |       |
 |   a   |
abX=====abY

Mike and Havard, would you please deep-six the lines except for when there is actually a strong link?

The lines are unnecessary and then we will have the traditional single line for a strong link of one UR digit ... and can use a double line for strong links of both UR digits (between the same cells).

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sun Apr 23, 2006 10:07 pm

Done - it does look better. Also I added UR+3X/2SL which is a nice strong unique rectangle. There are more of these. Even the traditional Type 4 (UR+2X/1SL) is a continuous nice loop which means that "a" can be removed from cells common to the leftmost "ab" and "abX" and cells common to the rightmost "ab" and "abY"! I'll update the previous post to include these.
Code: Select all
 ab     ab


     a     
abX-----abY
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Mike Barker » Mon Apr 24, 2006 2:37 am

After using Myth's nomenclature there is no question that it is effective. It's also about as dry as it comes. Its like eliminating all discussion of X-wings and Turbot Fish for X-cycles or XYZ-wings for ALS. The later terminology is correct and about as colorful as a rainy day. One thing I'd like to do is to add an "S" in front of those UR with strong links and an "N" if it is also a nice loop. As far as color - okay this is tongue in cheek, but here goes:

UR+1 -> Polaris (one bright star)
UR+2 -> Gemini (two bright stars)
UR+3 -> Orion (three bright stars in the sword)
UR+2/1SL -> Aquarius (two bright stars for the strong water bearer)
UR+3/2SL -> Cygnus (a 4 node swan with two strong wings)
UR+4/3SL -> Pegasus (4 bright stars in the body of the strong horse)

Okay, I've had my fun - I don't expect anyone to use the names, but you've got to admit its more colorful this way! I checked with Martha Stewart and the correct usage is to refer to a "UR Polaris" or if you want to go to a finer resolution a "SUR Aquarius/single candidate", for example.
Last edited by Mike Barker on Mon Apr 24, 2006 3:04 pm, edited 4 times in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Mon Apr 24, 2006 3:16 am

Mike Barker wrote:--- NUR+2X/1SL (Type 4): link between both cells with extra candidates, both cells with extra candidates in a line which forms a continuous nice loop => a strong link on "a" removes "a" in cells common to the rightmost "ab" and "abX", "a" in cells comon to the leftmost "ab" and "abY", and "b" from "abX" and "abY"
Code: Select all
 ab     ab


     a     
abX-----abY

Interesting, but I wonder if any of those 'a' exclusions still exist after the application of singles, naked pairs, and line/box interaction techniques.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Mon Apr 24, 2006 4:11 pm

Mike Barker wrote:NUR+4/3SL: all four UR cells with extra candidates, plus three strong links which forms a continuous nice loop => "a" can be removed from cells common to "abX" and "abY", "Z" can be removed from "abZ", "W" can be removed from "abW" which reduces the problem to UR+2B/1SL so "b" can be removed from "abX" and "abY"
Code: Select all
abX-----abZ
     a   |
        b|
     a   |
abY-----abW


It seems the opposing strong links in the same digit would in essence be an X-wing.

Here is a different setup for a UR+4/3SL which also has a reduction
Code: Select all
abX-----abZ
     a   |
        a|
     b   |
abY-----abW

In this case, the b can be removed from the abZ cell. The side-by-side strong links are not uncommon. Here is a real life example...
Code: Select all
 
 *--------------------------------------------------------------------*
 | 56     26    *46+2   | 1458   7      9      | 3     *46+12  1248   |
 | 1      9     *46+27  | 458    3      48     | 24578 *46+27  248    |
 | 357    37     8      | 145    2      6      | 457    147    9      |
 |----------------------+----------------------+----------------------|
 | 4      2378   1      | 78     5      2378   | 289    239    6      |
 | 368    5      9      | 468    1468   12348  | 248    234    7      |
 | 3678   23678  2367   | 46789  4689   23478  | 1      5      2348   |
 |----------------------+----------------------+----------------------|
 | 2      178    5      | 3      1489   1478   | 6      1479   14     |
 | 36789  13678  367    | 2      14689  1478   | 479    13479  5      |
 | 3679   4      367    | 679    169    5      | 279    8      123    |
 *--------------------------------------------------------------------*
...UR+4/3SL eliminates the 4 in r2c8
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Mon Apr 24, 2006 4:58 pm

Mike Barker wrote:One thing I'd like to do is to add an "S" in front of those UR with strong links and an "N" if it is also a nice loop.

I don't think either prefix 'S' or 'N' is helpful.

For the 'N', I pretty sure a nice loop expression can be written for every one of these "UR+n" deductions. I've got better things to do right now than prove that statement but, if necessary, I will do so.:D

For the 'S' and for "SUR+2/1SL", e.g., a second 'S' is simply redundant.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Mon Apr 24, 2006 5:14 pm

Myth Jellies wrote:Here is a different setup for a UR+4/3SL which also has a reduction
Code: Select all
abX-----abZ
     a   |
        a|
     b   |
abY-----abW

In this case, the b can be removed from the abZ cell. The side-by-side strong links are not uncommon.

With my solver, that configuration yields 105 exclusions from the top1465 puzzles. That's after every other logic technique ... including every other uniqueness reduction ... is applied. [edit: Only puzzle #1270 was incrementally advanced to a solution with this configuration.]

Compared to the zero exclusions for the other configuration ...
Code: Select all
abX-----abZ
     b   |
        a|
     b   |
abY-----abW

The a can be excluded from the abX and abY cells.

... that's impressive, MJ. Great find!
Last edited by ronk on Mon Apr 24, 2006 1:38 pm, edited 3 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Mon Apr 24, 2006 5:15 pm

I did not look through all these types and i never could keep them in my mind.
[Edit: gsf pointed out, that a 7 is missing in my grid]
Code: Select all
 *--------------------------------------------------------------------*
 | 56     26     462    | 1458   7      9      | 3      4612   1248   |
 | 1      9      4627   | 45+8   3      48     | 45+278 4627   248    |
 | 357    37     8      | 45+1   2      6      | 45+7   #147    9      |
 |--------------------------------------------------------------------|
 | 4      2378   1      | 78     5      2378   | 289    239    6      |
 | 368    5      9      | 468    1468   12348  | 248    234    7      |
 | 3678   23678  2367   | 46789  4689   23478  | 1      5      2348   |
 |----------------------+----------------------+----------------------|
 | 2      178    5      | 3      1489   1478   | 6      1479   14     |
 | 36789  13678  367    | 2      14689  1478   | 479    13479  5      |
 | 3679   4      367    | 679    169    5      | 279    8      123    |
 *--------------------------------------------------------------------*

But since its going crazy anyway: what about the elimination rep'nA found in the grid MJ showed above? You have 2 strong links for the 5 and a "finned" strong link for the 4 to eliminate 4 in r2c7.
Last edited by ravel on Mon Apr 24, 2006 5:21 pm, edited 2 times in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Mike Barker » Mon Apr 24, 2006 7:40 pm

I've made the updates (S and N are gone and added MJ's new technique). I'm not sure how rep'nA's find fits in. We may be looking at a whole new constellation. As I see it the problem looks like:
Code: Select all
abX--|--abZ
     | a |
     |   |a
     |   |
aby  |  abW  by

where "y" is a single candidate, "abZ" and "by" share a box, and "b" is eliminated from "abZ". Hopefully someone can come up with a better description.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby gsf » Mon Apr 24, 2006 8:10 pm

ravel wrote:
Code: Select all
 *--------------------------------------------------------------------*
 | 56     26     462    | 1458   7      9      | 3      4612   1248   |
 | 1      9      4627   | 45+8   3      48     | 45+278 4627   248    |
 | 357    37     8      | 45+1   2      6      | 45+7   #14    9      |
 |--------------------------------------------------------------------|
 | 4      2378   1      | 78     5      2378   | 289    239    6      |
 | 368    5      9      | 468    1468   12348  | 248    234    7      |
 | 3678   23678  2367   | 46789  4689   23478  | 1      5      2348   |
 |----------------------+----------------------+----------------------|
 | 2      178    5      | 3      1489   1478   | 6      1479   14     |
 | 36789  13678  367    | 2      14689  1478   | 479    13479  5      |
 | 3679   4      367    | 679    169    5      | 279    8      123    |
 *--------------------------------------------------------------------*


does the solution to this grid include r3c8=7?
Last edited by gsf on Mon Apr 24, 2006 4:17 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Mon Apr 24, 2006 8:13 pm

Mike Barker wrote:I've made the updates (S and N are gone and added MJ's new technique).

Thanks Mike.

Mike Barker wrote:I'm not sure how rep'nA's find fits in. We may be looking at a whole new constellation. As I see it the problem looks like:
.............

When the complexity increases to some level, I think we've crossed over from URs to Almost-Unique-Rectangles (AURs). I don't know exactly at what level that occurs, but when a bivalued cell (other than within the UR) is required for a deduction... I've got to believe we're there. Indeed, for that reason, I've always felt that the Type 3 UR should never have been defined as a UR ... but that's history.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques