Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Tue May 16, 2006 7:07 pm

RW wrote:To clarify my chain:
if r6c3=3 => r7c3<>3 => r8c3<>3 => r8c1=3 (=> r6c1=7 => r8c3=7 => UR: r6c3<>3)

Thanks for the explanation. It's a lot clearer when r78c3 are listed in the chain. Months ago I wouldn't have believed I would today prefer nice loop notation,:) which for this example might be ...

r6c3-3-r78c3=3=(AUR:r8c1=5|7=r6c3), implying r6c3<>3

RW wrote:I would call it a UR because I can make the elimination without taking any steps outside the pattern

When the chain uses cells outside the UR (the outside cells being r78c3 above) and the elimination is not in the "outside cell(s)", that sure seems like taking a "step outside" to me. IMO it's similar to your reasoning for keith's recent find.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Tue May 16, 2006 7:26 pm

ronk wrote:
RW wrote:I would call it a UR because I can make the elimination without taking any steps outside the pattern. IMO it's similar to your reasoning for keith's recent find.


When the chain uses cells outside the UR (the outside cells being r78c3 above)


I actually wrote:I would call it a UR because I can make the elimination without taking any steps outside the pattern (excluding the elimination steps, which I don't count as steps anyway).


The way I see it the chain would be if r6c3=3 => r8c1=3 => r6c1=7 => r8c3=7, no cells outside the pattern. Keiths example required to solve a third number 'c' outside the pattern, which is why I think it's different. But this is only terminology, not the most important issue here. Just like I like to complete the deadly pattern and make the reduction because I managed to do that, while friends of the AUR likes to almost complete it, make a reduction that prevents it from being completed and find a contradiction based on that. Same thing, solves the puzzle anyway.:)

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Tue May 16, 2006 7:58 pm

RW wrote:The way I see it the chain would be if r6c3=3 => r8c1=3 => r6c1=7 => r8c3=7, no cells outside the pattern.

For the highlighted inference above:

Since r6c3 and r8c1 are not in the same row, column, or box ... and the UR inference is either r6c3<>7 => r8c1=5 ... or r8c1<>5 => r6c3=7 ... you are implicitly using other cells (in box 7), even if you choose not to write them down.

RW wrote:Keiths example required to solve a third number 'c' outside the pattern, which is why I think it's different.

And yours requires the UR number 'a' not to exist in certain cells of one box containing the pattern, which is why I think it's the same.

RW wrote:But this is only terminology, not the most important issue here.

Agreed, but not listing all the cells involved in the deduction doesn't aid communication.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Tue May 16, 2006 9:36 pm

this simple xy cycle also cracks the puzzle
Code: Select all
r5c1=5 r4c2=1 r8c2=5 r8c9=9 r4c9=7 r5c8=5  =>  r5c1<>5
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mike Barker » Sun Jun 04, 2006 11:00 pm

For those of you who are experiencing UR technique withdrawl, here's something to ponder.

Ron asked for an example of:
Code: Select all
abc  ab    .   | abY  .      .     
.    .     .   | .    .      .     
.    abc   .   | ab   .      .     

abc in the intersection of the AUR's abY row and the AUR's abc box
excludes 'a' and 'b' from abY

I'm having an even more fundamental problem. I've been trying to find an example of a type 5 UR and have failed. Thinking about it I've come to the conclusion that they should occur infrequently. My arguement is somewhat weak, but here goes. A type 5 looks like:
Code: Select all
ab   abc
abc  ab

The key is the missing "c" from the top-left "ab" or equally the bottom-right "ab". If the "c" is missing then there must be something usually in its row, column, or box which eliminates it, but if the "c" is eliminated from something in its row then the "c" in the top-right "abc" will very likely be eliminated as well distroying the type 5; if by something in its column, then the "c" in the bottom-left "abc" will very likely be eliminated; and if by something in its box, then the "c" in which ever "abc" shares a box with the "ab". It is possble for a "c" to be eliminated, for example, a UR+4X/2SL can remove a "c" without affecting other UR cells. Even if the Type 5 UR exists, then there still must be a "c" in one of the 4 cells where eliminations can occur for the Type 5 to register in my solver. The closest I have come is what's been called a UR+3x where one only "c" is missing:
Code: Select all
+-------------------+----------------+------------------+
|   169  257  12569 |  679    3    4 |  1567   8     56 |
|   368  378    368 |    1   57   56 |     4   9      2 |
|     4   57   1569 |  679    8    2 |  1567  13    356 |
+-------------------+----------------+------------------+
|  *138 -2348     7 |    5   24 *138 |    19   6     49 |
|     5     9    12 |   67  247   16 |     3  14      8 |
|  *138     6   148 |   48    9  *13 |     2   5      7 |
+-------------------+----------------+------------------+
|  3689  358  35689 |    2    1    7 |   569  34  34569 |
|     2   45    459 |    3    6   59 |     8   7      1 |
|     7    1    369 |   48   45  589 |   569   2   3569 |
+-------------------+----------------+------------------+


Also, believe it or not, we missed one more UR elimination. It fits between Keith's ALS technique and the strong link techniques:

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

For Example:
Code: Select all
+---------------+---------------+----------------+
|    5    1   2 |   3    8    7 |  49    49    6 |
|    3    7   4 |   9    6    5 |   8    12   12 |
|   68   68   9 |   1    2    4 |   3     5    7 |
+---------------+---------------+----------------+
|  489    3  16 |  46    7  @89 |   2   149    5 |
|    2  489   7 |   5 -149 *189 |   6     3  149 |
|   49    5  16 |   2    3   16 |  49     7    8 |
+---------------+---------------+----------------+
|  469  469   5 |   7  #49    2 |   1     8    3 |
|    7    2   3 |   8 *149 *169 |   5   469   49 |
|    1   49   8 | #46    5    3 |   7  2469  249 |
+---------------+---------------+----------------+

UR+4X/1SL: r58c56, ALS1=r9c4|r7c5, ALS2=r4c6, r5c5=1=r8c5, => r5c5<>9


I've updated the list of techniques.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ravel » Mon Jun 05, 2006 8:18 am

Mike Barker wrote:The key is the missing "c" from the top-left "ab" or equally the bottom-right "ab"...

What about 2 turbot fishes to make the 2 single eliminations of c?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Fri Jun 16, 2006 3:56 am

Mike Barker wrote: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

The "Z" of "abZ" may be considered an extra ...
Code: Select all
 ab     abX
         |
        b|
     a   |
abY-----ab(Z)

... meaning a UR+2/2SL is valid too ...
Code: Select all
 ab     abX
         |
        b|
     a   |
abY-----ab

... although such a thing may not exist.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Fri Jun 16, 2006 1:54 pm

In this case you've discovered a siamese UR (2 UR+2D/1SL in one):
Code: Select all
ab     abX
         |
         |
     a   |
abY-----ab
eliminates "a" from "abX"

Code: Select all
ab     abX
         |
       b |
         |
abY-----ab
eliminates "b" from "abY

so although the "Z" doesn't technically need to exist, without it the pattern degenerates.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Fri Jun 16, 2006 2:10 pm

Mike Barker wrote:In this case you've discovered a siamese UR (2 UR+2D/1SL in one): (...) so although the "Z" doesn't technically need to exist, without it the pattern degenerates.

The subtle point was that the UR+2/2SL ...
Code: Select all
 ab     abX
         |
        b|
     a   |
abY-----ab

allows one to remove "a" in cells common to "ab" and "abY" ... and remove"b" in cells comon to "ab" and "abX". Treating it as 2 separate UR+2D/1SL units does not. But it's no biggie, as I think they're very rare.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Fri Jun 01, 2007 3:50 am

Ron came up with a very nice BUG Lite elimination as part of a solution to U#32. I was surprised that my solver didn't flag it. After looking at it I realized that it was actually based off of a "new" type of UR elimination (most anything you can do with a UR you can do with a BUG-Lite). Its a degenerate form of a UR+3C/2SL so I'd call it a UR+2C/2SL where both strong links share a bivalue node and have equal labels and the non-bivalue cells are diagonal => "b" can be removed from the lower right "ab" and "a" from both "abX" and "abY".
Code: Select all
 ab     abX
         |
        a|
     a   |
abY-----ab


There is also a UR+3C/3SL where the links with equal labels share the bivalue node. In this case "b" can be eliminated from "ab" as well as "a" from "abX" and "abY":
Code: Select all
 abZ     abX
 |       |
 |b     a|
 |   a   |
abY-----ab


I'd figured we had found all the URs out there - I wonder what else is waiting to be discovered, a disjoint endofin UR?
Last edited by Mike Barker on Sun Jun 03, 2007 3:17 pm, edited 1 time in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Re: Uniqueness Type 6 - UR meets X-Wing

Postby Sudtyro » Sun Jun 03, 2007 4:11 pm

Ruud wrote:So, to formulate uniqueness type 6:
When a rectangle can be found in a single floor or tower, with candidates a and b as the only possibilities in 2 of its corners, and candidates a and b are also present in the other 2 corners along with extra candidates, and the candidates for digit a form an X-Wing pattern, then candidate a can be removed from the 2 corners with extra candidates.


I may be seeing things, but the Sudopedia Article on Uniqueness Test 6 appears to incorrectly eliminate candidate "b" from the two corners with the extra candidates.
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Mike Barker » Sun Jun 03, 2007 7:06 pm

You are correct, digit "a" should be eliminated. The other issue is that the article requires strong links in both rows and columns. In fact, as Ron pointed out, only one strong link is required. In the following "a" can be eliminated from "abY". If there was a strong link from either "ab" to "abY" then "a" could also be eliminated from "abX"
Code: Select all
 ab     abX
         |
        a|
         |
abY     ab
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sun Jun 03, 2007 8:23 pm

Mike Barker wrote:Its a degenerate form of a UR+3C/2SL so I'd call it a UR+2C/2SL where both strong links share a bivalue node and have equal labels and the non-bivalue cells are diagonal => "b" can be removed from the lower right "ab" and "a" from both "abX" and "abY".
Code: Select all
 ab     abX
         |
        a|
     a   |
abY-----ab

Those same exclusions are available in two steps.
Code: Select all
 ab     abX
         |
        a|
         |
abY     ab

excludes 'a' from the 'abY' cell


 ab     abX
 
 
     a
abY-----ab

excludes 'a' from the 'abX' cell

I didn't think we were creating new types in order to combine steps. [edit: OTOH if we were documenting placements (inclusions), then the deduction for the UR+2C/2SL would be ... place 'a' in the lower right 'ab' cell.

P.S. I corrected that UR "Type 6" error on sudopedia.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby re'born » Tue Aug 28, 2007 11:02 am

The following UR pattern was noticed by Keith recently here and doesn't seem to be a part of this thread (where a partial classification of UR patterns is listed on page 3 by Mike Barker).
Code: Select all
--------------------------
ab       |    aby        |
         |               |
abx      |    ab       ax|
--------------------------

From this pattern we may conclude that the cell containing (aby) has value y. In fact, the potential deadly pattern implies (abx) is x or (aby) is y. If (abx) is x, then the above picture gives (aby) is y.

For convenience, here is the puzzle Keith used to demonstrate this phenomenon:
Code: Select all
.---------------------.---------------------.---------------------.
| 9      16     1367  | 4      167    5     | 12368  12     1678  |
| 1367   8      5     | 9      167    2     | 136    4      167   |
| 167    4      2     | 3      8      16    | 5      9      167   |
:---------------------+---------------------+---------------------:
| 2      9      168   | 56     156    146   | 148    7      3     |
| 1678   16     4     | 2      3      167   | 9      15     158   |
| 5      3      17    | 8      9      147   | 14     6      2     |
:---------------------+---------------------+---------------------:
| 16     2      9     | 56     4      8     | 7      3      156   |
| 4      5      16    | 7     *26     3     |*126    8      9     |
| 38     7      38    | 1     *256    9     |*26    &25     4     |
'---------------------'---------------------'---------------------'

There are some easy generalizations using ALS's, so I perhaps this is worth thinking about a little.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby RW » Tue Aug 28, 2007 11:33 am

That one has already been classified by Mike Barker as an UR+2kd. See here. Very nice example of the technique in action.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

PreviousNext

Return to Advanced solving techniques