The New Sudoku Players' Forum

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

by **ravel** » Thu Apr 27, 2006 1:10 pm

Posts crossed

Now i dont know, if it is clarified or not.

by **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

by 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

by **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?

by **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

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

by **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:

Code: Select all: abX-----abZ a | b| c | cdY-----bcW

by **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!

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

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

by **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

by **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?

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

by 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

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

The New Sudoku Players' Forum

Uniqueness Type 6 - UR meets X-Wing

An elementary introduction