View previous topic :: View next topic 
Author 
Message 
keith
Joined: 19 Sep 2005 Posts: 3165 Location: near Detroit, Michigan, USA

Posted: Sat Feb 11, 2006 3:54 pm Post subject: Two More Puzzles 


The David Bodycombe puzzles (published locally in the Detroit Free Press) have become significantly more interesting in the past couple of weeks.
Here is the puzzle from yesterday (5 stars)
Code: 
Puzzle: DB021006
++++
 . 8 .  . . .  . 7 . 
 3 1 .  2 . .  . . . 
 . 9 5  6 . 8  . 1 . 
++++
 . . .  . 5 .  7 9 . 
 9 . .  . . .  . . 8 
 . 5 1  . 8 .  . . . 
++++
 . 7 .  1 . 4  9 5 . 
 . . .  . . 6  . 8 4 
 . 3 .  . . .  . 6 . 
++++

and here is the one from last Sunday, also 5 stars:
Code: 
Puzzle: DB020506
++++
 . 3 6  1 4 .  8 . . 
 1 . .  . . .  . . . 
 . . 8  . 3 5  9 . . 
++++
 5 . .  . . 1  . 7 . 
 8 . .  . . .  . . 6 
 . 1 .  5 . .  . . 9 
++++
 . . 5  3 1 .  6 . . 
 . . .  . . .  . . 7 
 . . 3  . 2 7  1 9 . 
++++

Both of these can be solved by assuming uniqueness. If you do not, you may have to find wings and forcing chains.
Best wishes,
Keith 

Back to top 


Marty R. Guest

Posted: Sat Feb 11, 2006 8:06 pm Post subject: 


Quote:  Both of these can be solved by assuming uniqueness. If you do not, you may have to find wings and forcing chains. 
Two newbie questions, if I may:
1) What is "uniqueness"?
2) How does one input a grid? I don't know what to type between the Code tags and I couldn't find anything in the FAQs.
Thank you. 

Back to top 


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

Posted: Sat Feb 11, 2006 10:06 pm Post subject: Two questions 


Marty,
There are some techniques which assume a puzle has a single, unique solution. For example, if you find four squares which line up as the corners of a rectangle, and the possibilities are as follows:
Code: 
AB . . ABC
. .
AB . . AB

Then the top right square must be <C>, if the puzzle is unique. If the value is not <C>, then the puzzle has multiple (or possibly zero) solutions.
You will see more when the solutions to these puzzles are posted. Also, if you search on the internet for "Sudoku Susser" you will find a very good PDF manual that explains this. Look at the sections on "Unique Rectangles" and "BUGs".
When you post a message, you can enclose a section between Code and *Code delimiters. The text within these delimiters will be displayed at a fixed pitch (typewriter font), so columns line up. Take a look at the FAQ, and you can experiment by sending messages to the "Testing" section of the forum.
Best wishes,
Keith 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Sun Feb 12, 2006 4:07 pm Post subject: BUGgy puzzle 


keith wrote:  Puzzle: DB021006 ... 
With 19 cells remaining there's a BUG pattern, with the key lying in r2c6.
Or, if one doesn't want to use uniquity, there's a "fivestar constellation" with the alpha star at r7c5. Either way works well.
Keith wrote:  DB020506 ... 
With 28 cells remaining there's a "nonunique rectangle" in r4&5, c3&4.
Or, if one doesn't want to use uniquity, there's a "fourstar constellation" on "8" with the alpha star at r4c9. dcb 

Back to top 


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

Posted: Sun Feb 12, 2006 5:29 pm Post subject: 


The puzzle can be reduced to:
Code: 
Puzzle: DB021006
++++
 4 8 2  59 1 3  6 7 59 
 3 1 6  2 79 579  8 4 59 
 7 9 5  6 4 8  23 1 23 
++++
 8 6 3  4 5 2  7 9 1 
 9 4 7  3 6 1  5 2 8 
 2 5 1  79 8 79  4 3 6 
++++
 6 7 8  1 23 4  9 5 23 
 15 2 9  57 37 6  13 8 4 
 15 3 4  8 29 59  12 6 7 
++++

The BUG square is the one with possibilities <579>. Here is an explanation:
Quote: 
In a BUG pattern, in each row, column and block, each unsolved possibility appears exactly twice. Such a pattern either has 0 or 2 solutions, so it cannot be part of a valid Sudoku.
When a puzzle contains a BUG, and only one square in the puzzle has more than 2 possibilities, the only way to kill the BUG is to remove both of the BUG possibilities from the square, thus solving it.
R2C6  remove <57> from <579> leaving <9>.

Another way to solve this is via an XYwing. Look at R1C4, then R8C4 and R2C5. One of R8C4 and R2C5 must be <7>, so R8C5 cannot be <7>, it must be <3>. The rest of the solution is simple.
Keith 

Back to top 


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

Posted: Sun Feb 12, 2006 5:54 pm Post subject: 


Quote:  There are some techniques which assume a puzle has a single, unique solution. For example, if you find four squares which line up as the corners of a rectangle, and the possibilities are as follows: 
Keith,
Thank you. I must be naive, I thought all the puzzles had a single, unique solution.
I can be dense at times, but I can't find anything in the FAQs that would help one input a puzzle grid. But I will play around with the Code tags and see if I can figure things out.
As to the "Sudoku Susser", I searched and briefly looked at the results, but I'm not sure I found the manual you had in mind. I'll look again when time permits. 

Back to top 


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

Posted: Mon Feb 13, 2006 1:35 am Post subject: The other puzzle: DB020506 


Let me discuss this one, and at least show you the Unique Rectangle solution. With standard techniques you get to:
Code: 
Puzzle: DB020506
++++
 7 3 6  1 4 9  8 5 2 
 1 5 9  268 68 268  7 34 34 
 24 24 8  7 3 5  9 6 1 
++++
 5 6 24  248 9 1  234 7 348 
 8 9 24  24 7 3  5 1 6 
 3 1 7  5 68 2468  24 48 9 
++++
 9 7 5  3 1 48  6 2 48 
 246 248 1  9 5 468  34 348 7 
 46 48 3  468 2 7  1 9 5 
++++

Now, the unique rectangle is in C1 and C2:
The basic observation is, that if the puzzle has a unique solution, it cannot contain the pattern of possibilities
So, one of the lower squares must be 6 or 8. Not very helpful (here). But, if you look at the row and block containing the lower squares, one of them must be 2. There are no other squares that have possibility 2. Therefore, neither of them can be possibility 4. So, remove 4 as possibilities in R8C1 and R8C2.
Then, after a few row/column/block interactions, you will reach the following:
Code: 
++++
 7 3 6  1 4 9  8 5 2 
 1 5 9  268 68 268  7 34 34 
 24 24 8  7 3 5  9 6 1 
++++
 5 6 24  248 9 1  23 7 38 
 8 9 24  24 7 3  5 1 6 
 3 1 7  5 68 268  24 48 9 
++++
 9 7 5  3 1 48  6 2 48 
 26 28 1  9 5 468  34 348 7 
 46 48 3  68 2 7  1 9 5 
++++

This unique rectangle is in rows 4 and 5:
and so R4C4 must be <8>. (It cannot be <24>.) This solves the puzzle.
==============
If you do not use uniqueness, you may find a forcing chain that says R4C9 is not <8>. This also solves the puzzle.
Best wishes,
Keith 

Back to top 


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

Posted: Mon Feb 13, 2006 9:01 pm Post subject: 


Thanks Keith. I've printed that out for further study. 

Back to top 


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

Posted: Tue Feb 14, 2006 12:06 am Post subject: Thank YOU! 


Quote: 
Thanks Keith. I've printed that out for further study.

Thank you, Marty. I see this as the highest compliment.
And, I hope you agree that other frequent contributors to this Forum are here to help and teach.
Keith 

Back to top 


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

Posted: Tue Feb 14, 2006 5:49 pm Post subject: 


As a relative newbie (two months), I could ask a dozen questions every day, but will try to limit myself, at least for the time being. I would like to ask if any action can be taken in the grid below. This is just one box from a puzzle and I wonder if anything can be done by looking at this box only, without considering the rest of the puzzle.
Code:  2 568 4
1367 1367 67
9 13568 68 


Back to top 


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

Posted: Wed Feb 15, 2006 12:19 am Post subject: What's in the box? 


Marty,
Let me try, and I may miss something.
Code: 
2 568 4
1367 1367 67
9 13568 68

Which possibilities only occur twice? 5.
Which possibilities only occur in one row? 7.
Which possibilities only occur in one column? 5.
So, OUTSIDE of this block, in the row which contains the 7, no other square can be 7.
OUTSIDE of this block, in the column which contains the 5's, no other square can be 5.
These are the fundamentals of row/column/block intersections.
Also, since 5 is a possibility only twice in its column, make a mental note to check for Xwings and, later, swordfish and other patterns.
Keith 

Back to top 


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

Posted: Wed Feb 15, 2006 5:56 pm Post subject: 


Thank you Keith, all excellent observations.
One of the things I wanted to know, but didn't specify, was whether anything could be done due to the fact that the pairs 13, 67 and 68 each appeared within three cells. I'm virtually certain that the answer is "no"; otherwise you would have noted it.
Thanks again. You've been very patient and helpful. 

Back to top 


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

Posted: Thu Feb 16, 2006 12:21 am Post subject: Bodycombe puzzles 


Quote:  The David Bodycombe puzzles (published locally in the Detroit Free Press) have become significantly more interesting in the past couple of weeks.
Here is the puzzle from yesterday (5 stars) 
Quote:  Both of these can be solved by assuming uniqueness. If you do not, you may have to find wings and forcing chains. 
I tried that first puzzle, knowing that I wouldn't be able to solve it. But I DID solve it, much to my surprise. When I got down to about 20 unsolved cells, I hit a brick wall. Most of the cells held pairs, a few held triples. Finally, I got it by using my firstever forcing chain.
However, it sounds like I wouldn't have needed a chain if I had "assumed uniqueness." That concept still puzzles (pun intended) me. I've been doing puzzles without assuming anything. Other than the treatment of the unique rectangles you illustrated in an earlier post, what would one do differently if he did or did not "assume uniqueness"? 

Back to top 


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

Posted: Thu Feb 16, 2006 11:52 pm Post subject: 


Marty,
Look above in this thread of posts.
David Bryant solved it by identifying a BUG, which is a technique that assumes uniqueness. He also said there is a 5star constellation, which I do not understand well enough to explain.
In the next post, I explained the BUG, and then pointed out that the puzzle can also be solved by an XYwing, which does not assume uniqueness.
In response to your previous question, the answer is, I believe you can make no inferences on the repeated possibilities in your example.
Keith 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Fri Feb 17, 2006 12:50 am Post subject: The 5star constellation 


Keith wrote:  David Bryant solved it by identifying a BUG, which is a technique that assumes uniqueness. He also said there is a 5star constellation, which I do not understand well enough to explain. 
Hi, Keith! Let me spell out the "5star constellation" in this excellent example. It's kind of cute.
Code:  Puzzle: DB021006
++++
 4 8 2  59 1 3  6 7 59 
 3 1 6  2 79 579  8 4 59 
 7 9 5  6 4 8  23 1 23 
++++
 8 6 3  4 5 2  7 9 1 
 9 4 7  3 6 1  5 2 8 
 2 5 1  79 8 79  4 3 6 
++++
 6 7 8  1 23 4  9 5 23 
 15 2 9  57 37 6  13 8 4 
 15 3 4  8 29 59  12 6 7 
++++ 
The "constellation" lies in r1c4, r2c5, r7c5, r8c5, & r8c4. We can easily infer that r7c5 = 2 by noticing that r7c5 = 3 is impossible.
 r7c5 = 3 ==> r8c5 = 7 ==> r8c4 = 5 ==> r1c4 = 9 ==> r2c5 = 7
But we can't have two "7"s in column 5, so r7c5 = 3 is impossible.
Someone_somewhere coined the term "5star constellation" for this sort of formation. Basically it's a closed loop within the puzzle involving just 5 cells that can only exist in one state. Once you spot one it's easy to analyze. The tricky part is seeing the closed loop in the first place. dcb 

Back to top 


Guest

Posted: Fri Feb 17, 2006 8:43 pm Post subject: 


It seems to me that the exclusion implied by the '5star constellation' is really an xywing (which Keith noted in his post of Feb. 12). The cell r7c5 really has nothing to do with it. The fact that r8c5 can't be a 7 because that leaves r1c4 with no candidate is the key. Assigning R7c5 = 3 to start the loop merely adds an unnecessary step to find the contradiction. Otherwise we could say it was an '8star galaxy' with r3c7, r3c9 and r7c9 as the added stars and that r3c7 can't be 2. They all lead to the fact that r8c5 can't be 7, which can be deduced from the three cell xywing.
I am not familiar with the definition and proof of a '5star constellation' so maybe the fact that an xywing makes the same exclusion in this case is merely coincidental and that in a different but similar situation the '5star constellation' could make the exclusion where something like an xywing would not work. If that is true, then I apologize in advance.
Tracy 

Back to top 


TKiel Guest

Posted: Fri Feb 17, 2006 9:08 pm Post subject: 


The above post is mine, but I forgot to login after I registered so that's why it's attributed to a guest. 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Fri Feb 17, 2006 11:58 pm Post subject: You're right, Tracy 


Tracy wrote:  It seems to me that the exclusion implied by the '5star constellation' is really an xywing ... 
You're right, Tracy. I made this particular case more complicated than it ought to be. Good catch!
The "5star constellation" is a real feature of some difficult puzzles, though. You can read more about it over here.
Here's a real example (although I guess this one's a "sixstar constellation") from a very tough puzzle I'm working on currently.
Code:  236 59 23 8 129 7 159 156 4
1 47 24 6 29 5 79 3 8
67 8 59 3 19 4 2 156 179
259 6 7 1 4 3 59 8 29
59 15 8 7 6 2 13459 45* 139
24 3 124 5 8 9 6 7 12
3457 145 6 2 357 8 14 9 37
347 2 134 9 37 6 8 14 5
8 579 59 4 35 1 37 2 6 
We start from r5c8, marked with an asterisk. We can show that r5c1 = 9, as follows.
A. r5c8 = 5 ==> r5c1 = 9
B. r5c8 = 4 ==> r8c8 = 1 ==> r7c7 <> 1 ==> r7c2 = 1 ==> r5c2 = 5 ==> r5c1 = 9
In short, r5c8 must contain either a "4" or a "5", and no matter which value goes there, r5c1 must be a "9". Unfortunately, that isn't enough to solve this particular puzzle. Suggestions are welcome! dcb 

Back to top 


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

Posted: Sun Feb 19, 2006 5:32 am Post subject: 


keith wrote:  The puzzle can be reduced to:
Code: 
Puzzle: DB021006
++++
 4 8 2  59 1 3  6 7 59 
 3 1 6  2 79 579  8 4 59 
 7 9 5  6 4 8  23 1 23 
++++
 8 6 3  4 5 2  7 9 1 
 9 4 7  3 6 1  5 2 8 
 2 5 1  79 8 79  4 3 6 
++++
 6 7 8  1 23 4  9 5 23 
 15 2 9  57 37 6  13 8 4 
 15 3 4  8 29 59  12 6 7 
++++

The BUG square is the one with possibilities <579>. Here is an explanation:
Quote: 
In a BUG pattern, in each row, column and block, each unsolved possibility appears exactly twice. Such a pattern either has 0 or 2 solutions, so it cannot be part of a valid Sudoku.
When a puzzle contains a BUG, and only one square in the puzzle has more than 2 possibilities, the only way to kill the BUG is to remove both of the BUG possibilities from the square, thus solving it.
R2C6  remove <57> from <579> leaving <9>.

Another way to solve this is via an XYwing. Look at R1C4, then R8C4 and R2C5. One of R8C4 and R2C5 must be <7>, so R8C5 cannot be <7>, it must be <3>. The rest of the solution is simple.
Keith 
Keith (or anyone),
I'm having a problem understanding the BUG pattern. It says "In a BUG pattern, in each row, column and block, each unsolved possibility appears exactly twice."
Then, "When a puzzle contains a BUG, and only one square in the puzzle has more than 2 possibilities, the only way to kill the BUG is to remove both of the BUG possibilities from the square, thus solving it.
R2C6  remove <57> from <579> leaving <9>."
So we're "killing" something where two of the possibilities (5 & 7) occur twice and one thrice (9), even though it says in a BUG pattern each unsolved possibility appears exactly twice. I'm confused.
But regardless of my understanding, are we saying that when we have in one row, column or box the pattern XYYZXYZ and no other cells have more than two possibilities, then we can remove XZ from the XYZ cell?
Somehow, I think it must be more complicated than that, but I've looked at that many times and must be missing something.
And finally, just curious, it appears that BUG is an acronym. What does it stand for? 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Sun Feb 19, 2006 1:24 pm Post subject: Killing BUGS 


Hi, Marty! Let me take a stab at explaining this.
First, BUG stands for "bivalue universal grave," which is sort of meaningless ... I think someone cooked it up just to get the cute acronym. The idea is an extension of the more familiar "nonunique rectangle"  it (a BUG) is any pattern of unresolved cells that can be completed in more than one way.
Let's think about Keith's example above. If the possibilities at r2c6 were {5, 7} then the pattern of unresolved cells _for the whole puzzle_ would be a "BUG". We would either be able to complete it two different ways, or else we couldn't complete it (consistently) at all.
So the only way the pattern can define a unique solution is if r2c6 contains a "9". dcb
PS The "BUG" pattern doesn't just exist in a single row, or column. It exists throughout the entire puzzle. The ones I've run into occupied somewhere between 15 and 30 cells, roughly. 

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
