Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Thu Apr 27, 2006 12:59 pm

ravel wrote:No doubt that the "theory" is correct, Vidar's AUS is basically the same, but the pattern is very rare.

Note that in Vidar's example, the "freely invented" UR digits are missing because of their placement within the UR .. not placement elsewhere in their units.

Perhaps that's another requirement ... besides the "not a given", that is.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Thu Apr 27, 2006 1:10 pm

Posts crossed:) Now i dont know, if it is clarified or not.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Mike Barker » Thu Apr 27, 2006 1:33 pm

I think the issue may focus on why the "a" is missing. In this case, it is not a result of the UR so there must be some external influence. I'm not sure what would cause the "a" to be eliminated from "bY", but assuming there is then that same influence would prevent the deadly pattern from forming. If not, then the "bY" could be "a" which means the PM are incorrect! In the case the elimination is a result of the UR then further eliminations may be possible.
Code: Select all
ab      abX
         |
        b|
         |
bY      abZ
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby RW » Thu Apr 27, 2006 2:09 pm

Mike Barker wrote:I think the issue may focus on why the "a" is missing.


I just started a new thread on possible deadly patterns with candidates removed here. This thread was getting so messy with too many issues discussed that I thought this discussion should be continued elsewhere... Anybody else feel the same?

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

Postby ronk » Thu Apr 27, 2006 7:28 pm

#1144 is the only example of the UR+3X/2SL I found in the top1465. It follows a naked quad, multi-coloring (2x), and a UR Type 1.
Code: Select all
63......4..5......74..3..6..2.4.5........19......6...7..4.2..9.25.9.8......5..1..

 6     3    -1289  | 1278   5    -279   | 278   178   4
 189   189   5     | 12678 -4789 -24679 | 2378  1378  1389
 7     4    -1289  |-128    3    *29    |-258   6     1589
-------------------+--------------------+------------------
 1389  2     13678 | 4      789   5     | 368   138   1368
 4     678   3678  | 2378   78    1     | 9     5     2368
 5     189   1389  | 238    6    -239   | 4     1238  7
-------------------+--------------------+------------------
 138   1678  4     | 367    2     367   | 35678 9     3568
 2     5     367   | 9      1     8     | 367   4     36
 389   6789  36789 | 5      47    3467  | 1     2378  2368

 UR(29)+3X/2SL: r2c56<>9, r6c6<>9, r3c47<>2, r3c3<>9, r1c6<>2, r1c3<>18

Exclusions made manually, so hopefully there are no mistakes.:)

BTW what's the 'X' for in UR+3X?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Thu Apr 27, 2006 7:47 pm

The "X" starts with the UR+2X where the X refers to multiple candidates (x is for a single candidate) kind of in keeping with the nomenclature we've been using. in UR+2X/1SL and UR+3X/2SL the X implies the strong links are between the multi candidate cells. I'm thinking that a few words might be better than the letters, but for now there is actually some kind of logic. Just like "C" is "connected links" and "E" is "equal labels", "U" is "unequal labels", etc
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Thu Apr 27, 2006 8:19 pm

Mike Barker wrote:The "X" starts with the UR+2X where the X refers to multiple candidates (x is for a single candidate) kind of in keeping with the nomenclature we've been using.

In keeping with BUG and BUG-Lite nomenclature (per Myth Jellies suggestion), I think you mean the 'n' in 'UR+n' is the number of UR cells with poly-valued candidates. (The "poly" meaning three or more candidates ... as opposed to "multi" for two or more candidates ... in keeping with the BUG thread.)

Mike Barker wrote:... for now there is actually some kind of logic. Just like "C" is "connected links" and "E" is "equal labels", "U" is "unequal labels", etc

Hmm. Better re-read your post as I missed that too.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Mon May 01, 2006 1:02 am

I renamed UR+3C/2SL to UR+3N/2SL and added UR+3C/2SL which is similar to UR+4C/3SL (which is why I made the first change). I'm still not sure the list is complete so any inputs would be appreciated.

While I was gone this weekend I was thinking about how to apply strong links and nice loops to BUGs and when I got back noticed that Ron had already expressed concern about the sanity of anyone attempting such a task. I may be insane, but I think we should check the bath water more carefully. Several techniques should transfer over fairly simply:
    UR+1 -> BUG+1
    UR+2(x,d) and UR+3x -> BUG+x
    UR+2X -> BUG+X
    UR+2X/1SL -> BUG+2X/1SL
    UR+3X/2SL -> BUG+3X/2SL
    UR+3C/2SL -> BUG+3C/2SL
    UR+4X/3SL -> BUG+4X/3SL
    UR+4C/3SL -> BUG+4C/3SL
    BUG+4U/3SL: three unique labels (only possible with a BUG):
    Code: Select all
    abX-----abZ
         a   |
            b|
         c   |
    cdY-----bcW

    I've started to implement the first four (which correspond to historical Types 1-4). Other techniques which are not on the list and depend on bivalue cells, all of the X-wing/nice loop eliminations, and all of the new possibilities because of the added degrees of freedom may be more of a challenge. So anyone out there feeling slightly crazy and up to the task or willing to sign my commitment papers for making the suggestion?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

An elementary introduction

Postby keith » Sun May 07, 2006 4:30 am

The Daily Sudoku puzzles seem to be getting "harder", by including X-wings and Unique Rectangles. I wrote an elementary Introduction to UR's:

http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?p=3465#p3465

I put this in what I thought is a logical order of increasing complexity; I ignored the UR Type classifications, and tried to stay away from the jargon of strong links, conjugate pairs, etc. I welcome any and all comments.

Keith

Rereading this thread, I see that Mike Barker has edited one of his posts (buried on page 2) to link to my Introduction, and has included the Introduction in his solving "sticky". Thank you, Mike!
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby Mike Barker » Mon May 08, 2006 12:24 pm

I may be crazy, but I've implemented all of the UR techniques and the subset of BUG-lite techniques as delineated above. I ran my solver against the Top 1465, but some modification has significantly slowed it down and only the first 1096 puzzles were completed before my son accidently killed the process - something about school work. Even so, the results are pretty significant. The number in parentheses shows the number of times the technique was used for successfully completed puzzles. As a comparison X-wings were used 105 times; XY-wings 184 times; and WXYZ-wings, 216 times. Half the BUG-lite eliminations occur using strong links. More may be possible with implementation of other strong link techniques and nice loops. With UR's approximately 5 times more eliminations occur using strong links and nice loops than if they are not used. Interestingly no diagonal UR's were detected. I've checked my code and it appears to be working. I'd be interested in testing puzzles with a UR+2d elimination.

I don't know how many puzzles were solved because of these changes, my guess is very few, but given that UR's are not too difficult to identify, the results suggest UR's plus strong links are a pretty powerful technique. Note that I implemented the UR's and BUG-lites after all techniques except for ALS rules (except for xz-rule if it uses a bivalue cell in which case it came earlier) and nice loops. Of the 1096 puzzles only 707 were solved. "buglets" refers to the number of units used to construct the BUG-lite. Also my BUG-lite constructor is pretty limited (this is one area I know I have throughput problems) so it wouldn't surprise me if others find more BUG-lite eliminations.
    UR+1 (47) - Type 1
    UR+2x (20) - Type 2/2b
    UR+2X (20) - Type 3/3b
    UR+2(X,D,B)/1SL (273) - UR+2X/1SL is Type 4
    UR+2d/UR+3x (0) - Type 5
    UR+2D,UR+3(x,X)/1SL (22)
    UR+3(X,C,N,U,E)/2SL (199)
    UR+4(X,C)/3SL,UR+4(x,X)/2SL (114)
    Bug-Lite with 2 buglets - BUG+1,+x,+X (5)
    Bug-Lite with 3 buglets - BUG+1,+x,+X (6)
    Bug-Lite with 2 buglets - BUG+2X/1SL,+3(X,C)/2SL,+4(X,C,U)/3SL (7)
    Bug-Lite with 3 buglets - BUG+2X/1SL,+3(X,C)/2SL,+4(X,C,U)/3SL (4)

Here are the BUG-lite eliminations using strong links. The UR eliminations are way to numerous to list.
Code: Select all
Strong Links with 2 buglets

Puzzle 901
BUG+4C/3SL (2 buglets): r349c23 => r3c2<>4
r5c2=2=r3c2=2=r3c3=4=r9c3
+-----------------+-----------------+----------------+
|     6  379   79 |   137   137   5 |    8     4   2 |
|     5    8    1 |    37     4   2 |   37     9   6 |
|   347 -234 #247 |     8     6   9 |  357  1357  13 |
+-----------------+-----------------+----------------+
|   137 #237  *27 |     4    18  68 |    9   167   5 |
|  1479  479    5 |   126    19   3 |  247   267   8 |
|   149    6    8 |  1259   159   7 |  234    12  13 |
+-----------------+-----------------+----------------+
|    79    5    3 |    79     2   1 |    6     8   4 |
|     8    1   69 |  3569   359   4 |  235   235   7 |
|     2  *47 #467 |  3567  3578  68 |    1    35   9 |
+-----------------+-----------------+----------------+

Puzzle 610
BUG+4C/3SL (2 buglets): r368c45 => r8c4<>1
r8c5=7=r8c4=7=r3c4=2=r3c5
+-------------+---------------------+----------------------+
|  3    7   5 |     46      9   468 |      2     1     468 |
|  2   49  68 |     45    467     1 |      3  4689  456789 |
|  1   49  68 | #23457 #23467  3468 |  45689  4689  456789 |
+-------------+---------------------+----------------------+
|  4    1   9 |     36      8     5 |      7     2      36 |
|  5    8   2 |   3469    346     7 |     69  3469       1 |
|  7    6   3 |    *12    *12    49 |   4589   489    4589 |
+-------------+---------------------+----------------------+
|  8   35   7 |     19  13456     2 |   1469    36    3469 |
|  9   23   4 |  -1367  #1367    36 |    168     5    2368 |
|  6  235   1 |      8     45   349 |     49     7     249 |
+-------------+---------------------+----------------------+

Puzzle 581
BUG+4C/3SL (2 buglets): r148c46 => r1c6<>5
r8c4=5=r1c4=2=r1c6=2=r4c6
+-------------------+-----------------+----------------+
|     1  35678    4 | #258   68  -256 |    9   38   57 |
|   368    356    2 |    7    9  1568 |   14   38  145 |
|    89     78  589 |    3    4    18 |    6    2  157 |
+-------------------+-----------------+----------------+
|   248      1   38 |  *28    5 #2348 |    7    9    6 |
|  2468    268    7 |    9  168    46 |   25   15    3 |
|     5      9   36 |   12    7    36 |  124   14    8 |
+-------------------+-----------------+----------------+
|  2389   2358    1 |    4  238     7 |   58    6   29 |
|   369      4   69 | #158   23   *58 |   18    7   29 |
|     7    258   58 |    6  128     9 |    3  145   14 |
+-------------------+-----------------+----------------+

Puzzle 498
BUG+3C/2SL (2 buglets): r79c149 => r7c9<>6
r7c4=1=r7c9=1=r9c9
+-------------+---------------------+---------------------+
|   5   4   7 |   1268    168     9 |   1268    268     3 |
|  12  23  13 |      5    468     7 |      9    468    46 |
|   9   6   8 |      3     14   124 |   1245    245     7 |
+-------------+---------------------+---------------------+
|   7   9  16 |    168      3  1458 |  24568  24568  2456 |
|  14   8   5 |     67      2   146 |    467      3     9 |
|  24  23  36 |      9  45678  4568 |   5678      1   456 |
+-------------+---------------------+---------------------+
| *68   5   4 | #12678     79     3 |     26   2679  -126 |
|   3   1   9 |      4    567   256 |    256   2567     8 |
| *68   7   2 |    *18  15689  1568 |      3   4569 #1456 |
+-------------+---------------------+---------------------+

Puzzle 457
BUG+3C/2SL (2 buglets): r78c149 => r7c4<>6
r7c1=5=r7c4=5=r8c4
+-----------------+--------------------+----------------+
|   38    56    1 |  2346  24678  3478 |  479  356   29 |
|    4    56   27 |    36      1     9 |   57    8   23 |
|   38   279  279 |  2346  34678     5 |   47   36    1 |
+-----------------+--------------------+----------------+
|    6     3  249 |     8    257   147 |   59   15   49 |
|    1   249    5 |  2349   2349    34 |    6    7    8 |
|   79   479    8 |    19     45     6 |    2  135  349 |
+-----------------+--------------------+----------------+
| #579  1479  479 | -1569    689    18 |    3    2  *67 |
|  *57     8    3 |  #456     46     2 |    1    9  *67 |
|    2    19    6 |     7     39    13 |    8    4    5 |
+-----------------+--------------------+----------------+

Puzzle 241
BUG+4C/3SL (2 buglets): r148c79 => r8c7<>7
r9c9=3=r9c7=3=r4c7=9=r4c9
+--------------+-------------+-----------------+
|   1   2    3 |   4   5   6 |  *79    8   *79 |
|  46  58   46 |   7   9  28 |   15   13   123 |
|   7  58    9 |  28   3   1 |   45  456    26 |
+--------------+-------------+-----------------+
|   2   4   56 |  35   8   7 | #139  136 #1369 |
|   3   1    8 |  26  26   9 |   47   47     5 |
|  56   9    7 |  35   1   4 |    8    2    36 |
+--------------+-------------+-----------------+
|  45   7  145 |  16  46   3 |    2    9     8 |
|   8   6   14 |   9  24  25 | -357  157  #137 |
|   9   3    2 |  18   7  58 |    6   15     4 |
+--------------+-------------+-----------------+

Puzzle 240
BUG+4C/3SL (2 buglets): r79c168 => r9c1<>7
r7c6=5=r9c6=4=r9c1=4=r7c1
+----------------+----------------+------------+
|    89  18  189 |    5   4     6 |  3   2   7 |
|    27  27    4 |    3   1     8 |  5   9   6 |
|     5   3    6 |    7   9     2 |  1   8   4 |
+----------------+----------------+------------+
|     1  48   23 |   48  23     9 |  7   6   5 |
|   789   5   79 |   18   6    17 |  4   3   2 |
|     6  47   23 |   24   5   347 |  8   1   9 |
+----------------+----------------+------------+
| #3478   6  178 |  124  23 #1345 |  9 *57  13 |
|    23  12    5 |    9   7    13 |  6   4   8 |
|  -347   9   17 |    6   8 #1345 |  2 *57  13 |
+----------------+----------------+------------+

Strong links with three buglets

Puzzle 837
BUG+2X/1SL (3 buglets): r25c4|r35c6|r23c7 => r3c6<>4,r3c7<>4
+-------------------+-------------------+--------------------+
|   57   2457     1 |    9   578   4678 |  2456     3   2568 |
|  569      3    69 |  *14    58      2 |   *14   589      7 |
|    8  24579   279 |   67   357 -134567|-12456   259   2569 |
+-------------------+-------------------+--------------------+
|    1    789     3 |  278     6    578 |   257     4   2589 |
|    2   6789  6789 |  *14  5789    *14 |  3567  5789  35689 |
|    4   6789     5 |    3  2789     78 |   267  2789      1 |
+-------------------+-------------------+--------------------+
|  356      1   268 |  268     4      9 |  2357   257    235 |
|  359   2579     4 |   27     1     37 |     8     6    235 |
|  367   2678  2678 |    5  2378   3678 |     9     1      4 |
+-------------------+-------------------+--------------------+

Puzzle 714
BUG+2X/1SL (3 buglets): r5c45|r89c458 => r8c8<>7,r9c8<>7
+--------------+-------------+---------------+
|   1   29   7 |  29   4   3 |  5     6    8 |
|   3    6  59 |  59   1   8 |  7     4    2 |
|  48   48  25 |  25   7   6 |  1     9    3 |
+--------------+-------------+---------------+
|  57    3   6 |   4   9  12 |  8  1257  157 |
|  58   18  12 | *36 *36   7 |  4   125    9 |
|  79  129   4 |   8   5  12 |  3    27    6 |
+--------------+-------------+---------------+
|   6   47   8 |   1   2  45 |  9     3   57 |
|   2  179  19 | *37 *38  59 |  6  -578    4 |
|  49    5   3 | *67 *68  49 |  2  -178   17 |
+--------------+-------------+---------------+

Puzzle 698
BUG+3C/2SL (3 buglets): r6c789|r78c6|r8c7|r7c89 => r7c9<>1
+--------------------+-----------------+---------------+
|     1      8   469 |     3  29     5 |   7  269  246 |
|     3    679  4679 |   246   1   469 |   5    8  246 |
|   569      2  4569 |    46   8     7 |   1   69    3 |
+--------------------+-----------------+---------------+
|   679      3   679 |     8   4  1269 |  26    5   17 |
|   567    156     8 |    57   3    12 |  26    4    9 |
|     4  15679     2 |  1567  59   169 | *38  *13 #178 |
+--------------------+-----------------+---------------+
|  2579    579  3579 |   145   6  #348 |  49  *13 -128 |
|    26      4     1 |     9   7   *38 | *38   26    5 |
|     8    569  3569 |  1245  25   134 |  49    7   16 |
+--------------------+-----------------+---------------+

Puzzle 694
BUG+3C/2SL (3 buglets): r1c46|r8c248|r9c268 => r9c6<>1
+--------------+-------------------+---------------+
|   5   9    7 |    *18     3  *18 |    6    4   2 |
|  38   2    1 |      4     9    6 |    5   37  78 |
|   6   4   38 |    257   257   25 |   39    1  89 |
+--------------+-------------------+---------------+
|   1   6   49 |      3     8   45 |   79    2  57 |
|  28   5  289 |   1267  1267   12 |    4   69   3 |
|   7   3   24 |    256   245    9 |    8   56   1 |
+--------------+-------------------+---------------+
|   4   8  236 |    126   126    7 |   13   59  59 |
|   9 *17   26 | #12568  1256    3 |  127  *78   4 |
|  23 *17    5 |      9   124 -1248|  127 #378   6 |
+--------------+-------------------+---------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Tue May 09, 2006 12:07 am

Hi Mike!

Very interesting combining strong links and bugs. Can you make a generalised example of how you would apply strong links to a bug of n candidates?

I made a quick search through the top 1465 with BUG's after Locked sets (and UR), but before strong links /fishes. These were my results:

BUG+1: 10

BUG-Lite+1 (size 6): 18
BUG-Lite+1 (size 7): 1
BUG-Lite+1 (size 8): 4
BUG-Lite+1 (size 9): 1
BUG-Lite+1 (size 12): 15
BUG-Lite+1 (size 16): 1

I have not yet implemented a UR type 2 and 3-like search for BUG's yet, and not at all strong links.

(also the WAY most common UR is this one:
Code: Select all
     
ab     ab
|
|a
|
abX     abY
with a whopping 593 occurences, and this one:
Code: Select all
ab-----abX
     a   

     a   
abY-----abZ               
with 247.

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Tue May 09, 2006 12:28 am

Havard wrote:BUG-Lite+1 (size 6): 18
BUG-Lite+1 (size 7): 1
BUG-Lite+1 (size 8): 4
BUG-Lite+1 (size 9): 1
BUG-Lite+1 (size 12): 15
BUG-Lite+1 (size 16): 1

What is "size?" If it's the number of cells in the BUG-Lite pattern, how can that ever be an odd number?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Tue May 09, 2006 1:35 am

A generalized statement is still in work. As far as I see it the applicability is independent of size. I've basically broken up the UR eliminations as they apply to BUG's (really BUGS and BUG-lites, but I don't think the distinction is important) as follows:
1) No strong link eliminations (BUG+1, BUG+x, BUG+X) are directly applicable (eg BUG+x -> "x" can be eliminated from all non-BUG cells common to all of the BUG cells which contain "x". Its possible for 2, 3 or more BUG cells to contain the "x")
2) Strong links between only non-bivalued BUG cells (excluding the nice loop elimination portions). These are the strong link reductions I implemented and the UR eliminations are directly applicable to BUGs (eg BUG+2X/1SL - the strong link is between the two non-bivalued cells and it is easy to show that the eliminated values will always lead to a non-unique solution independent of what the BUG looks like).
3) [edit] extensions of UR techniques to larger BUG grids (eg a BUG+5X/4SL and all of its possible permutations on labels)

Things get more complicated at this point. What I haven't had a chance to show is when nice loop eliminations are possible or when strong link eliminations are possible when the strong link includes a bivalued cell (eg a BUG+2B/1SL). General rules in these cases may be more difficult to obtain. I hope we can all work on this. I first wanted to show that applying the new UR reductions to BUGs makes sense which IMO I've done. Now its time to roll up our sleeves.

[edit] In these cases it appears that what is needed is to determine XY chains between the strong links/non-bivalued cells. The number of elements in the chain will determine the elimination. (eg UR+2B/1SL and UR+2D/1SL become one type. If the length of the chain from the bivalued cell in the strong link to the non-bivalued cell which is not part of the strong link is even then a "2D" elimination occurs; if odd, then a "2B". Not nearly as simple as UR's.
Last edited by Mike Barker on Tue May 09, 2006 8:31 am, edited 1 time in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby RW » Tue May 09, 2006 7:50 am

ronk wrote:What is "size?" If it's the number of cells in the BUG-Lite pattern, how can that ever be an odd number?


It is indeed possible to construct a deadly pattern of 7 cells (or other odd amounts),

Code: Select all
.  .  ab+d |ab . .
.  .  .    |.  . .
bc .  abc  |ab . .
------------------
bc .  bc+d |
.  .  .    |
.  .  .    |

=>Eliminate d from all other cells in column 3

but these would have at least one trivalue cell. If Havard found one with only bivalue cells, I'd be very interested to see it. It could be possible, if we could somehow make the reduction r3c3<>b in the pattern above there would be a very correct BUG-lite+2 with 7 cells, all numbers appear twice in every unit.

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

Postby ronk » Tue May 09, 2006 9:55 am

RW wrote:It is indeed possible to construct a deadly pattern of 7 cells (or other odd amounts) (...) but these would have at least one trivalue cell.

Yes, most of us are aware of the Forming MUGs from BUG-Lite composites thread.

If Havard found one with only bivalue cells, I'd be very interested to see it.
Me too.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques