dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

A Double Bug?

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sun Sep 23, 2007 6:59 pm    Post subject: A Double Bug? Reply with quote

I've tried this reasoning a couple of times. This is the first time it has worked out!

This is the Super Hard Brain Basher from July 2, 2007:
Code:
Puzzle: BB070207sh
+-------+-------+-------+
| . . 4 | . . . | 6 . . |
| 9 . 2 | . . . | 3 . 8 |
| 3 8 . | 2 . 9 | . 7 4 |
+-------+-------+-------+
| . . . | 5 1 6 | . . . |
| . 2 . | 7 . 3 | . 6 . |
| . . . | 9 2 8 | . . . |
+-------+-------+-------+
| 2 1 . | 3 . 5 | . 4 6 |
| 5 . 3 | . . . | 9 . 1 |
| . . 8 | . . . | 7 . . |
+-------+-------+-------+

Basic moves, plus an X-wing on <1> get you to here:
Code:
+-------------+-------------+-------------+
| 17  5   4   | 8   3   17  | 6   9   2   |
| 9   67  2   | 46  567 147 | 3   15  8   |
| 3   8   16  | 2   56  9   | 15  7   4   |
+-------------+-------------+-------------+
| 47  49  79  | 5   1   6   | 2   8   3   |
| 8   2   15  | 7   4   3   | 15  6   9   |
| 16  3   56  | 9   2   8   | 4   15  7   |
+-------------+-------------+-------------+
| 2   1   79  | 3   79  5   | 8   4   6   |
| 5   67  3   | 46  8   47  | 9   2   1   |
| 46  49  8   | 1   69  2   | 7   3   5   |
+-------------+-------------+-------------+

Except for R2C56, all the unsolved cells have two candidates.

The BUG principle is that if all the unsolved cells have only two candidates, it is a deadly pattern and the puzzle does not have a unique solution.

Further, in a grid where each cell has only two candidates, each candidate value will appear exactly twice in each row, column or block.

The candidates in C5 are:
567, 56, 79, 69. The deadly pattern would be 57, 56, 79, 69.

The candidates in C6 are:
17, 147, 47. The deadly pattern would be 17, 14, 47.

Check in R2: The candidates are 67, 46, 57, 14, 15, which is a deadly pattern.

To repeat:
Code:
+-------------+-------------+-------------+
| 17  5   4   | 8   3   17  | 6   9   2   |
| 9   67  2   | 46  57  14  | 3   15  8   |
| 3   8   16  | 2   56  9   | 15  7   4   |
+-------------+-------------+-------------+
| 47  49  79  | 5   1   6   | 2   8   3   |
| 8   2   15  | 7   4   3   | 15  6   9   |
| 16  3   56  | 9   2   8   | 4   15  7   |
+-------------+-------------+-------------+
| 2   1   79  | 3   79  5   | 8   4   6   |
| 5   67  3   | 46  8   47  | 9   2   1   |
| 46  49  8   | 1   69  2   | 7   3   5   |
+-------------+-------------+-------------+

must be avoided! The only way to do this is R2C5 is <6> or R2C6 is <7>. These form a pair with R2C2 <67>, so R2C4 must be <4>, and the puzzle is solved.

I mentioned I had tried this before. What happens is that you cannot always find a valid deadly pattern. In this example, you might have found that you could argue the values in the columns, but the candidates in the row would not then be valid.

(And yes, I know there is an X-wing which leads to a BUG+1, but this is so much more fun!)

Keith
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Sat Sep 29, 2007 4:52 am    Post subject: Reply with quote

Quote:
I mentioned I had tried this before. What happens is that you cannot always find a valid deadly pattern. In this example, you might have found that you could argue the values in the columns, but the candidates in the row would not then be valid.


Consider the following:

Code:

+------------+----------+-------+
| 14  145 15 | 7  2  3  | 8 9 6 |
| 6   2   7  | 8  59 59 | 4 3 1 |
| 3   8   9  | 4  1  6  | 7 5 2 |
+------------+----------+-------+
| 8   6   25 | 25 3  7  | 9 1 4 |
| 7   59  4  | 6  59 1  | 3 2 8 |
| 19  3   12 | 29 4  8  | 5 6 7 |
+------------+----------+-------+
| 5   19  6  | 19 7  4  | 2 8 3 |
| 249 49  8  | 3  6  29 | 1 7 5 |
| 12  7   3  | 15 8  25 | 6 4 9 |
+------------+----------+-------+

Play this puzzle online at the Daily Sudoku site

The puzzle is easily solved with the W-Wing on 19, and perhaps other methods which I haven't looked for.

On the surface it looks like a solution could be obtained via the BUG+2, with the only trivalue cells being in r1c2 and r8c1. Either r1c2 must be 1 or r8c1 must be 9. However, neither the 1 nor the 9 meets the BUG+1 requirement of being present thrice in the row, column and box. Does this by itself preclude the use of BUG+2?

Conversely, when each trivalue cell contains a number that does occur thrice in row, column and box, does this by itself assure that the BUG+2 CAN be used?
Back to top
View user's profile Send private message
Steve R



Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England

PostPosted: Sat Sep 29, 2007 11:56 am    Post subject: Reply with quote

Marty

The answers to you questions are “yes” and “no” respectively.

It may help to think through why it is necessary to avoid a grid in which each unsolved cell is bivalent and, in addition, each candidate of the unsolved cells occurs twice in each house. Suppose such a situation arises. If the puzzle has a solution, you can select a candidate for each cell which produces it. Evidently the selected candidates occur once in each house. However, if you then take the other candidate for each unsolved cell, each of these must also occur once in each house: you have produced a second solution.

As you rightly point out, your example contains no subset of candidates which occur twice in each house, so there is no underlying BUG to form the base of a BUG+2.

The reason for the answer “no” to your second question is that it possible to have a grid in which the bivalent cells themselves offer three appearances of a candidate in a house. Then it does not matter what the trivalent cells contain: there can again be no underlying BUG pattern.

Steve
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Sat Sep 29, 2007 4:27 pm    Post subject: Reply with quote

Thank you Steve. Things aren't always as simple and straightforward as I'd like them to be.
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Apr 19, 2008 7:41 pm    Post subject: Reply with quote

The puzzle of this thread:

http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2484

reduces to:
Code:
+-------------+-------------+-------------+
| 1   38  27  | 89  5   4   | 27  6   39  |
| 9   4   23  | 7   6   1   | 5   23  8   |
| 6   5   78  | 89  3   2   | 79  4   1   |
+-------------+-------------+-------------+
| 2   89  58  | 1   789 3   | 4   57  6   |
| 4   6   1   | 2   79  5   | 8   37  39  |
| 7   389 358 | 4   89  6   | 19  15  2   |
+-------------+-------------+-------------+
| 8   2   6   | 5   1   7   | 3   9   4   |
| 3   7   9   | 6   4   8   | 12  12  5   |
| 5   1   4   | 3   2   9   | 6   8   7   |
+-------------+-------------+-------------+

which is possibly a BUG+3. But, no. Look at R4C5 <789>.

In R4, to make a BUG pattern, R4C5 must be <79>.
In R5, to make a BUG pattern, R4C5 must be <78>.

There is no underlying BUG. But, as Steve R. points out, there is a Uniqueness argument: The diagonal (Type 6?) UR on <89> in R46C25.

Keith
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Sun Apr 20, 2008 12:39 am    Post subject: Reply with quote

keith wrote:
There is no underlying BUG.

Well... actually, there is. But, it is a BUG+4, not a BUG+2:
Code:
+-----------------+---------------+-------------+
| 1   38    27    | 89  5     4   | 27  6   39  |
| 9   4     23    | 7   6     1   | 5   23  8   |
| 6   5     78    | 89  3     2   | 79  4   1   |
+-----------------+---------------+-------------+
| 2  (8)9   58    | 1   78(9) 3   | 4   57  6   |
| 4   6     1     | 2   79    5   | 8   37  39  |
| 7   38(9) 35(8) | 4   89    6   | 19  15  2   |
+-----------------+---------------+-------------+
| 8   2     6     | 5   1     7   | 3   9   4   |
| 3   7     9     | 6   4     8   | 12  12  5   |
| 5   1     4     | 3   2     9   | 6   8   7   |
+-----------------+---------------+-------------+

Seeing it requires looking beyond the two trivalues and isn't all that easy. But, if you were to find it, it leads to a solution. Either of the two "extra"digits in c2 result in r4c5=9. And, if r6c3=8, r6c5=9. So, r5c5=7.
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sun Apr 20, 2008 2:47 am    Post subject: Reply with quote

Asellus wrote:
keith wrote:
There is no underlying BUG.

Well... actually, there is. But, it is a BUG+4, not a BUG+2

Really? I thought we were looking at a possible BUG+3.

I need to think about this, when my brain is free of the well-known product of Sonoma County. What are we looking at?:

1. It is a BUG, here are the subsequent eliminations.

2. It might be a BUG, here are the eliminations that make it so.

Keith Question Question
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Sun Apr 20, 2008 7:53 pm    Post subject: Reply with quote

keith wrote:
when my brain is free of the well-known product of Sonoma County

You mean cheese?
Quote:
I thought we were looking at a possible BUG+3.

I don't know why I wrote BUG+2 and referred to two trivalues. It is clearly three. (And I hadn't even had any cheese!)

Just to be clear, if you removed the four digits shown in parentheses, you would be left with a BUG. So at least one of those four must be true. And, as I noted, any of them being true result in r5c5=7.

It just shows that a potential BUG may depend upon losing one or more bivalue digits when there is more than one trivalue present.
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Mon Apr 21, 2008 10:27 am    Post subject: Reply with quote

Aha! Now I see it!

Quote:
You mean cheese?


Yes. The red kind, that is very runny. But, it was not the cheese. It was your second explanation that allowed me to see it.

Maybe this is a BUG with Greatly Extended Reasoning: BUGGER.

Keith
Back to top
View user's profile Send private message
Victor



Joined: 29 Sep 2005
Posts: 207
Location: NI

PostPosted: Thu May 01, 2008 11:53 am    Post subject: Reply with quote

Being doing my homework! Thanks to all contributors to this thread - BUG+x is a bit more clear now.
Back to top
View user's profile Send private message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Sat May 03, 2008 8:04 am    Post subject: Reply with quote

Code:
+-------------+-------------+-------------+
| 1   38  27  | 89  5   4   | 27  6   39  |
| 9   4   23  | 7   6   1   | 5   23  8   |
| 6   5   78  | 89  3   2   | 79  4   1   |
+-------------+-------------+-------------+
| 2   89  58  | 1   789 3   | 4   57  6   |
| 4   6   1   | 2   79  5   | 8   37  39  |
| 7   389 358 | 4   89  6   | 19  15  2   |
+-------------+-------------+-------------+
| 8   2   6   | 5   1   7   | 3   9   4   |
| 3   7   9   | 6   4   8   | 12  12  5   |
| 5   1   4   | 3   2   9   | 6   8   7   |
+-------------+-------------+-------------+


What you actually have here is a gigantic BUG-Lite+3. All the starred cells are part of the BUG-Lite. Note that the only unsolved cell that isn't part of the BUG-Lite is r4c2.

Code:
+----------------+--------------+-------------+
| 1  *38   *27   |*89  5    4   |*27  6  *39  |
| 9   4    *23   | 7   6    1   | 5  *23  8   |
| 6   5    *78   |*89  3    2   |*79  4   1   |
+----------------+--------------+-------------+
| 2   89   *58   | 1  *78+9 3   | 4  *57  6   |
| 4   6     1    | 2  *79   5   | 8  *37 *39  |
| 7  *38+9 *35+8 | 4  *89   6   |*19 *15  2   |
+----------------+--------------+-------------+
| 8   2     6    | 5   1    7   | 3   9   4   |
| 3   7     9    | 6   4    8   |*12 *12  5   |
| 5   1     4    | 3   2    9   | 6   8   7   |
+----------------+--------------+-------------+


The same logic already mentioned above eliminates the 9 in r5c5. Maybe even easier to see that each of the three extra candidates forces an 8 in either r6c3 or r4c2; hence r6c2 & r4c3 <> 8. Not very practical to find compared to the 89-UR, but definitely fun.
Back to top
View user's profile Send private message
Steve R



Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England

PostPosted: Sat May 03, 2008 3:16 pm    Post subject: Reply with quote

Excellent analysis, MJ!

As well as finding a BUG-Light by omitting r4c2, I think you could instead have chosen to omit r6c5:

Code:
+----------------+--------------+-------------+
| 1  *38   *27   |*89  5    4   |*27  6  *39  |
| 9   4    *23   | 7   6    1   | 5  *23  8   |
| 6   5    *78   |*89  3    2   |*79  4   1   |
+----------------+--------------+-------------+
| 2  *89   *58   | 1  *79+8 3   | 4  *57  6   |
| 4   6     1    | 2  *79   5   | 8  *37 *39  |
| 7  *39+8 *35+8 | 4   89   6   |*19 *15  2   |
+----------------+--------------+-------------+
| 8   2     6    | 5   1    7   | 3   9   4   |
| 3   7     9    | 6   4    8   |*12 *12  5   |
| 5   1     4    | 3   2    9   | 6   8   7   |
+----------------+--------------+-------------+

This is no easier to spot but, by chance, the eliminations are more obvious.

Keith originally called the subject A Double BUG? If I have it right, it is indeed a double BUG-Light + 3.

Steve
Back to top
View user's profile Send private message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Sun May 04, 2008 9:23 am    Post subject: Reply with quote

Nice one, Steve. It is actually a fun challenge to come up with the best big BUG-Lites that always exist in these "not-quite-right-for-a-BUG" type grids. It can't get any better than yours.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group