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 "4-star constellation" example

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
David Bryant



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

PostPosted: Sun Feb 19, 2006 4:20 pm    Post subject: A "4-star constellation" example Reply with quote

Here's a pretty good example of a "4-star constellation." This is from the David Bodycombe puzzle for Saturday, Feb 18, rated six stars.

After doing the obvious stuff I arrived at this position.
Code:
 36     7     4     5    38    136   18     2     9
  9     8    356   16     7     2    145   134   36
  2    35     1     9    348   346   458    7    368
 368   34    36     2     5    16     9    134    7
  7     1     9     8    34    34     6     5     2
3568   345    2    16     9     7    148   134   38
 35     6    35     7     1     9     2     8     4
  4     2     8     3     6     5     7     9     1
  1     9     7     4     2     8     3     6     5

Notice that the "6" in row 6 must either occur at r6c1 or at r6c4. Suppose that r6c1 = 6. Then we have a nice double-implication chain, or "4-star constellation":

A. r6c1 = 6 ==> r6c4 = 1
B. r6c1 = 6 ==> r2c3 = 6 ==> r2c4 = 1

Since we can't have two "1"s in column 4 the "6" can't go at r6c1, and we must have r6c4 = 6. This isn't enough to break the puzzle wide open, but it will allow one to make quite a bit of progress, leading to an easily resolved "BUG" pattern. dcb

PS There's more than one way to look at this pattern. For instance, consider this chain of reasoning:

r6c1 = 6 ==> r6c4 = 1 ==> r2c4 = 6 ==> {3, 5} pair in column 3 ==> r4c3 = 6

and now we have two "6"s in the middle left 3x3 box. I've noticed this in a lot of Sudoku puzzles -- with a chain like this there are usually two or three different ways to "see" the contradiction.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



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

PostPosted: Mon Feb 20, 2006 2:40 am    Post subject: Bodycombe Puzzles Reply with quote

This Saturday puzzle is very similar to the Friday puzzle I posted previously. The starting point is:

Code:


Puzzle: DB021806
+-------+-------+-------+
| . . 4 | 5 . . | . . 9 |
| . 8 . | . 7 2 | . . . |
| 2 . 1 | 9 . . | . 7 . |
+-------+-------+-------+
| . . . | 2 5 . | 9 . . |
| . 1 9 | . . . | 6 5 . |
| . . 2 | . 9 7 | . . . |
+-------+-------+-------+
| . 6 . | . . 9 | 2 . 4 |
| . . . | 3 6 . | . 9 . |
| 1 . . | . . 8 | 3 . . |
+-------+-------+-------+



In the position given by David, may I point out the Unique rectangle in C5 and C6? It is

Code:


348  346

34   34



The argument goes as follows: The pattern of possibilities

34 34

34 34

does not allow a unique solution. However, one of the squares in R3 must be <4>, for there are no other possible values <4> in their block. Therefore neither R3C5 or R3C6 can be <3>.

More to come,

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



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

PostPosted: Mon Feb 20, 2006 2:51 am    Post subject: Reply with quote

The Sunday David Bodycombe puzzle is hidden in the TV book that comes with the Sunday newspaper (in my case, the Detroit Free Press). Like the Friday puzzle, it has become much more interesting and challenging in the last few weeks. Here is today's puzzle (which is rated 5 stars):

Code:


Puzzle: DB021906
+-------+-------+-------+
| 3 . . | . . . | 6 7 . |
| . 5 . | 6 . . | 9 3 . |
| . . . | 5 7 . | . . 4 |
+-------+-------+-------+
| . . . | 9 . 4 | . . . |
| . . 6 | . . . | 8 . . |
| . . . | 3 . 7 | . . . |
+-------+-------+-------+
| 8 . . | . 9 6 | . . . |
| . 6 4 | . . 5 | . 2 . |
| . 1 3 | . . . | . . 6 |
+-------+-------+-------+



The only clue I'll give, for now, is that there is a very good reason I have posted this puzzle in this thread!!

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: Mon Feb 20, 2006 4:21 pm    Post subject: DB021806 again Reply with quote

Thanks for the Sunday puzzle, Keith. I only get these in the paper on Saturdays.

On the Saturday puzzle, there's also a nice "coloring" solution available. To get to this (slightly different) position one must recognize that the "8" in r4c1 is unique in row 4 (starting from the position posted previously).
Code:
 36+    7     4     5    38    136-  18     2     9
  9     8    356   16     7     2    145   134   36
  2    35     1     9    348   346   458    7    368
  8    34    36=    2     5    16~    9    134    7
  7     1     9     8    34    34     6     5     2
 356   345    2    16     9     7    148   134   38
 35     6    35     7     1     9     2     8     4
  4     2     8     3     6     5     7     9     1
  1     9     7     4     2     8     3     6     5

There are only two ways to place a "6" in rows 1 & 4.

r1c6 = 6 ==> r4c6 <> 6 ==> r4c3 = 6
r1c6 <> 6 ==> r1c1 = 6

So either r1c1 = 6, or else r4c3 = 6 ... either way there cannot be a "6" at r2c3. So the "6" in column 3 must appear at r4c3 -- this is essentially the same conclusion forced by the "4-star constellation" in my previous post. dcb

PS The "BUG" pattern that eventually emerges from this puzzle can also be resolved by "coloring" on the digit "3".
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Steve R



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

PostPosted: Mon Feb 20, 2006 6:21 pm    Post subject: Cloudy Skies Reply with quote

If I remember correctly someone_somwhere’s four-star constellation took the form of a rectangle containing four cells:


…..XY…………..XZetc…
………………………….......
…..Yetc………..YZetc…
………………………….......

with only two places for Y in the bottom row and only two places for Z in the right hand column. The alpha star (top left) admits only two possibilities, X and Y. X can then be eliminated from the cell containing XZetc.

I can’t spot this pattern in David’s example of yesterday, 19 February, which started this thread. Perhaps I am looking in the wrong part of the sky. Perhaps the constellation has developed beyond its original form. If the latter, would it not be better to qualify the term “four-star constellation” when using the development so as to minimise confusion?

Steve
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Mon Feb 20, 2006 10:50 pm    Post subject: What's in a name? Reply with quote

Steve R wrote:
I can’t spot this pattern in David’s example of yesterday, 19 February, which started this thread.

Well, I'm not real sure myself, Steve. Smile

Someone_somewhere wrote:
Here the definition of a "4 stars constellation" similar to the "5 ...":

1. it involves 4 stars (meaning 4 cells)
2. it has 2 starting digits, in the so called starting cell. We always find this alpha star, the bright one to start with.
3. we follow 2 chains, or pathes, to other stars/cells, forcing a digit TO BE or NOT TO BE in this cell.
4. the overall result is a chain of 4 stars, with an ending in some result, as to set or exclude a digit in one of the stars, or a contradiction.

I guess, to comply with #2, I should start the argument from r6c4:

A. r6c4 = 1 ==> r2c4 = 6 ==> r4c3 = 6
B. r6c4 = 1 ==> r6c1 = 6

So there I have the chains involving four cells and ending in a contradiction. It sort of looks like what s_s was talking about , to me. But hey, a rose by any other name would smell as sweet.

BTW, where is someone_somewhere, anyway? We haven't heard from him in quite a while. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



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

PostPosted: Mon Feb 20, 2006 11:39 pm    Post subject: What pattern is this? Reply with quote

I have found this pattern only once or twice:

Code:


AB .  .  .  AC
.  .  .  .  .
.  .  .  .  .
BD .  .  .  CD



Values in other squares do not matter. If the top left square is A, follow a clockwise cycle to give

Code:


A .  .  .  C
. .  .  .  .
. .  .  .  .
B .  .  .  D



If the top left square is B, follow a counter-clockwise cycle to give

Code:


B .  .  .  A
. .  .  .  .
. .  .  .  .
D .  .  .  C



Either way, you can eliminate all other possibilities of A in the top row, C in the right column, D in the bottom row, and B in the left column.

These situations can involve more than four squares. Personally, I have been calling them "bidirectional cycles", where "cycle" is a closed chain. If you find one, the situation is similar to an X-wing, where one of two adjacent "corners" must be some particular value.

You can try to find one of these in the Sunday puzzle posted above! (It has 5 squares.)

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



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

PostPosted: Tue Feb 21, 2006 5:39 pm    Post subject: What's in a name? Reply with quote

David

Thanks for the response. I had forgotten the wise words you quote from someone_somewhere, taking them as a general description of what was going on rather than a definition. Perhaps he will say more when he surfaces again.

By coincidence both approaches crop up at the same position in the six stars puzzle you posted on Friday, 17th.

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


As well as the widely defined variety of constellation which you used to put 9 in r5c1, there is a narrowly defined one with alpha star r5c2, using only two 1s in row 7 and only two 4s in column 7. This narrow version eliminates 5 from r5c7.

Making both these moves gives a (finned) X-wing for 5 in rows 1 and 5. So r3c9 is not 5 and the only place for 5 in row 3 is r3c3.

The solution of the puzzle is then relatively straightforward, with the emphasis on “relatively.”

Steve
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Fri Mar 03, 2006 4:36 pm    Post subject: Another "5 Star Constellation" example Reply with quote

Here's a good example of a "5-star constellation." This is the "Nightmare" puzzle for Friday, 3 March, 2006.
Code:
. 1 . . . . . 7 4
. 5 . . 8 . 3 . .
2 . . . . 9 . . .
. . 6 5 . . . . .
7 4 . . 1 . . 3 8
. . . . . 4 1 . .
. . . 2 . . . . 3
. . 4 . 7 . . 8 .
6 3 . . . . . 9 .

After resolving 18 cells and making a few eliminations via simple coloring I found a "5-Star Constellation" that allowed me to set the value at r6c8. The rest of the puzzle was duck soup. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Fri Mar 03, 2006 9:14 pm    Post subject: Reply with quote

Quote:
After doing the obvious stuff I arrived at this position.
Code:

 36     7     4     5    38    136   18     2     9
  9     8    356   16     7     2    145   134   36
  2    35     1     9    348   346   458    7    368
 368   34    36     2     5    16     9    134    7
  7     1     9     8    34    34     6     5     2
3568   345    2    16     9     7    148   134   38
 35     6    35     7     1     9     2     8     4
  4     2     8     3     6     5     7     9     1
  1     9     7     4     2     8     3     6     5


Notice that the "6" in row 6 must either occur at r6c1 or at r6c4. Suppose that r6c1 = 6. Then we have a nice double-implication chain, or "4-star constellation":

A. r6c1 = 6 ==> r6c4 = 1
B. r6c1 = 6 ==> r2c3 = 6 ==> r2c4 = 1


David (or anyone),

Forgive me, but I just can't understand "B", above. How does one get to r2c3 being a "6"? It seems to me that it has to be a "5" because the "6" in r6c1 forces a "3" in r1c1 and a "1" in r6c4, which forces a "6" in r2c4, thus leaving a "5" as the only choice for r2c3. I'm obviously missing something here. Question
Back to top
View user's profile Send private message
keith



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

PostPosted: Fri Mar 03, 2006 11:41 pm    Post subject: Reply with quote

Marty,

I agree with you. David must have mistyped something. However, his conclusion is valid:

R6C1 = 6 ==> R1C1 = 3 and R4C3 = 3 ==> R7C1 = R7C3 = 5.

The mystery to me is how you decide to test the value <6> in R6C1?

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



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

PostPosted: Sat Mar 04, 2006 12:56 am    Post subject: "Constellations" are mysterious ... Reply with quote

Marty R wrote:
David (or anyone),

Forgive me, but I just can't understand "B", above. How does one get to r2c3 being a "6"? It seems to me that it has to be a "5" because the "6" in r6c1 forces a "3" in r1c1 and a "1" in r6c4, which forces a "6" in r2c4, thus leaving a "5" as the only choice for r2c3. I'm obviously missing something here.

Hi, Marty! Thanks for asking the question. It's a good one.

The really interesting thing about the "n-star constellations" or "double-implication chains" is that they depend on both positional logic and on value-oriented logic.

In the case you're asking about, I've used positional logic.
Code:
 36     7     4     5    38    136   18     2     9
  9     8    356   16     7     2    145   134   36
  2    35     1     9    348   346   458    7    368
 368   34    36     2     5    16     9    134    7
  7     1     9     8    34    34     6     5     2
3568   345    2    16     9     7    148   134   38
 35     6    35     7     1     9     2     8     4
  4     2     8     3     6     5     7     9     1
  1     9     7     4     2     8     3     6     5

-- There has to be a "6" in the top left 3x3 box somewhere.
-- Only two slots are open for a "6" in that 3x3 box -- at r1c1 & at r2c3.
-- If r6c1 = 6 there can't be a "6" at r1c1, so then there would have to be a "6" at r2c3.

I abbreviated this logic by writing "r6c1 = 6 ==> r2c3 = 6" ... I thought that would be clear enough, but I'm happy to provide this clarification. The notion of "positional logic" took me a little while to catch onto.

You'll notice also that this "positional logic" conclusion is at variance with the result you obtained using "value-oriented logic." That's not very surprising, since I was reasoning toward a contradiction. In other words, one might just as well argue that assuming "r5c1 = 6" forces one to place two different values at r2c3 -- a "5" using value-oriented logic around the loop r6c1 - r6c4 - r2c4, and a "6" by tracing a different path, from r6c1 - r1c1 - r3c2 - r2c3. It's all the same -- a contradiction is a contradiction. Either approach yields the result r6c1 <> 6.

Keith wrote:
I agree with you. David must have mistyped something. However, his conclusion is valid:

R6C1 = 6 ==> R1C1 = 3 and R4C3 = 3 ==> R7C1 = R7C3 = 5.y

The mystery to me is how you decide to test the value <6> in R6C1?

I don't think I mistyped anything, Keith -- please see the reply to Marty R, above.

Once you've spotted a "constellation" you can usually start arguing from any point inside it. The conclusion "r6c1 <> 6" is what caught my eye, so I started the argument from that cell. Perhaps the {1, 6} pair in column 4 is a more natural place to start.

-- There has to be a "6" in column 4 somewhere.
-- Since there are only two spots for a "6" in column 3, we can conclude that if r2c4 = 6, then r4c3 = 6. But then r6c1 <> 6, because there can't be two "6"s in the middle left 3x3 box.
-- If r6c4 = 6 the conclusion r6c1 <> 6 is immediate, because there can't be two "6"s in row 6.

Viewed from this perspective we can see this "4-star constellation" as an exercise in multi-coloring.
Code:
 36     7     4     5    38    136   18     2     9
  9     8    356+  16=    7     2    145   134   36
  2    35     1     9    348   346   458    7    368
 368   34    36-    2     5    16     9    134    7
  7     1     9     8    34    34     6     5     2
3568   345    2    16~    9     7    148   134   38
 35     6    35     7     1     9     2     8     4
  4     2     8     3     6     5     7     9     1
  1     9     7     4     2     8     3     6     5

That's another cute thing about the "constellations" -- sometimes they can be analyzed as two sets of binary chains involving a single digit. Other times they involve more than one digit, and can't be worked out in terms of simple coloring. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Sat Mar 04, 2006 4:07 pm    Post subject: someone_somewhere is still alive Reply with quote

Sorry for not beeing active in this forum for a longer time ...
I am active now in a project in UK where I have similar excitement as solving the "almost imposible" Sudoku's.
In the airport, I noticed a lot of small Sudoku books ... thinking not to buy one, in order not to be dissapointed if the games are to easy.
Maybe I will get a couple of "Nightmaire" from Sudo Cue or "Super Tough" from Krazydad because the planes started having delays as soon as the first snow storm is approching.
Not sure if from the airport I can see the 4 and 5 star constellation.
On the weekend I take a look here and note that everthing is on the right way. People are solving and enjoying.
BTY, I have keep one or two Sudoku's from the minimal 17, that I have found out to be as difficult for human, as beeing from an different galaxy. The 4, 5, etc stars all all in our galaxy. The solving of this particular ones, means looking far outside the stars of our galaxy.
If you got not tired, reading so many words (less than what Alan's Wink
and are still interested, please ask David, whom I will send the exceptional ones that I have found.
see u,
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sat Mar 04, 2006 6:40 pm    Post subject: Reply with quote

Quote:
-- There has to be a "6" in the top left 3x3 box somewhere.
-- Only two slots are open for a "6" in that 3x3 box -- at r1c1 & at r2c3.
-- If r6c1 = 6 there can't be a "6" at r1c1, so then there would have to be a "6" at r2c3.

I abbreviated this logic by writing "r6c1 = 6 ==> r2c3 = 6" ... I thought that would be clear enough, but I'm happy to provide this clarification. The notion of "positional logic" took me a little while to catch onto.

You'll notice also that this "positional logic" conclusion is at variance with the result you obtained using "value-oriented logic." That's not very surprising, since I was reasoning toward a contradiction. In other words, one might just as well argue that assuming "r5c1 = 6" forces one to place two different values at r2c3 -- a "5" using value-oriented logic around the loop r6c1 - r6c4 - r2c4, and a "6" by tracing a different path, from r6c1 - r1c1 - r3c2 - r2c3. It's all the same -- a contradiction is a contradiction. Either approach yields the result r6c1 <> 6.


Thank you for the explanation. I can see that either your positional or my value-oriented leads to different contradictions which both result in precluding a "6" in r6c1.

However, I don't know how I could have known that "r6c1=6==>r2c3=6" equated to the logic described above it.

Being a newbie to a sudoku forum, I'd like to ask if the notation you use is considered standard on forums, i.e., "==>" representing an arrow and "<>" meaning unequal.
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Sat Mar 04, 2006 7:14 pm    Post subject: "Standards" for notation Reply with quote

Marty R wrote:
Being a newbie to a sudoku forum, I'd like to ask if the notation you use is considered standard on forums, i.e., "==>" representing an arrow and "<>" meaning unequal.

I don't know if it's "standard" for fora, or not, Marty. I'm not even sure that any such "standards" exist.

By "==>" I intend to represent an implication arrow, which is a more or less standard symbol in most textbooks on mathematics and/or symbolic logic. So

A ==> B

means "if A, then B," and

A <==> B

means "A, if and only if B" (or "A and B are logically equivalent").

I learned to use this notational shortcut about 30 years ago, when there was a lot less control over computer-generated fonts than there is today. Old habits die hard.

For the other trick, "<>" meaning "is not equal to," I can actually claim a meaningful, or semi-official, precedent. This is the notation used in C (a widely used computer language) and also in JavaScript (a widely used scripting language for internet browsers). So I would expect most computer programmers, at least, to recognize what "<>" stands for. dcb
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
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