Help with BUG

Advanced methods and approaches for solving Sudoku puzzles

Help with BUG

Postby EnderGT » Tue Feb 19, 2008 11:19 pm

While attacking the Paul's Pages Daily SudokuXP Extreme puzzle, I encountered some difficulty in determining how to apply the BUG rule.

The original puzzle is
030001050004020000900000070800000600700900001002004003050000008000060200090300040

The puzzle in the state that I encountered trouble is
630001052104020000925836174849173625763952481512684793050207008000060200290318540

In this state, all cells have 2 candidates except for R2C7 and R8C3. In each of these two cells, there is 1 candidate that appears 3 times in each row, column, and box that the cell belongs to. Additionally, removing the suspect candidate results in that candidate appearing exactly twice in each row, column, and box (with the exception of the other BUG suspect cell). For R2C7 it's the 9, for R8C3 it's the 7.

Sounds like 2 BUGs to me... except one is and one isn't, and I can't figure out how I'm supposed to identify which is and which isn't. The only reason I know right now is that the program told me that one of them was incorrect.

Can someone take a look and tell me what I'm missing, and what to look for in the future? Thanks...
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby ArkieTech » Tue Feb 19, 2008 11:49 pm

EnderGT said
Can someone take a look and tell me what I'm missing

There is a locked set 49,39, 43 in row 7 allowing the removal of 3 in r7c8 which leaves a Bug+1.

dan
dan
User avatar
ArkieTech
 
Posts: 2653
Joined: 29 May 2006
Location: NW Arkansas USA

Postby ab » Wed Feb 20, 2008 12:17 am

why don't you do the sensible thing and solve it with an xy chain? BUG's rely on the uniqueness of the solution yuck
ab
 
Posts: 451
Joined: 06 September 2005

Postby sirdave » Wed Feb 20, 2008 2:15 am

ab wrote:why don't you do the sensible thing and solve it with an xy chain? BUG's rely on the uniqueness of the solution yuck


Why 'yuck'. Uniqueness assumes only one solution. Virtually every published sudoku puzzle has only one solution. But let's assume for the moment that there might be more than one solution which would make an xy chain preferable to using BUG. Now you're in a situation where, since there might be more than one solution, you can't be sure that your solution is only one of several. Yuck

Of course, it's easy to use a solver to establish that there is only one solution or not, but who bothers these days because, again, virtually every puzzle only has one solution. Those who avoid uniqueness-based methods are unnecessarily limiting their solving alternatives.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby EnderGT » Wed Feb 20, 2008 2:45 am

ArkieTech wrote:EnderGT said
Can someone take a look and tell me what I'm missing

There is a locked set 49,39, 43 in row 7 allowing the removal of 3 in r7c8 which leaves a Bug+1.

dan


Sorry I didn't specify - I'd already removed that 3. The only 2 squares that have more than 2 candidates are the 2 I identified in my first post.

I consider myself to be pretty good at sudoku - the puzzles rated as Really Tough at www.paulspages.co.uk/sudoku I can solve fairly easily - but I've recently been made aware that I'm still at a fairly moderate skill level. I've been using the www.paulspages.co.uk/sudokuxp daily puzzles to try to teach myself some of the more advanced tricks you all seem to be quite adept at using.

BUG is a new one for me. I used the analysis tool to know what techniques to watch out for, which is why I know there's a BUG here at all. I'm assuming that BUG+1 means that there's at least one other cell that hasn't been reduced to 2 candidates yet? How do I identify which cell is the BUG and which is the +1?
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby EnderGT » Wed Feb 20, 2008 3:10 am

ab wrote:why don't you do the sensible thing and solve it with an xy chain? BUG's rely on the uniqueness of the solution yuck


It has always seemed to me that a forcing chain is nothing more than glorified guessing. Am I wrong on this?

I'm assuming that's what you mean by xy-chain - if not, please do correct me.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby Mike Barker » Wed Feb 20, 2008 4:37 am

First of all, let me put in a vote for uniqueness tests including BUGs. They are generally easy to spot and can solve many moderate puzzles. As Myth has pointed out, if a puzzle maker doesn't provide a puzzle with a unique solution, I'll take my business elsewhere. As far as XY-chains they are nice forcing chains (Jeff's nice loops) which don't rely on assuming a starting cell. They are considered excellent solving techniques by many.

As far as your puzzle, I wouldn't apply a BUG at this point (an X-wing can eliminate 9 from r2c7 leaving a simple BUG+1 or as ab said simply use an xy-chain). If you really want to then you'll need to apply and advanced BUG which links the non-bivalued cells, but this is much more complicated than alternatives for this puzzle. In this case the buggy approach is:
Code: Select all
r8c3 -1- r8c8 -3- r2c8 =3= r2c7 -9- BUG:{r2c7 =7= r8c3} => r8c3<>1
r2c7 -3- r2c8 =3= r8c8 =1= r8c3 -7- BUG:{r8c3 =9= r2c7} => r2c7<>3
+---------------+-------------+---------------+
|  6   3    78* | 47* 49*  1  |   89*  5   2  |
|  1  78*    4  | 57*  2  59* | 89-3* 36* 69* |
|  9   2     5  |  8   3   6  |    1   7   4  |
+---------------+-------------+---------------+
|  8   4     9  |  1   7   3  |    6   2   5  |
|  7   6     3  |  9   5   2  |    4   8   1  |
|  5   1     2  |  6   8   4  |    7   9   3  |
+---------------+-------------+---------------+
| 34*  5    16* |  2  49*  7  |   39* 16*  8  |
| 34* 78* 78-1* | 45*  6  59* |    2  13* 79* |
|  2   9    67* |  3   1   8  |    5   4  67* |
+---------------+-------------+---------------+


The alternative XY-chain is:
Code: Select all
4-node XY-chain: r9c3 -7- r1c3 -8- r1c7 -9- r2c9 -6-  => r9c9<>6
+--------------+-------------+----------------+
|  6   3   78* | 47  49   1  |  89*   5    2  |
|  1  78    4  | 57   2  59  | 389   36   69* |
|  9   2    5  |  8   3   6  |   1    7    4  |
+--------------+-------------+----------------+
|  8   4    9  |  1   7   3  |   6    2    5  |
|  7   6    3  |  9   5   2  |   4    8    1  |
|  5   1    2  |  6   8   4  |   7    9    3  |
+--------------+-------------+----------------+
| 34   5   16  |  2  49   7  |  39  136    8  |
| 34  78  178  | 45   6  59  |   2   13   79  |
|  2   9   67* |  3   1   8  |   5    4  7-6  |
+--------------+-------------+----------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Wed Feb 20, 2008 5:50 am

Mike Barker wrote:the buggy approach is:
Code: Select all
r8c3 -1- r8c8 -3- r2c8 =3= r2c7 -9- BUG:{r2c7 =7= r8c3} => r8c3<>1
r2c7 -3- r2c8 =3= r8c8 =1= r8c3 -7- BUG:{r8c3 =9= r2c7} => r2c7<>3
+---------------+-------------+---------------+
|  6   3    78* | 47* 49*  1  |   89*  5   2  |
|  1  78*    4  | 57*  2  59* | 89-3* 36* 69* |
|  9   2     5  |  8   3   6  |    1   7   4  |
+---------------+-------------+---------------+
|  8   4     9  |  1   7   3  |    6   2   5  |
|  7   6     3  |  9   5   2  |    4   8   1  |
|  5   1     2  |  6   8   4  |    7   9   3  |
+---------------+-------------+---------------+
| 34*  5    16* |  2  49*  7  |   39* 16*  8  |
| 34* 78* 78-1* | 45*  6  59* |    2  13* 79* |
|  2   9    67* |  3   1   8  |    5   4  67* |
+---------------+-------------+---------------+

I still prefer a BUG+N illustration ...
Code: Select all
+---------------+-------------+---------------+
|  6   3   78   | 47  49   1  |  89    5   2  |
|  1  78    4   | 57   2  59  |  38+9 36  69  |
|  9   2    5   |  8   3   6  |   1    7   4  |
+---------------+-------------+---------------+
|  8   4    9   |  1   7   3  |   6    2   5  |
|  7   6    3   |  9   5   2  |   4    8   1  |
|  5   1    2   |  6   8   4  |   7    9   3  |
+---------------+-------------+---------------+
| 34   5   16   |  2  49   7  |  39   16   8  |
| 34  78   18+7 | 45   6  59  |   2   13  79  |
|  2   9   67   |  3   1   8  |   5    4  67  |
+---------------+-------------+---------------+

... making it obvious that at least one of r2c7=9 and r8c3=7 must be true. The single nice loop ...

r8c3 -1- r8c8 -3- r7c7 -9- BUG:(r2c7 =9|7= r8c3) => r8c3<>1

... and singles solves the puzzle.

The above uses three strong inferences compared to four for your alternative xy-chain, and I think the BUG+2 is just as easy, if not easier, to spot.

[edit: r7c7 was typo r2c7]
Last edited by ronk on Thu Feb 21, 2008 10:26 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

against assuming Uniqueness-Of-Answer

Postby Pat » Wed Feb 20, 2008 9:24 am

sirdave wrote:
ab wrote:why don't you do the sensible thing and solve it with an xy chain? BUG's rely on the uniqueness of the solution yuck



Why 'yuck'. Uniqueness assumes only one solution. Virtually every published sudoku puzzle has only one solution. But let's assume for the moment that there might be more than one solution which would make an xy chain preferable to using BUG. Now you're in a situation where, since there might be more than one solution, you can't be sure that your solution is only one of several. Yuck

Of course, it's easy to use a solver to establish that there is only one solution or not, but who bothers these days because, again, virtually every puzzle only has one solution. Those who avoid uniqueness-based methods are unnecessarily limiting their solving alternatives.



no, sirdave, when i use an xy-chain and i do reach an answer, i do know it is the only answer.
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby EnderGT » Wed Feb 20, 2008 1:09 pm

Mike Barker wrote:if a puzzle maker doesn't provide a puzzle with a unique solution, I'll take my business elsewhere.

I'm in agreement here.

Mike Barker wrote:As far as XY-chains they are nice forcing chains (Jeff's nice loops) which don't rely on assuming a starting cell. They are considered excellent solving techniques by many.


I will have to look into these more, because I still don't see how they could be considered anything but guessing.

Mike Barker wrote:As far as your puzzle, I wouldn't apply a BUG at this point (an X-wing can eliminate 9 from r2c7 leaving a simple BUG+1 or as ab said simply use an xy-chain).

Thanks for pointing that out, I didn't see that. As I said, I was using the analysis on the paulspages site, and it had said there was only 1 X-wing, which I'd already found, so I wasn't looking for another.

Mike Barker wrote:The alternative XY-chain is:
Code: Select all
4-node XY-chain: r9c3 -7- r1c3 -8- r1c7 -9- r2c9 -6-  => r9c9<>6
+--------------+-------------+----------------+
|  6   3   78* | 47  49   1  |  89*   5    2  |
|  1  78    4  | 57   2  59  | 389   36   69* |
|  9   2    5  |  8   3   6  |   1    7    4  |
+--------------+-------------+----------------+
|  8   4    9  |  1   7   3  |   6    2    5  |
|  7   6    3  |  9   5   2  |   4    8    1  |
|  5   1    2  |  6   8   4  |   7    9    3  |
+--------------+-------------+----------------+
| 34   5   16  |  2  49   7  |  39  136    8  |
| 34  78  178  | 45   6  59  |   2   13   79  |
|  2   9   67* |  3   1   8  |   5    4  7-6  |
+--------------+-------------+----------------+

Could you explain this more? I understand XY-wing, but making it a chain... how do you know which candidates should be removed?
Edit: Ok, reading the snippet you had before, this isn't about removing candidates, it's about assuming that your first cell is a certain value and then proving that it can't be that value. How is this not guessing?
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby eleven » Wed Feb 20, 2008 4:51 pm

Code: Select all
+--------------+-------------+----------------+
|  6   3   78* | 47* 49   1  |  89    5    2  |
|  1  78*   4  | 57   2  59  | 389   36   69  |
|  9   2    5  |  8   3   6  |   1    7    4  |
+--------------+-------------+----------------+
|  8   4    9  |  1   7   3  |   6    2    5  |
|  7   6    3  |  9   5   2  |   4    8    1  |
|  5   1    2  |  6   8   4  |   7    9    3  |
+--------------+-------------+----------------+
| 34   5   16  |  2  49   7  |  39  136    8  |
| 34 -78  178  | 45*  6  59* |   2   13   79* |
|  2   9   67  |  3   1   8  |   5    4   76  |
+--------------+-------------+----------------+

I agree, that xy-chains are kind of guessing, because you have to guess, where to begin to search for one. E.g. in this grid i found this one first, though it is longer than Mike Barker's. When once started (r2c2=7 -> r8c2!=7), it is clear, where you must try to get to: from r2c2=8 to either r8c9=7 or r9c3=7. If there is a path with 2-values, you will find it, if 4 cells or 6. If not, try the next pair:( It is the same for xy-wings, try one after the other (but shorter).

But here the BUG is much better, as ronk said.
Code: Select all
+---------------+-------------+---------------+
|  6   3   78   | 47  49   1  |  89    5   2  |
|  1  78    4   | 57   2  59  |  38+9 36 6-9  |
|  9   2    5   |  8   3   6  |   1    7   4  |
+---------------+-------------+---------------+
|  8   4    9   |  1   7   3  |   6    2   5  |
|  7   6    3   |  9   5   2  |   4    8   1  |
|  5   1    2   |  6   8   4  |   7    9   3  |
+---------------+-------------+---------------+
| 34   5   16   |  2  49   7  | 3-9   16   8  |
| 34  78   18+7 | 45   6  59  |   2   13  79* |
|  2   9   67   |  3   1   8  |   5    4  67  |
+---------------+-------------+---------------+

You also can use it this way: r8c3=7 or r2c7=9.
r8c3=7 -> r8c9=9: r2c9!=9, r7c7!=9
eleven
 
Posts: 1557
Joined: 10 February 2008

Postby ab » Wed Feb 20, 2008 9:24 pm

EnderGT wrote:Edit: Ok, reading the snippet you had before, this isn't about removing candidates, it's about assuming that your first cell is a certain value and then proving that it can't be that value. How is this not guessing?

eleven wrote:I agree, that xy-chains are kind of guessing

xy chains are not guessing they're pattern based. In this example there are two possibilities for row 9 column 3. If it's 7 then row 1 column 3 must be 8, so row 1 column 7 must be 9 therefore row 2 column 9 is 6. Alternatively row 9 column 3 is 6. Either way row 9 column 9 can't be 6. Where is the guesswork?

I don't like uniqueness tests because it's not using pure logic, it's making an extra assumption. Yes I want my puzzles to have a unique solution and if I get puzzles from a source that don't have a unique soltion I will not return to that source. But if I use uniqueness tests as part of my solving arsenal I may never find out that a puzzle has more than one solution:!:
ab
 
Posts: 451
Joined: 06 September 2005

Postby EnderGT » Wed Feb 20, 2008 11:12 pm

ab wrote:xy chains are not guessing they're pattern based. In this example there are two possibilities for row 9 column 3. If it's 7 then row 1 column 3 must be 8, so row 1 column 7 must be 9 therefore row 2 column 9 is 6. Alternatively row 9 column 3 is 6. Either way row 9 column 9 can't be 6. Where is the guesswork?


I bolded the part where you guessed.

I don't like uniqueness tests because it's not using pure logic, it's making an extra assumption. Yes I want my puzzles to have a unique solution and if I get puzzles from a source that don't have a unique soltion I will not return to that source. But if I use uniqueness tests as part of my solving arsenal I may never find out that a puzzle has more than one solution:!:

While I understand your reasoning here, it seems to me that applying an assumption of uniqueness to a puzzle that isn't, in fact, unique, would actually end up resulting in a no-solution state. If this happens, then you have identified a puzzle that has more than one solution!

Either way, encountering a puzzle that has multiple solutions is a huge disappointment to me - the way I see it, someone just wasted my time.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby sirdave » Wed Feb 20, 2008 11:30 pm

I don't like uniqueness tests because it's not using pure logic, it's making an extra assumption. Yes I want my puzzles to have a unique solution and if I get puzzles from a source that don't have a unique soltion I will not return to that source. But if I use uniqueness tests as part of my solving arsenal I may never find out that a puzzle has more than one solution:!:


To each his own, of course. But if we are now at a point where virtually every published puzzle has only one solution and virtually everyone appears to agree that they will find any puzzle with more than one solution unacceptable, to the point that no one on any of the Sudoku forums wants to use or discuss multi-solution puzzles, then, in my view, we now have what is a collective standard established. We don't just assume there is a single solution; we know there is a single solution. With that in mind, I see uniqueness-based methods as purely logical.

Not using uniqueness-based methods can really limit solving with more advanced puzzles (AURs etc.). While I'm still learning to make the most of them, people such as Carcul & Myth have given pretty good evidence of what you can do with AURs, BUG, BUG-LITE etc.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby tarek » Wed Feb 20, 2008 11:34 pm

EnderGT wrote:
ab wrote:xy chains are not guessing they're pattern based. In this example there are two possibilities for row 9 column 3. If it's 7 then row 1 column 3 must be 8, so row 1 column 7 must be 9 therefore row 2 column 9 is 6. Alternatively row 9 column 3 is 6. Either way row 9 column 9 can't be 6. Where is the guesswork?


I bolded the part where you guessed.
This discussion can go forever.

The human way of thinking doesn't usually follow the "if ... then" statement when solving. You can visualise the start, the process & the result at the same time. Occasionally the process isn't even there... It is difficult to label that as guessing.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Next

Return to Advanced solving techniques

cron