| View previous topic :: View next topic |
| Author |
Message |
keith
Joined: 19 Sep 2005
Posts: 3355
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: 3355
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 xx (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 "five-star constellation" with the alpha star at r7c5. Either way works well.
| Keith wrote: | | DB020506 ... |
With 28 cells remaining there's a "non-unique rectangle" in r4&5, c3&4.
Or, if one doesn't want to use uniquity, there's a "four-star constellation" on "8" with the alpha star at r4c9. dcb |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
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 XY-wing. 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: 5770
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: 3355
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: 5770
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: 3355
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: 5770
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: 3355
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 X-wings and, later, swordfish and other patterns.
Keith |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
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: 5770
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 first-ever 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: 3355
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 5-star 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 XY-wing, 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 5-star constellation |
|
|
| Keith wrote: | | David Bryant solved it by identifying a BUG, which is a technique that assumes uniqueness. He also said there is a 5-star constellation, which I do not understand well enough to explain. |
Hi, Keith! Let me spell out the "5-star 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 "5-star 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 '5-star constellation' is really an xy-wing (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 '8-star 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 xy-wing.
I am not familiar with the definition and proof of a '5-star constellation' so maybe the fact that an xy-wing makes the same exclusion in this case is merely coincidental and that in a different but similar situation the '5-star constellation' could make the exclusion where something like an xy-wing 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 log-in 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 '5-star constellation' is really an xy-wing ... |
You're right, Tracy. I made this particular case more complicated than it ought to be. Good catch!
The "5-star 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 "six-star 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: 5770
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 XY-wing. 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 XY-YZ-XYZ 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 "non-unique 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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
