| View previous topic :: View next topic |
| Author |
Message |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
 Posted: Sun Sep 23, 2007 6:59 pm Post subject: A Double Bug? |
 |
|
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 |
|
 |
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sat Sep 29, 2007 4:52 am Post subject: |
|
|
| 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 |
|
|
Steve R
Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England
|
| Posted: Sat Sep 29, 2007 11:56 am Post subject: |
|
|
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 |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sat Sep 29, 2007 4:27 pm Post subject: |
|
|
| Thank you Steve. Things aren't always as simple and straightforward as I'd like them to be. |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Apr 19, 2008 7:41 pm Post subject: |
|
|
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 |
|
|
Asellus
Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA
|
| Posted: Sun Apr 20, 2008 12:39 am Post subject: |
|
|
| 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 |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Apr 20, 2008 2:47 am Post subject: |
|
|
| 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  |
|
| Back to top |
|
|
Asellus
Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA
|
| Posted: Sun Apr 20, 2008 7:53 pm Post subject: |
|
|
| 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 |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Mon Apr 21, 2008 10:27 am Post subject: |
|
|
Aha! Now I see it!
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 |
|
|
Victor
Joined: 29 Sep 2005
Posts: 207
Location: NI
|
| Posted: Thu May 01, 2008 11:53 am Post subject: |
|
|
| Being doing my homework! Thanks to all contributors to this thread - BUG+x is a bit more clear now. |
|
| Back to top |
|
|
Myth Jellies
Joined: 27 Jun 2006
Posts: 64
|
| Posted: Sat May 03, 2008 8:04 am Post subject: |
|
|
| 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 |
|
|
Steve R
Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England
|
| Posted: Sat May 03, 2008 3:16 pm Post subject: |
|
|
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 |
|
|
Myth Jellies
Joined: 27 Jun 2006
Posts: 64
|
| Posted: Sun May 04, 2008 9:23 am Post subject: |
|
|
| 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 |
|
|
|
|
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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
