Between Uniqueness and BUG: BUG Lite

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Fri Apr 14, 2006 5:55 pm

Myth Jellies wrote:Nice one, ronk.

The flowers are appreciated.:D

Myth Jellies wrote:The BUG+2 method reqires a 6-cell xy-chain and a naked pair to show that r2c2 = 4 and crack the puzzle.

It's a lot easier than that.
Code: Select all
 38   68    1    | 4    36   7    | 9    2    5
 5    47    39   | 2    1    39   | 6    8    47
 27   49+67 26+9 | 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

By inspection, r3c2<>9 which cracks the puzzle. Did you perhaps forget to set the different 'extra candidates' for r3c2?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sat Apr 15, 2006 12:21 am

Nah, I just missed the fact that either choice knocked out the 9. Too many distractions in my life:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Wed Apr 19, 2006 3:23 am

BUG-Lite and RodHagglund's Guardians

Consider the following BUG-Lite grid (an RW example)

000070500000001060040560310012000600000000103009000420081040730050700000006038000
Code: Select all
 
 1    6   38  |#3489    7    #349  | 5    489 2
 35  *29  357 | 34     *29+8  1    |#89   6   47
*29   4   78  | 5       6    *29   | 3    1   78
--------------+--------------------+--------------
 458  1   2   | 348     58    34   | 6    7   9
 4568 7   45  |*29+468 #2589 *29+4 | 1    58  3
 568  3   9   | 68      1     7    | 4    2   58
--------------+--------------------+--------------
*29   8   1   |*29      4     5    | 7    3   6
 34   5   34  | 7      *29    6    |*29+8 89  1
 7   *29  6   | 1       3     8    |*29   45  45


According to the BUG-Lite+N principle, we know at least one of the extra candidates in r2c5, r5c4, r5c6, and r8c7 must be true. But finding a common exclusion for six extra candidates is not an easy task.

However, as a corollary to the BUG-Lite+N principle, we also know at least one of the BUG candidates must be excludible from the cells with extra candidates. We get no help from the 2s, because every row, column, and box contains either 0 or 2 candidates. But with a placement of digit 9 in either r1c4, r1c6, r2c7, or r5c3, the deadly pattern is avoided ... and r2c5 "sees" all four of those cells. Therefore, r2c5<>9 is a valid exclusion.

Those familiar with RodHagglund's Broken Wing may see the four cells (marked with '#') as "guardians", any one of which being true prevents the deadly BUG-Lite pattern.

[edit: While I'm sure the theory is sound, the example stinks ... because I missed the 9 in r8c8.:( ]

P.S. Why the heck aren't we getting line-wrap on this page?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Wed Apr 19, 2006 6:05 pm

ronk wrote:the four cells (marked with '#') as "guardians", any one of which being true prevents the deadly BUG-Lite pattern.


I suppose you can look at it that way too. But notice that if r5c5=9 then r2c7 is 9 as well (r5c5=9 => r8c5=2 => r2c5=8 => r2c7=9), that means that if r2c7<>9 => r5c5<>9 and we only need to consider this grid:

Code: Select all
 1    6   38  |#3489    7    #349  | 5     489  2
 35  *29  357 | 34     *29+8  1    |#89    6    47
*29   4   78  | 5       6    *29   | 3     1    78
--------------+--------------------+---------------
 458  1   2   | 348     58    34   | 6     7    9
 4568 7   45  |*29+468  2589 *29+4 | 1     58   3
 568  3   9   | 68      1     7    | 4     2    58
--------------+--------------------+---------------
*29   8   1   |*29      4     5    | 7     3    6
 34   5   34  | 7      *29    6    |*29+8 #89   1
 7   *29  6   | 1       3     8    |*29    45   45


r1c8 sees all the marked cells => r1c8<>9

I still think it saves us a lot of time to make the same reduction by looking at the five already solved cells of 2 and 9.

ronk wrote:This is the most complex BUG-Lite pattern I've spotted on my own. From #226 of the top1465:


I found this one in #83 of the top1465:

Code: Select all
7.....48....6.1..........2....3..6.52...8..............63.....1.5.1.........4.7..

 *--------------------------------------------------------------------*
 | 7      12     12     | 9     *35    *35     | 4      8      6      |
 | 3      48     48     | 6      2      1      | 59     59     7      |
 |*56     9     *56     | 8      7      4      | 1      2      3      |
 |----------------------+----------------------+----------------------|
 | 89     478    489    | 3      1      2      | 6      47     5      |
 | 2      1347  *56     | 47     8     *56     | 39     13479  49     |
 |*56     1347   14     | 47    *56     9      | 28     1347   28     |
 |----------------------+----------------------+----------------------|
 | 48     6      3      | 2      9      7      | 58     45     1      |
 | 49     5      7      | 1     *36     8      | 23    -3469   249    |
 | 1      28     289    | 5      4     *36     | 7     *36     89     |
 *--------------------------------------------------------------------*


Seems my BUG-lite is as long as yours Ron:) Anybody seen a bigger pattern?

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

Postby ronk » Wed Apr 19, 2006 6:54 pm

RW wrote:But notice that if r5c5=9 then r2c7 is 9 as well (r5c5=9 => r8c5=2 => r2c5=8 => r2c7=9), that means that if r2c7<>9 => r5c5<>9 and we only need to consider (...)
You're a sly one, RW.:D

RW wrote:I still think it saves us a lot of time to make the same reduction by looking at the five already solved cells of 2 and 9.
Agreed.

RW wrote:Seems my BUG-lite is as long as yours Ron:) Anybody seen a bigger pattern?
Nice one, RW. I can't imagine a "pairs BUG-Lite" any bigger than this ...
Code: Select all
 .     .     .     | .     ab    ab    | .     .     .
 .     .     .     | .     .     .     | .     bc    bc
 bc    .     bc    | .     .     .     | .     .     .
-------------------+-------------------+-----------------
 .     .     .     | .     .     .     | .     .     .
 .     .     bc    | .     .     bc    | .     .     .
 bc    .     .     | .     bc    .     | .     .     .
-------------------+-------------------+-----------------
 .     .     .     | .     .     .     | .     .     .
 .     ab    .     | .     ac    .     | .     bc    .
 .     ab    .     | .     .     ac    | .     .     bc

... and someday I think one will be found.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Wed Apr 19, 2006 7:07 pm

ronk wrote:I can't imagine a "pairs BUG-Lite" any bigger than this ...


Well, I can easily imagine this:

Code: Select all
 .     .     ed    | .     ab    ab    | ed    .     .
 .     .     .     | ed    .     .     | ed    .     . 
 ed    .     .     | ed    .     .     | .     ac    ac
-------------------+-------------------+-----------------
 .     .     .     | .     .     .     | .     af    af
 .     .     ec    | .     .     bc    | .     be    .
 ec    .     .     | .     bc    .     | .     be    .
-------------------+-------------------+-----------------
 cd    .     cd    | .     .     .     | .     .     .
 .     af    .     | .     ac    .     | .     cf    .
 .     af    .     | .     .     ac    | .     .     cf


Would be thrilled to find one of these some day!

[Edit: my imagination left no room for c in box 2, so I changed my vision a bit]


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

Postby ronk » Wed Apr 19, 2006 9:37 pm

RW wrote:
ronk wrote:I can't imagine a "pairs BUG-Lite" any bigger than this ...


Well, I can easily imagine this: (...)

LOL! I haven't figured out how to code complex 3-digit BUG-Lite patterns yet, so I'm sure not going to be looking for any 6-digit ones.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Thu Apr 20, 2006 12:26 am

My BUG-Lite is bigger than your BUG-Lite dept.:)

Recently in this thread, I noticed this BUG-Lite...

Myth Jellies wrote:Just for grins and giggles, there is a big old BUG-Lite+3 grid here
Code: Select all
 *-----------------------------------------------------------*
 |*12    3     9     | 57    6     57    | 4    *18   *28    |
 |*15    8    *56    | 2     9     4     | 3    *16    7     |
 | 4    *26    7     | 8     1     3     | 5     9    *26    |
 |-------------------+-------------------+-------------------|
 | 8    *45   *45    | 3     2     6     | 9     7     1     |
 |*29   *29    3     | 15    7     15    |*68   *68    4     |
 | 6     7     1     | 9     4     8     | 2     5     3     |
 |-------------------+-------------------+-------------------|
 | 3    *46+9 *46    | 467   8     79    | 1     2     5     |
 |*79    14    8     | 14    5     2     |*67    3    *69    |
 |*57+9 *59+16 2     | 16    3     19    |*78    4    *89    |
 *-----------------------------------------------------------*

To avoid the BUG-lite, it is pretty easy to show that either r9c1 or r9c6 equals 9, therefore you can remove 9 as a candidate from every other cell in row 9.


23 cells & 8 digits. You might be able to find bigger BUG-Lites inside of BUG grids. Only 3 cells short of RW's big thrill:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Thu Apr 20, 2006 12:47 am

Myth Jellies wrote:Just for grins and giggles, there is a big old BUG-Lite+3 grid here ...
23 cells & 8 digits. You might be able to find bigger BUG-Lites inside of BUG grids. Only 3 cells short of RW's big thrill:)

Nice one, MJ.

I've been using the 'N' of BUG+N and BUG-Lite+N to be the number of extra candidates and not the number of cells with extra candidates. Is your "+3" a typo? Or have I gotten lost somewhere?

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

Postby Myth Jellies » Thu Apr 20, 2006 2:43 am

ronk wrote:I've been using the 'N' of BUG+N and BUG-Lite+N to be the number of extra candidates and not the number of cells with extra candidates. Is your "+3" a typo? Or have I gotten lost somewhere?


It wasn't a typo; but, to be honest, I didn't know the rule. Without looking it up, I am pretty sure you are right since Jeff had some funny rule about reductions to a BUG+1 grid always being valid. On the other hand, I think the number of cells with extra candidates is a better indication of how complex it will be to "use" the BUG information. For example, a BUG with 2 extra candidates in only one cell is always immediately useful with a type 1 uniqueness reduction, whereas a BUG with an extra candidate in two different cells might require some advanced tactics to reduce.

Now that I know, though; I have no problem with counting candidates.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Thu Apr 20, 2006 3:05 am

Myth Jellies wrote:
ronk wrote:I've been using the 'N' of BUG+N and BUG-Lite+N to be the number of extra candidates and not the number of cells with extra candidates. Is your "+3" a typo? Or have I gotten lost somewhere?


It wasn't a typo; but, to be honest, I didn't know the rule. Without looking it up, I am pretty sure you are right since Jeff had some funny rule about reductions to a BUG+1 grid always being valid.
.....................
Now that I know, though; I have no problem with counting candidates.

Seems that we're both guessing. On the BUG thread ...
Jeff wrote:A BUG+n is a BUG that has exactly n number of poly-valued cells. A BUG+1 is a BUG that has exactly one poly-valued cell left.

But my guess was the incorrect one.:(
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Sat May 06, 2006 2:51 pm

Hi, I have a question about BUG-lite.

I tried to construct a BUG-lite grid on this puzzle, and I know it is not right, but I can't seem to put my finger on what it is that is wrong about it:
Code: Select all
7     3     26*   | 26*   4     9     | 1     8     5
15*   9     16*   | 8     7     56+2* | 3     4     26
28*   58*   4     | 3     1     56*   | 7     26*   9
------------------+-------------------+------------------
28*   18*   12*   | 7     9     4     | 6     5     3
9     6     7     | 5     2     3     | 8     1     4
3     4     5     | 1     6     8     | 2     9     7
------------------+-------------------+------------------
4     7     3     | 26*   5     1     | 9     26*   8
15*   15*   8     | 9     3     26    | 4     7     26
6     2     9     | 4     8     7     | 5     3     1


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


thanks!

Havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby ravel » Sat May 06, 2006 5:03 pm

What is wrong with it? r2c6 has to be 6 (2 more 6's in r2 and c6)
If it is 2, you would get two 2's in column 3, if it is 5, two 2's in row 1 (or other contradictions).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Havard » Sat May 06, 2006 9:06 pm

Sorry, I should have been more specific. I know that the BUG produces a wrong result, but I can't see what mistake I have made in construction the BUG grid. Can you see what BUG-lite construction rule I have broken that have lead to this wrong result?

Havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby ronk » Sat May 06, 2006 9:44 pm

Havard wrote:I tried to construct a BUG-lite grid on this puzzle (...)
Code: Select all
7     3     26*   | 26*   4     9     | 1     8     5
15*   9     16*   | 8     7     56+2* | 3     4     26
28*   58*   4     | 3     1     56*   | 7     26*   9
------------------+-------------------+------------------
28*   18*   12*   | 7     9     4     | 6     5     3
9     6     7     | 5     2     3     | 8     1     4
3     4     5     | 1     6     8     | 2     9     7
------------------+-------------------+------------------
4     7     3     | 26*   5     1     | 9     26*   8
15*   15*   8     | 9     3     26    | 4     7     26
6     2     9     | 4     8     7     | 5     3     1

The fundamental rule for both BUG and BUG-Lite grids is the same, the deadly pattern has each candidate appearing exactly twice in each row, col, and box. While the BUG involves the entire grid, the BUG-Lite involves only a portion.

I see no possibility of a BUG-Lite, only this BUG as ravel stated.
Code: Select all
7     3     26*   | 26*   4     9     | 1     8     5
15*   9     16*   | 8     7     25+6* | 3     4     26
28*   58*   4     | 3     1     56*   | 7     26*   9
------------------+-------------------+------------------
28*   18*   12*   | 7     9     4     | 6     5     3
9     6     7     | 5     2     3     | 8     1     4
3     4     5     | 1     6     8     | 2     9     7
------------------+-------------------+------------------
4     7     3     | 26*   5     1     | 9     26*   8
15*   15*   8     | 9     3     26    | 4     7     26
6     2     9     | 4     8     7     | 5     3     1
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques