Between Uniqueness and BUG: BUG Lite

Advanced methods and approaches for solving Sudoku puzzles

Postby Havard » Fri Feb 03, 2006 7:03 pm

Code: Select all
.32|...|.6.
 ...|6.9|...
 9..|2..|.43
 ---+---+---
 7..|.84|9..
 ..4|...|..6
 .5.|.1.|...
 ---+---+---
 .9.|8..|...
 .2.|..3|7..
 5..|...|.9.


 1     3     2     | 47    47    8     | 5     6     9
 8     4     5     | 6     3     9     | 2     17    17
 9    *67   *67    | 2     5     1     | 8     4     3
-------------------+-------------------+------------------
 7    *16   *16    | 35    8     4     | 9     235   25
 3     8     4     | 579   279   257   | 1     57    6
 2     5     9     | 37    1     6     | 34    378   478
-------------------+-------------------+------------------
#46    9     137   | 8    #2467  257   | 346   1235  1245
#46    2     18    | 1459 #469   3     | 7     158   1458
 5    *17   *1378  | 147   2467  27    | 346   9     1248



Valid eliminations are r9c3<>1 and r9c3<>7. There also is a UR(46) type 3 for eliminations r1c5<>7, r9c5<>2, and r9c5<>7.



I have really trouble understanding how this could be a type UR type 3?
As far as I can see you have three extra candidates: 2 and 7 for one cell, and 9 for the other cell. Would not the logic fail then?
With the "two extra candidates per cell" scenario I think the logic is quite clear because if you here had 2 and 7 as the extras in both cells you could go:

if one cell is 4 or 6, then the other HAS to be 2 or 7 (to avoid m.s).

hence you know there has to be either 2 or 7 in one of them, and that can be coupled with other subset-stuff, but in this case, the cell in question does not HAVE to be 2 or 7, becuase the other cell can be 9. And v.v. that cells dos not have to 9, because the other cell could be 2 or 7.

I am completly confused? Can you explain it to me?:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Fri Feb 03, 2006 11:16 pm

Havard wrote:I am completely confused? Can you explain it to me?

I was the confused one. I applied the "quantum square" concept to the union of digits '27' and '9' ... and incorrectly counted the cells for the quantum as 2 instead of 1 ... which incorrectly yielded a naked triple in cells r5c5, r7c5, and r8c5.

The eliminations being correct was a lucky accident. I intend to edit my original post.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Between Uniqueness and BUG: The Extended Uniqueness Theo

Postby Myth Jellies » Sat Feb 04, 2006 6:48 am

Moschopulus wrote:...We discussed these over on the pseudo-puzzles thread:

http://forum.enjoysudoku.com/viewtopic.php?t=2747

Ocean and Red Ed did a lot of work in classifying the small ones.


Thanks for the link. Some of these have been noted in our various uniqueness threads, but probably not all of them.

Your thread tended to look at this working backward from a final solution, which made sense considering the topic of the thread. Here we are focusing on means of hunting and confirming deadly multi-solution patterns that exist in candidate lists.

Considering the third of the 6-cell patterns listed...the BUG-Lite rule would catch the following nicely...
Code: Select all
 .   .   ab  |  ab  .  .  |  .   .   .
 .   .   bc  |  bc  .  .  |  .   .   .
 .   .   ac  |  acx .  .  |  .   .   .

...but it would trigger multiple ways on the following...
Code: Select all
 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abcx .  .  |  .   .   .

...none of which would make it obvious that the x can be placed in its cell. Can we extend the BI-value Universal Grave rule to a more generic N-value Universal Death rule where N must be greater than 1, and N can vary depending on the dimension (rows vs columns vs blocks) you are measuring. For example using row-col-blk order, the abc's in the last grid would be a deadly pattern according to the 2-3-3-UG rule.

Or can we get even more generic and consider any pattern where no digit shows up only once in a group. Thus we could safely choose the x in the following grid...
Code: Select all
 
 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   ab  | abx  .  .  |  .   .   .

Food for thought.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Sat Feb 04, 2006 7:48 am

Here is one for the most general Multivalue Universal Grave theory...
Code: Select all
*48+1 *48   5    | 7    14   2    |  3    9    6     
 14    6    2    | 9    3    14   |  5    7    8     
 9     7    3    | 8    6    5    |  4    1    2   
-----------------+----------------+----------------
 3     1    9    | 2    8    6    |  7    4    5   
 5   **28   6    | 14   7    14   |**28   3    9   
*48  **248  7    | 5    9    3    |  6  **28   1     
-----------------+----------------+----------------
 26    9    8    | 346  24   7    |  1    5    34   
 27    5    4    | 13   12   8    |  9    6    37   
 76    3    1    | 46   5    9    |**28 **28   47   

The double-starred cells form a simple uniqueness pattern which forces r6c2 = 4. The set of starred and double-starred cells all form a MUG+1 pattern forcing r1c1 = 1. Combined, these two solve the puzzle.

The most general concept for MUG was a red herring, as shown below. The real reason this worked is because all the starred cells represent two interlaced uniqueness patterns.
Last edited by Myth Jellies on Sat Feb 04, 2006 4:43 am, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Sat Feb 04, 2006 8:37 am

Bah, MUG is no good. In the following grid...
Code: Select all
 1     3     2     | 47    47    8     | 5     6     9
 8     4     5     | 6     3     9     | 2     17    17
 9     67    67    | 2     5     1     | 8     4     3
-------------------+-------------------+------------------
 7     16    16    | 35    8     4     | 9     235   25
 3     8     4     |*579  *279  *257   | 1     57    6
 2     5     9     | 37    1     6     | 34    378   478
-------------------+-------------------+------------------
*46    9    *137   | 8    *2467 *257   |*346   1235 *1245
*46    2    *18    |*1459 *469   3     | 7     158  *1458
 5     17   *1378  |*147  *2467 *27    |*346   9    *1248

...the starred cells form a MUG+0 grid, which you would think is impossible if you were going to perform uniqueness operations on it. Come to think of it, any full grid which does not contain a hidden or naked single, must be a MUG. Bit of a waste of time there, eh. Next!:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Between Uniqueness and BUG: The Extended Uniqueness Theo

Postby Moschopulus » Sat Feb 04, 2006 2:23 pm

Myth Jellies wrote:Thanks for the link. Some of these have been noted in our various uniqueness threads, but probably not all of them.

Your thread tended to look at this working backward from a final solution, which made sense considering the topic of the thread. Here we are focusing on means of hunting and confirming deadly multi-solution patterns that exist in candidate lists.


Yes, I tend to think of them as being contained in a particular grid, but they can be considered as configurations on their own, which is more what you are doing.

I guess I'm thinking that unavoidable sets are precisely the things that "cause" multiple solutions, so what you all are doing is saying
"if I put this digit here, then I'm left with an unavoidable set, so it can't go here".

Your deadly multi-solutions patterns must have an unavoidable set at the heart of them. I'm not saying that what you're doing is the same as finding unavoidable sets, but there is something in common.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Re: Between Uniqueness and BUG: The Extended Uniqueness Theo

Postby Myth Jellies » Sat Feb 04, 2006 11:31 pm

Moschopulus wrote:I guess I'm thinking that unavoidable sets are precisely the things that "cause" multiple solutions, so what you all are doing is saying
"if I put this digit here, then I'm left with an unavoidable set, so it can't go here".

Your deadly multi-solutions patterns must have an unavoidable set at the heart of them. I'm not saying that what you're doing is the same as finding unavoidable sets, but there is something in common.


You are absolutely right, and we are finding unavoidable sets.

Perhaps I am just not explaining myself very well.

Rather than trying to remember all of the many many candidate patterns that represent unavoidable sets, I am trying to come up with a few simple conditions which, if they are satisfied, mean that you have an unavoidable set a.k.a. a deadly pattern.

For example, the BUG-Lite rule will catch the following bivalue cases of eight-cell deadly patterns without forcing you to remember them...
Code: Select all
T1
----------------------
ab .  .|bc .  .|ca .  .
.  ab .|bc .  .|ca .  .
.  .  .|.  .  .|.  .  .
----------------------
ab ab .|
.  .  .|
.  .  .|
----------------------

T2
----------------------
ab .  .|ab .  .|.  .  .
.  ab .|.  .  .|ab .  .
.  .  .|ab .  .|ab .  .
----------------------
ab ab .|
.  .  .|
.  .  .|
----------------------

T3
----------------------
ab .  .|ab .  .|.  .  .
.  ab .|ab .  .|.  .  .
.  .  .|.  .  .|.  .  .
----------------------
ab .  .|.  ab .|
.  ab .|.  ab .|
.  .  .|.  .  .|
----------------------

T4
----------------------
ab .  .|ab .  .|.  .  .
.  ab .|ab .  .|.  .  .
.  .  .|.  .  .|.  .  .   
----------------------
ab .  .|.  .  .|ab .  .
.  ab .|.  .  .|ab .  .
.  .  .|.  .  .|.  .  .
----------------------

T5
----------------------
ab .  .|ab .  .|.  .  .
.  ab .|.  ab .|.  .  .
.  .  .|.  .  .|.  .  .
----------------------
ab .  .|ab .  .|
.  ab .|.  ab .|
.  .  .|.  .  .|
----------------------

T6
----------------------
ab bc . |ca .  .|.  .  .
.  .  ca|ca .  .|.  .  .
.  .  . |.  .  .|.  .  .
----------------------
ab bc ca|
.  .  . |
.  .  . |
----------------------

T7
----------------------
ab .  .|bd .  .|ad .  .
bc .  .|bc .  .|.  .  .
ca .  .|cd .  .|ad .  .
----------------------

T8
----------------------
ab cd .|ac .  .|bd .  .
ab cd .|ac .  .|bd .  .
.  .  .|.  .  .|.  .  .
----------------------

T9
----------------------
ac ad .|cd .  .|.  .  .
bc bd .|cd .  .|.  .  .
.  .  .|.  .  .|.  .  .
----------------------
ab ab .|
.  .  .|
.  .  .|
----------------------

Note that BUG-Lite won't do very well finding unavoidable sets containing tri-value cells and more.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Between Uniqueness and BUG: The Extended Uniqueness Theo

Postby Moschopulus » Sun Feb 05, 2006 2:22 am

Myth Jellies wrote:You are absolutely right, and we are finding unavoidable sets.

Perhaps I am just not explaining myself very well.

Rather than trying to remember all of the many many candidate patterns that represent unavoidable sets, I am trying to come up with a few simple conditions which, if they are satisfied, mean that you have an unavoidable set a.k.a. a deadly pattern.


I see now .... thanks!
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Myth Jellies » Tue Feb 07, 2006 11:07 am

This was a nice catch for many interesting forms of uniqueness including BUG-Lite.

If you want to get wild with uniqueness and a sashimi x-wing, you can solve this without coloring, chains, or almost locked sets.

Code: Select all
 *-----------------------------------------------------------*
 | 137   5     13    | 4     2     79    | 8     19    6     |
 | 17    4     2     | 89    78    6     | 5     19    3     |
 | 89    6     89    | 5     1     3     | 2     4     7     |
 |-------------------+-------------------+-------------------|
 | 358   7     35    | 1     45    245   | 9     6     28    |
 | 4     2     89    | 3     6     89    | 7     5     1     |
 | 589   1     6     | 89    57    257   | 4     3     28    |
 |-------------------+-------------------+-------------------|
 | 15    9     7     | 2     3     15    | 6     8     4     |
 | 6    *38    15    | 7     458  *18+45 |*13    2     9     |
 | 2    *38    4     | 6     9    *18    |*13    7     5     |
 *-----------------------------------------------------------*


38-81-13 BUG-Lite+1 grid (r89c267) kills 18 in r8c6 via uniqueness type 1. Note that considering only the starred cells, the 1's, 3's, and 8's all appear zero or exactly twice in all rows, columns, and boxes. This is the rule for a BUG-Lite deadly uniqueness pattern which must be avoided.

Code: Select all
 *---------------------------------------------------*
 | 137  5    13   | 4    2     79   | 8    19   6    |
 | 17   4    2    | 89   78    6    | 5    19   3    |
 | 89   6    89   | 5    1     3    | 2    4    7    |
 |----------------+-----------------+----------------|
 | 358  7    35   | 1   *45   *45+2 | 9    6    28   |
 | 4    2    89   | 3    6     89   | 7    5    1    |
 | 589  1    6    | 89   57    257  | 4    3    28   |
 |----------------+-----------------+----------------|
 | 15   9    7    | 2    3     15   | 6    8    4    |
 | 6    38   15   | 7   *45+8 *45   | 13   2    9    |
 | 2    38   4    | 6    9     18   | 13   7    5    |
 *---------------------------------------------------*


Another uniqueness rectangle is uncovered, note that r4c6 = 2 or r8c5 = 8 or both. Also note that 4's are confined to these four cells, thus either (r4c6 and r8c5 = 4) or (r4c5 and r8c6 = 4). Since the first pairing clashes with the uniqueness implication, it must be true that r4c5 and r8c6 = 4. This is kind of like a type 4-5 combination reduction. Now you have...
Code: Select all
 *--------------------------------------------------*
 | 137  5    13   | 4    2    79   | 8    19   6    |
 | 17   4    2    | 89   78   6    | 5    19   3    |
 | 89   6    89   | 5    1    3    | 2    4    7    |
 |----------------+----------------+----------------|
 | 358  7   *35   | 1   *4   -25-  | 9    6    28   |
 | 4    2    89   | 3    6    89   | 7    5    1    |
 | 589  1    6    | 89  #57   257  | 4    3    28   |
 |----------------+----------------+----------------|
 | 15   9    7    | 2    3    15   | 6    8    4    |
 | 6    38  *15   | 7   *58   4    | 13   2    9    |
 | 2    38   4    | 6    9    18   | 13   7    5    |
 *--------------------------------------------------*

A Sashimi X-Wing for 5's in r48c35 with fin in box 5 r6c5 kills the 5 in r4c6.
A few naked pairs and basic stuff gets the grid to...
Code: Select all
 |*37+1 5    13   | 4    2    79   | 8    19   6    |
 | 17   4    2    | 89   78   6    | 5    19   3    |
 | 89   6    89   | 5    1    3    | 2    4    7    |
 |----------------+----------------+----------------|
 | 35   7    35   | 1    4    2    | 9    6    8    |
 | 4    2    89   | 3    6    89   | 7    5    1    |
 | 89   1    6    | 89   57   57   | 4    3    2    |
 |----------------+----------------+----------------|
 | 15   9    7    | 2    3    15   | 6    8    4    |
 | 6    38   15   | 7    58   4    | 13   2    9    |
 | 2    38   4    | 6    9    18   | 13   7    5    |

This is just a BUG+1 grid where you can set r1c1 = 1 to solve the puzzle.
Last edited by Myth Jellies on Thu Feb 09, 2006 3:58 am, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Tue Feb 07, 2006 5:21 pm

Hi MJ, It appears that you are using an old version of Simple Sudoku to output your grids. The latest version output grids without curly brackets.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Thu Feb 09, 2006 7:59 am

Thanks for the heads up, Jeff.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Sun Feb 19, 2006 1:28 pm

Puzzle is messing with my head now. I missed the naked pair in row 9 below:( ...
Code: Select all
  *-----------------------------------------------------------------------------*
 | 2368    5       26      | 4       78      139     | 27      279     16      |
 | 2368    238     7       | 39      58      139     | 4       259     16      |
 | 9       1       4       | 2       57      6       | 8       57      3       |
 |-------------------------+-------------------------+-------------------------|
 |*48+2    248     3       | 1      *49      5       | 6       78     *89+7    |
 |*48      7       5       | 6      *49      2       | 1       3      *89      |
 | 1       6       9       | 8       3       7       | 5       24      24      |
 |-------------------------+-------------------------+-------------------------|
 | 27      9       8       | 5       1       4       | 3       6       27      |
 | 234567  234     1       | 37      26      38      | 9       48      458     |
 | 234567  234     26      | 379     26      389     | 27      1       458     |
 *-----------------------------------------------------------------------------*

...and found the nice loop with the BUG-Lite+2 instead.:)
Code: Select all
[r4c9] = 7 = [r7c9] = 2 = [r7c1] - 2 - [r4c1] = 2|BUG|7 = [r4c9]; => [r4c9] = 7.
(or for those who are just learning nice loops and might like to see the alternating links used)
[ 7  ] = [7 - 2] = [ 2  ] - [ 2  ] =BUG= [ 7  ]
[r4c9] = [r7c9 ] = [r7c1] - [r4c1] =BUG= [r4c9]  the hard link in and out of r4c9 (7) means r4c9 = 7.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby RW » Thu Mar 16, 2006 9:52 pm

Myth Jellies wrote:Even though this seems to work so long as I don't leave a pure diagonal pairing, it is quite possible that I have just been lucky. Have to review what makes a deadly pattern deadly, I guess.


Just posted a very long explanation on Uniqueness chains that might give you some kind of answer. Check i out here.

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

Postby ronk » Fri Apr 14, 2006 12:31 pm

This is the most complex BUG-Lite pattern I've spotted on my own. From #226 of the top1465:
Code: Select all
..14.7...5.....6.....8.....4.86...7.....2.3...........63..5...........41.2.......

 38   68    1    | 4    36   7    | 9    2    5
 5   *47    39   | 2    1    39   | 6    8   *47
 27  *47+69 269  | 8    69   5    |*47   1    3
-----------------+----------------+---------------
 4    5     8    | 6    39   39   | 1    7    2
 79   1     69   | 57   2   *48   | 3    56  *48
 23   67    23   | 57  *48   1    |*48   56   9
-----------------+----------------+---------------
 6    3     4    | 1    5    2    |*78   9   *78
 89   89    5    | 3    7    6    | 2    4    1
 1    2     7    | 9   *48  *48   | 5    3    6

To avoid a deadly non-uniqueness pattern in the cells marked with an asterisk, r3c2<>4 and r3c2<>7, which "breaks" the puzzle. However, most would likely find using the BUG principle on cells r3c23 a bit easier.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Fri Apr 14, 2006 5:11 pm

Nice one, ronk.

The BUG+2 method reqires a 6-cell xy-chain and a naked pair to show that r2c2 = 4 and crack the puzzle. Your BUG-Lite results in a hidden single for that cell--much easier to resolve.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

PreviousNext

Return to Advanced solving techniques