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 

Two More Puzzles
Goto page 1, 2  Next
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
keith



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

PostPosted: Sat Feb 11, 2006 3:54 pm    Post subject: Two More Puzzles Reply with 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)

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
View user's profile Send private message
Marty R.
Guest





PostPosted: Sat Feb 11, 2006 8:06 pm    Post subject: Reply with quote

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

PostPosted: Sat Feb 11, 2006 10:06 pm    Post subject: Two questions Reply with quote

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
View user's profile Send private message
David Bryant



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

PostPosted: Sun Feb 12, 2006 4:07 pm    Post subject: BUGgy puzzle Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
keith



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

PostPosted: Sun Feb 12, 2006 5:29 pm    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Sun Feb 12, 2006 5:54 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



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

PostPosted: Mon Feb 13, 2006 1:35 am    Post subject: The other puzzle: DB020506 Reply with quote

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:

Code:


24   24
.    .
246  248



The basic observation is, that if the puzzle has a unique solution, it cannot contain the pattern of possibilities

Code:


24  24
.   .
24  24



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:

Code:


24  248
24  24



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
View user's profile Send private message
Marty R.



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

PostPosted: Mon Feb 13, 2006 9:01 pm    Post subject: Reply with quote

Thanks Keith. I've printed that out for further study.
Back to top
View user's profile Send private message
keith



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

PostPosted: Tue Feb 14, 2006 12:06 am    Post subject: Thank YOU! Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Tue Feb 14, 2006 5:49 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



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

PostPosted: Wed Feb 15, 2006 12:19 am    Post subject: What's in the box? Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Wed Feb 15, 2006 5:56 pm    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Thu Feb 16, 2006 12:21 am    Post subject: Bodycombe puzzles Reply with quote

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
View user's profile Send private message
keith



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

PostPosted: Thu Feb 16, 2006 11:52 pm    Post subject: Reply with quote

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
View user's profile Send private message
David Bryant



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

PostPosted: Fri Feb 17, 2006 12:50 am    Post subject: The 5-star constellation Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Guest






PostPosted: Fri Feb 17, 2006 8:43 pm    Post subject: Reply with quote

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





PostPosted: Fri Feb 17, 2006 9:08 pm    Post subject: Reply with quote

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

PostPosted: Fri Feb 17, 2006 11:58 pm    Post subject: You're right, Tracy Reply with quote

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 Smile
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Sun Feb 19, 2006 5:32 am    Post subject: Reply with quote

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
View user's profile Send private message
David Bryant



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

PostPosted: Sun Feb 19, 2006 1:24 pm    Post subject: Killing BUGS Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
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