Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles

Re: Questions

Postby Havard » Sat Apr 15, 2006 3:39 pm

keith wrote:Question 2:

Havard wrote:
Type 3: UR with two extra candidates in addition to the UR-pair. Can create a locked set with other cells, as long as all the UR-extra-candidates-cells are concidered one cell in the locked set, and of course all cells in the locked set can see eachother...


Would it not be more accurate to say that the UR-pair is one cell in the locked set? Since the UR-pair can occupy only one of two cells in the UR. Then, the locked set of 2+N possibilities will only occupy 1+N cells?

To say it another way: The extra candidates will be fully represented in the solution of the locked set. Only one (of two) of the UR candidates will be there.

Thanks to all,

Keith


Hi Keith!

I guess I was thinking in very general terms, and that it is possible for the type 3 to have extra candidates in three cells:
Code: Select all
           *
          xy
 abxy---abxy
  |      |
  |      |
  |      |
 ab-----abxy


Code: Select all
. . . | . . * | . . .
. . . | . . xy| . . .
. . . | xy--xy| . . .
------+-|---|-+------
. . . | | . | | . . .
. . . |ab---xy| . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .


As you can see from these illustrations, the * can not be either x or y, because that would with the xy cell eliminate all xy's in the UR, and make a deadly pattern! As you can see, this would only apply for this special case, and would only ever be able to eliminate in one cell, but I still think it is worth mentioning, and that is why I generalised my description of the type 3 to not just include two cells:)

havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Sat Apr 15, 2006 5:16 pm

Type 9 is also a continuous nice loop. If the nodes are numbered starting with the bottom left then
Code: Select all
xabx====xabx
 ||   a  ||
 ||b    b||
 ||      ||
xabx----xabx

N1=b=N2=a=N3=b=N4-b-N1 => N2,N3={ab}

Also b can be eliminated from the cells in the line containing N1 and N4 excluding N1 and N4. The UR is now type 6. I wonder if this is why Ron didn't see any Type 9 URs or maybe they are just rare?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Another Type-6 Example

Postby keith » Sat Apr 15, 2006 8:34 pm

Found in the wild, another Type-6 Unique X-wing.

http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?t=669

I would be interested in how to classify the other UR in this puzzle.

By the way, in the tests of frequency of Type-6, do we know how many have just one conjugate link, and are not X-wings?

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby Myth Jellies » Sat Apr 15, 2006 8:56 pm

Keith, you could have performed either a type 3 or a type 4 (what you did) reduction on that efgh rectangle. The type 3 reduction would note the virtual 24 naked pairing in ghi and eliminate the 24's in all other cells in the box/row.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sat Apr 15, 2006 9:21 pm

Myth Jellies wrote:Keith, you could have performed either a type 3 or a type 4 (what you did) reduction on that efgh rectangle. The type 3 reduction would note the virtual 24 naked pairing in ghi and eliminate the 24's in all other cells in the box/row.

I agree, and since exclusions due to type 4 "destroy" the type 3 UR, most programmed solvers first perform exclusions due to type 3, if any.

keith wrote:By the way, in the tests of frequency of Type-6, do we know how many have just one conjugate link, and are not X-wings?

If you're asking about URs where the only extra candidates are on a diagonal, I earlier reported 28 candidates excluded (in the top1465) due to "type 7" versus 8 candidates for type 6. Note that type 6 had priority over type 7, and if the type 6 UR technique had been disabled, 4 of the 8 type 6 exclusions might have been reported as type 7.

I should also point out that almost every other logical technique had a crack at the puzzles BEFORE the uniqueness technique.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Type-1 and Type-6

Postby keith » Mon Apr 17, 2006 2:12 am

There is a UR in Ruud's Nightmare of April 17 that is both Type-1 and Type-6.

http://www.sudocue.net/forum/viewtopic.php?t=114

Of course, the Type-1 reduction forces the placement of the values <3>, whether you recognize the Type-6 or not.

Best wishes,

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Re: Type-1 and Type-6

Postby ronk » Mon Apr 17, 2006 4:00 am

keith wrote:There is a UR in Ruud's Nightmare of April 17 that is both Type-1 and Type-6.

Type 1 has extra candidates in only one cell, and type 6 has extra candidates in diagonal cells ... so how can that statement be correct?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby keith » Mon Apr 17, 2006 5:00 am

Ron,

The Type-6 pattern is, to me, an overlay of an X-wing on a UR. It is useful if the UR does not have extra possibilities on one diagonal. It does not require extra possibilities on both the other diagonal squares.

In this situation:

Code: Select all

+----------------+----------------+----------------+
| 2589 78   3    | 1    2678 2678 | 256  569  4    |
| 25   14e  14f  | 9    236  26   | 2356 7    8    |
| 289  6    79   | 4    2378 5    | 123  39   129  |
+----------------+----------------+----------------+
| 89   78   5    | 27   4    3    | 267  1    2679 |
| 34a  34b  6    | 278  1    2789 | 257  59   2579 |
| 1    2    79   | 6    5    79   | 8    4    3    |
+----------------+----------------+----------------+
| 34c  134d 148g | 5    9    4678 | 1467 2    167  |
| 6    9    248  | 2378 278  1    | 3457 358  57   |
| 7    5    1248 | 238  268  2468 | 9    368  16   |
+----------------+----------------+----------------+



abcd is an X-wing on <3>, and a UR on <34>.

a = d = <3> would force the Deadly Pattern, (b = c = <4>), so we must have b = c = <3>.

The Type-1 reduction is, of course, d = <1>.

Which sort of brings up my previous question: Are these UR classifications lists of the possibility patterns, or of the reductions?

And now, for me, to bed.

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby ronk » Mon Apr 17, 2006 12:09 pm

keith wrote:The Type-6 pattern is, to me, an overlay of an X-wing on a UR. It is useful if the UR does not have extra possibilities on one diagonal. It does not require extra possibilities on both the other diagonal squares.

I think I see your point. We only need the UR pair without any extra candidates on one diagonal.
Code: Select all
Type 1 UR:
 .  ab   .  | .  ab+(Y) .
 . a|.   .  | . a|.     .
 .  ab+X .  | .  ab     .

 Lower case indicates exactly one candidate
 Upper case indicates one or more candidates
 Parenthesis indicates "optional" candidate(s)

Rereading ...
Ruud wrote: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.

... it seems that's what Ruud said too. My bad!
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sat Apr 22, 2006 4:30 am

Based on Havard's and Keith's works I've a couple of more unique rectangles to throw into the pool. The first combines types 2 and 5:
Code: Select all
 . ab  | abx . .
 . abx | abx * *
 .  .  |   . . .
where x is a single digit common to the three "abx"
and eliminations of "x" can occur at "*"

The second may have already appeared, but I'm not finding it. It uses the strong link of type 7 with the configuration of type 4:
Code: Select all
 . ab  | ab  . .
    |  |       
 . a|  |  .  . .
    |  |       
 . abX | abY . .
where X and Y are possibly different with possibly more than one element
and the strong link on "a" allows elimination of "b" in "abY"

Also it seems that the eliminations created by a type 6 (diagonal form with an X-wing) are equivalent to those of type 7 (one strong link) where type 7 is applied twice, so it is somewhat redundant.

Based on these additions I'd recommend the following definitions for UR types:
    Type 1 (UR+1): one UR cell with extra candidates
    Type 2 (UR+2): two or three UR cells with one identical extra candidate
    2A (UR+2): two cells with the extra candidate in a box and line
    2B (UR+2): two cells with the extra candidate in a line
    2C (UR+3): three cells with the extra candidate
    2D (UR+2D): two cells with the extra candidate diagonal to each other
    Type 3: two or three UR cells with one or more, not necessarily equivalent, extra candidates in a line
    3A (UR+2): two cells with extra candidates in a box and line
    3B (UR+2): two cells with extra candidates in a line
    3C (UR+3): three cells with extra candidates
    3D (UR+2D): two cells with extra candidates diagonal to each other
    Type 4 (UR+2/1SL): two UR cells with extra candidates, strong link between two cells
    4A (UR+2A/1SL): link between both cells with extra candidates in a box and line (strong link on "a", removes "b" twice)
    4B (UR+2A/1SL): link between both cells with extra candidates in a line (strong link on "a", removes "b" twice)
    4C (UR+2B/1SL): link between one cell with extra candidates and one bivalue cell, both cells with extra candidates in a line (strong link on "a", removes "b" for each link)
    4D (UR+2C/1SL): link between one cell with extra candidates and one bivalue cell, cells with extra candidates diagonal to each other (strong link on "a", removes "a" for each link)
    Type 5 (UR+3/2SL): three UR cells with extra candidates, plus two strong links, one and only one of which includes the bivalue cell
    5A (UR+3A/2SL): both strong links share a node and have different labels
    5B (UR+3B/2SL): the strong links are disjoint with different labels
    5C (UR+3C/2SL): the strong links are disjoint with the same labels
    Type 6 (UR+4/3SL): all four UR cells with extra candidates, plus three strong links (note this degenerates because of the nice loop with exists so I don't plan to implement it, but this completes the tale anyway)

There are lots of other alternatives. The argument for the history of type 5 being the diagonal version is compelling, but with the added types (2C, 3C, 3D, and 4C) and redundancy of strong links and X-wing a contraction of the types seems appropriate.
Last edited by Mike Barker on Sat Apr 22, 2006 6:52 pm, edited 1 time in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Sat Apr 22, 2006 7:57 am

I don't know that catagorizing dozens of different kinds of UR reductions as different "types" really buys us anything. The thing to note is that you have to avoid the deadly pattern and that allows us to make various nifty reductions. It's cool that strong links can be used as an aid in this, but I don't know that I care to discern between a type 2D vs new type 5 vs old type 5.

How about just refering to these reductions as what they are: things like A UR+1; A UR+2 assisted naked pair; a UR+2 w/a locked candidate; or a UR+2 X-Wing. A little extra verbiage might avoid some future arguments and save some wear and tear on the old memory cells.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Havard » Sat Apr 22, 2006 12:59 pm

Mike Barker wrote:The second may have already appeared, but I'm not finding it. It uses the strong link of type 7 with the configuration of type 4:
Code: Select all
 . ab  | ab  . .
    |  |       
 . a|  |  .  . .
    |  |       
 . abX | abY . .
where X and Y are possibly different with possibly more than one element
and the strong link on "a" allows elimination of "b" in "abY"

Also it seems that the eliminations created by a type 6 (diagonal form with an X-wing) are equivalent to those of type 7 (one strong link) where type 7 is applied twice, so it is somewhat redundant.



Great find Mike!

Here is a puzzle that jumped out when I was fooling around a bit with the "new rules"!:)
Code: Select all
Unique Rectangle type 3:
247    1      8      | 5      379U#  6      | 3479U# 2479-  34#
9      257    256    | 47     8      34     | 1      267    356
3      457    56     | 2      79U    1      | 479U#  8      456
---------------------+----------------------+---------------------
5      37     4      | 9      137    8      | 6      17     2
27     6      9      | 147    1257   245    | 478    3      148
8      237    1      | 467    2367   234    | 5      47     9
---------------------+----------------------+---------------------
1246   9      25     | 8      1256   7      | 34     146    1346
126    258    3      | 16     4      25     | 89     169    7
146    48     7      | 3      16     9      | 2      5      1468

Unique Rectangle with 2 strong links:
247    1      8      | 5      379    6      | 3479   279    34
9      257    256U-6 | 47     8      34     | 1      267    356U
3      457    56U    | 2      79     1      | 479    8      456U
---------------------+----------------------+---------------------
5      37     4      | 9      137    8      | 6      17     2
27     6      9      | 147    1257   245    | 478    3      148
8      237    1      | 467    2367   234    | 5      47     9
---------------------+----------------------+---------------------
1246   9      25     | 8      1256   7      | 34     146    1346
126    258    3      | 16     4      25     | 89     169    7
146    48     7      | 3      16     9      | 2      5      1468

Unique Rectangle with 1 Strong Link and diagonal extras:
247     1       8       | 5       379     6       | 3479U   279     34U
9       257     25      | 47      8       34      | 1       267     356
3       457     6       | 2       79      1       | 479     8       45
------------------------+-------------------------+------------------------
5       37      4       | 9       137     8       | 6       17      2
27      6       9       | 147     1257    245     | 478     3       148
8       237     1       | 467     2367    234     | 5       47      9
------------------------+-------------------------+------------------------
1246    9       25      | 8       1256    7       | 34U     146     1346U-3
126     258     3       | 16      4       25      | 89      169     7
146     48      7       | 3       16      9       | 2       5       1468


None of the steps is really that useful, but I thought it would be good to see som "live" examples of all this theory!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Havard » Sat Apr 22, 2006 1:03 pm

here is a few more:

Code: Select all
Unique Rectangle with 1 Strong Link not connecting the in-line extras: (Mike Barkers discovery)
8        4        39       | 13       5        6        | 7        2        19
7        1        2        | 4        9        8        | 6        5        3
69       36       5        | 7        12       23       | 89       48       149
---------------------------+----------------------------+---------------------------
13469U-6 5        8        | 1369     146      349      | 2        16U      7
169      67       79       | 1569     126      259      | 4        3        8
1346U    2        34       | 8        7        34       | 59       16U      59
---------------------------+----------------------------+---------------------------
2        78       47       | 56       468      1        | 3        9        45
345      38       6        | 59       48       459      | 1        7        2
45       9        1        | 2        3        7        | 58       48       6

Unique Rectangle with 2 strong links:
8       4       39      | 13      5       6       | 7       2       19
7       1       2       | 4       9       8       | 6       5       3
69      36      5       | 7       12      23      | 89      48      149
------------------------+-------------------------+------------------------
1349    5       8       | 1369    146     349     | 2       16      7
169     67      79      | 1569U-9 126     259U    | 4       3       8
1346    2       34      | 8       7       34      | 59      16      59
------------------------+-------------------------+------------------------
2       78      47      | 56      468     1       | 3       9       45
345     38      6       | 59U     48      459U    | 1       7       2
45      9       1       | 2       3       7       | 58      48      6
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Havard » Sat Apr 22, 2006 4:45 pm

heh, I also found this one...

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


Now I have put UR's way up front in my solver, but it came out with these steps (all in this puzzle, only UR-eliminations shown)


Code: Select all
Unique Rectangle type 2:
2       479     3       | 469     8       1       | 4579-9  45679   5679
8       49      1       | 7       4569    4569    | 2       469     3
5679    479     4567    | 2349    249     2349    | 1       479     8
------------------------+-------------------------+------------------------
1       6       9       | 5       3       7       | 8       2       4
4       278     57U     | 2689    269     2689    | 579U    3       1
357     2378    57U     | 1       249     2489    | 579U    5679-9  5679-9
------------------------+-------------------------+------------------------
3679    3479    467     | 3469    1       34569   | 34579-9 8       2
379     5       2478    | 23489   2479    23489   | 6       1       79
3679    1       24678   | 234689  245679  2345689 | 34579-9 4579    579


Unique Rectangle with 1 Strong Link not connecting the in-line extras:
2       479     3       | 469     8       1       | 457     45679   5679
8       49      1       | 7       4569    4569    | 2       469     3
5679    479     4567    | 2349    249     2349    | 1       479     8
------------------------+-------------------------+------------------------
1       6       9       | 5       3       7       | 8       2       4
4       278     57U     | 2689    269     2689    | 579U    3       1
357     2378    57U     | 1       249     2489    | 579U-7  567     567
------------------------+-------------------------+------------------------
3679    3479    467     | 3469    1       34569   | 3457    8       2
379     5       2478    | 23489   2479    23489   | 6       1       79
3679    1       24678   | 234689  245679  2345689 | 3457    4579    579


Unique Rectangle with 1 Strong Link and diagonal extras:
2       79U     3       | 69      8       1       | 4       5679U-7 567
8       49      1       | 7       4569    4569    | 2       69      3
5       479U    6       | 2349    249     2349    | 1       79U     8
------------------------+-------------------------+------------------------
1       6       9       | 5       3       7       | 8       2       4
4       28      57      | 2689    269     2689    | 579     3       1
3       28      57      | 1       249     2489    | 59      567     567
------------------------+-------------------------+------------------------
679     3       4       | 69      1       569     | 57      8       2
79      5       28      | 23489   2479    23489   | 6       1       79
679     1       28      | 2689    25679   25689   | 3       4       579


Unique Rectangle with 1 Strong Link not connecting the in-line extras:
2       79      3       | 69      8       1       | 4       569     567
8       49      1       | 7       4569    4569    | 2       69      3
5       479     6       | 2349    249     2349    | 1       79      8
------------------------+-------------------------+------------------------
1       6       9       | 5       3       7       | 8       2       4
4       28U     57      | 2689    269     2689U-2 | 579     3       1
3       28U     57      | 1       249     2489U   | 59      567     567
------------------------+-------------------------+------------------------
679     3       4       | 69      1       569     | 57      8       2
79      5       28      | 23489   2479    23489   | 6       1       79
679     1       28      | 2689    25679   25689   | 3       4       579


Unique Rectangle with 1 Strong Link not connecting the in-line extras:
2      79     3      | 69     8      1      | 4      569    567
8      49     1      | 7      4569   4569   | 2      69     3
5      479    6      | 2349   249    2349   | 1      79     8
---------------------+----------------------+---------------------
1      6      9      | 5      3      7      | 8      2      4
4      28     57     | 2689   269    689    | 579    3      1
3      28     57     | 1      249    2489   | 59     567    567
---------------------+----------------------+---------------------
679    3      4      | 69     1      569    | 57     8      2
79U    5      28     | 23489  2479   23489  | 6      1      79U
679U-7 1      28     | 2689   25679  25689  | 3      4      579U


Unique Rectangle with 1 Strong Link and diagonal extras:
2       79      3       | 69      8       1       | 4       569     567
8       49      1       | 7       4569    4569    | 2       69      3
5       479     6       | 2349    249     2349    | 1       79      8
------------------------+-------------------------+------------------------
1       6       9       | 5       3       7       | 8       2       4
4       28      57      | 2689    269     689     | 579     3       1
3       28      57      | 1       249     2489    | 59      567     567
------------------------+-------------------------+------------------------
679U    3       4       | 69U     1       569     | 57      8       2
79      5       28      | 23489   2479    23489   | 6       1       79
69U     1       28      | 2689U-6 25679   25689   | 3       4       579


Unique Rectangle with 2 strong links:
2       79      3       | 69      8       1       | 4       569     567
8       49      1       | 7       4569    4569    | 2       69      3
5       479     6       | 2349    249     2349    | 1       79      8
------------------------+-------------------------+------------------------
1       6       9       | 5       3       7       | 8       2       4
4       28      57      | 2689    269     689     | 579     3       1
3       28      57      | 1       249     2489    | 59      567     567
------------------------+-------------------------+------------------------
679     3       4       | 69      1       569     | 57      8       2
79      5       28      | 23489   2479U-9 23489   | 6       1       79U
69      1       28      | 289     25679U  25689   | 3       4       579U


Unique Rectangle with 3 strong links:
2        79       3        | 69       8        1        | 4        569      567
8        49       1        | 7        4569     4569     | 2        69       3
5        479      6        | 2349U    249      2349U-4  | 1        79       8
---------------------------+----------------------------+---------------------------
1        6        9        | 5        3        7        | 8        2        4
4        28       57       | 2689     269      689      | 579      3        1
3        28       57       | 1        249      2489     | 59       567      567
---------------------------+----------------------------+---------------------------
679      3        4        | 69       1        569      | 57       8        2
79       5        28       | 23489U   247      23489U-4 | 6        1        79
69       1        28       | 289      25679    25689    | 3        4        579


Unique Rectangle type 1:
2        79       3        | 69       8        1        | 4        569      567
8        49       1        | 7        4569     4569     | 2        69       3
5        479      6        | 234      249      239      | 1        79       8
---------------------------+----------------------------+---------------------------
1        6        9        | 5        3        7        | 8        2        4
4        28       57       | 28       269      689      | 579      3        1
3        28       57       | 1        249      2489     | 59       567      567
---------------------------+----------------------------+---------------------------
679      3        4        | 69       1        569      | 57       8        2
79       5        28U      | 2348U-28 247      2389     | 6        1        79
69       1        28U      | 28U      25679    25689    | 3        4        579


Unique Rectangle with 1 Strong Link not connecting the in-line extras:
2        79       3        | 69       8        1        | 4        569      567
8        49       1        | 7        4569     4569     | 2        69       3
5        479      6        | 234      249      239      | 1        79       8
---------------------------+----------------------------+---------------------------
1        6        9        | 5        3        7        | 8        2        4
4        28       57       | 28       269      689      | 579      3        1
3        28       57       | 1        249      2489     | 59       567      567
---------------------------+----------------------------+---------------------------
679      3        4        | 69       1        569      | 57       8        2
79       5        28U      | 34       247      2389U    | 6        1        79
69       1        28U      | 28       25679    25689U-2 | 3        4        579


I think it pretty much covers all the "new" UR discoveries!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Sat Apr 22, 2006 4:50 pm

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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques