The BUG (Bivalue Universal Grave) principle

Advanced methods and approaches for solving Sudoku puzzles

Postby Jeff » Mon Feb 06, 2006 4:11 am

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

Postby ilovemathlikeaburger » Sat Mar 25, 2006 7:26 pm

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

Postby Jeff » Sat Mar 25, 2006 8:12 pm

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.

Image

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

Postby ilovemathlikeaburger » Sat Mar 25, 2006 8:46 pm

Cool, Thanks.
ilovemathlikeaburger
 
Posts: 2
Joined: 25 March 2006

Postby Mike Barker » Thu Jun 22, 2006 5:00 am

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

Postby RW » Thu Jun 22, 2006 8:14 am

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: 1000
Joined: 16 March 2006

Postby Mike Barker » Thu Jun 22, 2006 1:10 pm

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

Postby claudiarabia » Sun Nov 05, 2006 10:30 pm

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

Postby daj95376 » Sun Nov 05, 2006 11:17 pm

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

Postby claudiarabia » Mon Nov 06, 2006 3:06 pm

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

Postby ronk » Mon Nov 06, 2006 4:24 pm

This is just a test to see if "database problem" can be cleared with an additional post ... or two ... or three:D
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Pat » Mon Nov 06, 2006 4:58 pm

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

probably need about 5 more
to get past 15
( 15 Posts per "page" )
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Postby Pat » Mon Nov 06, 2006 4:59 pm

probably need about 4 more
Last edited by Pat on Mon Nov 06, 2006 1:01 pm, edited 1 time in total.
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Postby Pat » Mon Nov 06, 2006 5:00 pm

12
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Postby Pat » Mon Nov 06, 2006 5:02 pm

14?
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

PreviousNext

Return to Advanced solving techniques

cron