## Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles
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

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

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

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     abab     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     ababx    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      ababX     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   |  abXabY  |  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   |  abxabx  |  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   |  abXabY  |  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      aaby     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      aabY     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

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

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

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

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

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

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.

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

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

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

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

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

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