## The BUG (Bivalue Universal Grave) principle

Advanced methods and approaches for solving Sudoku puzzles
aeb wrote:......I cannot interpret your Corollary 4 - what does it say?

Hi Aeb, here is Corollary 4:
Any placement of a candidate which forces a grid into a BUG+1 is a valid move. (example)

We know that a BUG+1 grid has a unique solution in which the one only non-BUG candidate is true. This corollary states that if a placement of a digit can force a grid into a BUG+1, such placement is true also.
Jeff

Posts: 708
Joined: 01 August 2005

I'm not sure if you know this but I figured out that Bug removal does not require the entire puzzle to have two possible solutions in each square except for one suqare. here is an example: http://www.brainbashers.com/sudokuload449 (I found it, at brainbashers.com so a thanks to them)
here we are looking at the 3 quadrants that make a row in the middle if R5C2 is 9 and a solution is found then the following can be switched to find an other solution: R4C3 with R5C3, R4C5 with R5C5, and R4C7 with R5C7. the definition of a BUG removal should be something more like: 1, 2, or 3 collums or rows of quadrants where all unsolved squares have 2 possible solutions, and each row and collum of squares in the quadrants that we are looking at have each possible solution (ex. it the quadrants we were looking at in row#4 there were two squares that could be 6, two squares that could be 8, and two squares that could be 4. also in collum#5, 6 is a possible solution twice and 8 is a possible solution twice.) thank you for reading my blatherings.
-Ben
ilovemathlikeaburger

Posts: 2
Joined: 25 March 2006

ilovemathlikeaburger wrote:I'm not sure if you know this but I figured out that Bug removal does not require the entire puzzle to have two possible solutions in each square except for one suqare.

Welcome to the forum, Mr Ilovemathlikeaburger.

You are right, it's called a BUG-Lite and a {9} can be fixed in r5c3 as a result. BUG-Lite is described in the first post of this thread as follow:

A BUG-Lite is a partial BUG pattern that exhibits similar properties of a BUG where all nodes in the pattern are bivalue and if a candidate exists in a row, column, or box, it shows up exactly twice. (example)
Jeff

Posts: 708
Joined: 01 August 2005

Cool, Thanks.
ilovemathlikeaburger

Posts: 2
Joined: 25 March 2006

A number of new techniques involving elimination of candidates within a Unique Rectangle based on the existance of strong links, ALS, and even a grouped strong link (RW's technique) have been developed. Many of the possible configurations for these eliminations have been identified here and here. Several of these techniques are directly extendable to BUGs and BUG-Lites (see here), but because of the more general nature of BUG-Lites, enumeration of the remaining techniques to BUG-Lites is daunting. There is, however, a general principle with allows all of these techniques (and more) to be applied to BUG-Lites. In the UR techniques the role of the strong link, ALS, or grouped strong link is to link each of the non-bivalued cells of the UR (except for the one where the elimination will occur) to another cell of the UR. If a consistent set of links can be constructed then selection of the appropriate value in a non-bivalued cell forces the development of a deadly pattern and the contradiction which allows that candidate to be eliminated. Viewed this way the new UR techniques and their extension to BUG-Lites form an error net with the existance of a non-unique solution as the contradiction as opposed to say proof that a cell must and cannot contain a certain candidate.

The linkage between need not be limited to the above list. A non-bivalued BUG-Lite cell which contains only candidates which are part of the BUG-Lite may be linked to multiple BUG-Lite cells to force the deadly pattern. In addition, any nice loop node or set of nodes can be used to create the linkage (XY-chains, strong link chains, AURs, almost X-wings, etc).

I've implemented advanced BUG-Lites using strong links and ALS. I've only gotten through the first 840 puzzles so far, but based on the Top1465, I'm seeing approximately 5 times more BUG-Lite eliminations (75 vs 15) with the advanced techniques verses the "basic" techniques already identified here. This is about what I observed when I implemented strong links and ALS techniques with URs. So far I've only seen one more puzzle solved with the advanced BUG-Lite techniques (#406). Without advanced BUG-Lites my solver only gets to:
Code: Select all
`+-------------------+--------------------+----------------+|  1389     5    36 |   1269  236    #12 |   389    4   7 ||  1369  1479  3467 |  14679    8  #3457 |  *135    2 *13 ||    18     2   347 |   1479   34  13457 |  1358   89   6 |+-------------------+--------------------+----------------+|     4    19    12 |      3    5      6 |   289    7  89 ||    27     6     5 |    278    9    #78 |     4  *13 *13 ||   279     3     8 |   1247   24  #1247 |    29    6   5 |+-------------------+--------------------+----------------+|    23    47  2347 |      5    1    #24 |     6   89  89 ||   156    18   126 |    268  236      9 |     7  135   4 ||    56   148     9 |    468    7   #348 |   *13 -135   2 |+-------------------+--------------------+----------------+`

The BUG-Lite is located in r9c78|r5c89|r2c79. The ALS located in r125679c6 which links to (r9c7|r2c9) with 3's to r2c7 with 5 (forcing r2c7=1), results in the elimination r9c8<>1. I still need to come up with some good nomenclature for describing the interactions. Note there are two other advanced BUG-Lites in the puzzle as well. The third one is (r1c147|r3c148|r7c89|r4c79):
Code: Select all
`+-----------------+-------------------+--------------+|  *18    5    36 | -1269  236     12 | *389   4   7 ||   39  479  3467 |   467    8    457 |  135   2  13 ||  *18    2   347 | *1479   34  13457 |  358 *89   6 |+-----------------+-------------------+--------------+|    4   19    12 |     3    5      6 | *289   7 *89 ||   27    6     5 |   278    9     78 |    4  13  13 ||  279    3     8 |   127   24    147 |  #29   6   5 |+-----------------+-------------------+--------------+|   23   47   347 |     5    1     24 |    6 *89 *89 ||    5   18    12 |    68  236      9 |    7  13   4 ||    6  148     9 |    48    7     38 |   13   5   2 |+-----------------+-------------------+--------------+`

and utilizes strong links between r1c4=9=r1c7 and r1c4=9=r3c4 and an ALS (actually the bivalue located at r6c7) to link r1c7 and r4c7 and results in the elimination: r1c4<>1.
Last edited by Mike Barker on Wed Feb 20, 2008 7:58 pm, edited 3 times in total.
Mike Barker

Posts: 458
Joined: 22 January 2006

Very nice finds Mike. This is only terminology, but shouldn't these be called BUG-lites to avoid confusion? As I understood it a BUG should take up all unsolved cells in the grid. Then a question about the last example.

Mike Barker wrote:The third one ... utilizes strong links between r1c4=9=r1c7 and r1c4=9=r3c4 and an ALS (actually the bivalue located at r6c7) to link r1c7 and r4c7 and results in the elimination: r1c4<>1.

Is the ALS really needed? There is also the strong link r4c7=8=r4c9.

Code: Select all
`18    19+X====89+W       ||   9      9||       ||18    19+Y          89              89+Z========89                     8                    89    89`

From this diagram I can tell without considering any extra cells that r1c4<>1.

RW
RW
2010 Supporter

Posts: 1010
Joined: 16 March 2006

RW, you are right they are BUG-lites. I guess I've gotten into the habit of dropping the "lite", but when posting I should be more exact. Also, the net is not necessarily unique, however, since finding a strong link is much easier than an ALS, a human would do this first. I should modify my solver to give priority to strong links.
Mike Barker

Posts: 458
Joined: 22 January 2006

### Bug type 3

Hi,
Does anybody know a puzzle with a BUG type 3? I have no idea about how it is looking like.

Claudia
claudiarabia

Posts: 288
Joined: 14 May 2006

### Re: Bug type 3

claudiarabia wrote:Hi,
Does anybody know a puzzle with a BUG type 3? I have no idea about how it is looking like.

Claudia

You might check out Mike Barker's contributions to the zoo ... here.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: Bug type 3

You might check out Mike Barker's contributions to the zoo ... here.[/quote]

Thank you. I've found it now. I searched there before but some of these puzzles defined as BUG type 3 Sudoku-Explainer rated as Bug type 2 or Bug type 4. It depends in which order you place the numbers, and then you will have different patterns in the end. It So I lost patience first.

Claudia
claudiarabia

Posts: 288
Joined: 14 May 2006

This is just a test to see if "database problem" can be cleared with an additional post ... or two ... or three
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:This is just a test to see if "database problem" can be cleared with an additional post ... or two ... or three

to get past 15
( 15 Posts per "page" )

Pat

Posts: 3904
Joined: 18 July 2005

Last edited by Pat on Mon Nov 06, 2006 1:01 pm, edited 1 time in total.

Pat

Posts: 3904
Joined: 18 July 2005

12

Pat

Posts: 3904
Joined: 18 July 2005

14?

Pat

Posts: 3904
Joined: 18 July 2005

PreviousNext