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 "5 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: Mon Nov 28, 2005 8:27 pm    Post subject: A "5 Star Constellation" example Reply with quote

Here's a puzzle I got from HollyDoll.
Code:
... ... .73
4.8 ... ...
.31 45. ...

..7 ... 298
..5 2.7 3..
924 ... 6..

... .13 96.
... ... 7.5
84. ... ...

After 32 moves you'll need to locate a "5 Star Constellation" to crack it. Enjoy! dcb

PS I looked it over again, and you can also solve it using "colors." But the "5 Star Constellation" is there, and fun to look for.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
alanr555



Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39

PostPosted: Tue Nov 29, 2005 3:06 pm    Post subject: Reply with quote

Code:

This one seemed like a breeze. More and more Mandatory Pairs
came to light and cells resolved very easily - until I reached the
following position.

250 000 473
408 002 510
731 450 820

317 040 298
685 297 341
924 000 657

572 813 964
103 024 785
840 000 132

leaving 21 to go.

Rather than persevering with m/Pairs, I heeded the warning
that something interesting could be about to happen and so
moved to setting the candidate profiles. Column 6 and Row 2
needed normalising in terms of splitting the "Missing" profile.
Col 6 has (18) and (569) whilst row 2 has (37) and (69).

Overall inspection revealed that column 5 has a similar profile
to that identified in an earlier post on "Inferential Chains".

It has eight candidate occurrences in four cells - implying two
occurrences of each digit and two binary links from each cell.
This column looked good to contain the end point of the two
inferential chains that I was seeking - but where to start.

An inferential chain is one linking two cells where the end cell
must have the SAME value irrespective of the value of the
cell at the other end of the chain.

Experience suggests that this can be achieved only by making
use of the one-way link whereby a positive value X in one cell
implies 'not-X' for everywhere else X is a candidate, whereas
the converse is not true (a cell being not-X does NOT imply
value X in another cell - unless there are only TWO cells
containing X).

Thus row 1 seems to be interesting with 1,8,9 having binary links
but value 6 having the potential of a one-way link.

Thus, I guessed that r1c3 and r1c5 might be possible points for
the start and end of the inferential chain - and so it proved.

Starting from r1c5

r1c5=6
r1c3=9 (very short chain!)

r1c5=8 implies (not-6) but this still leaves two possibilities
for the cell in row 1 where the 6 must be located and so is no use
to us in terms of forming an inferential chain. Thus:- another route!

r1c5=8
r9c5=6
r9c4=7
r9c6=5
r4c6=6
r3c6=9
r3c9=6
r2c9=9
r2c2=6
r1c3=9

This (long!) chain was found visually by writing out the candidate
profiles and tracing the path using binary links. The latter part
is a trail of 6-9 alternations and so while seemingly complex is
really just the expansion of a simple logical thought. The real
work was making the connection from column 5 to the "right"
cell in the 6-9 chain so that one arrives at the end with value '9'
rather than with value '6'.

Now that the two chains have been identified, it is clear that r1c3
MUST take the value 9. This is a POSITIVE result and so does not
depend on the "allocate until contradicted" method.

Using r1c3=9 as a resolved cell, the remainder of the puzzle falls
into place to give the final solution.

Sadly it can take some time to find the two chains involved but
experience is bringing us some clues as to the more promising
places to look. Hopefully our prescience will improve over time
and these chains will start staring out at the less myopic among us.

Alan Rayner  BS23 2QT
Back to top
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Tue Nov 29, 2005 3:30 pm    Post subject: Reply with quote

Hi,

For me a combination of the techniques:
- Hidden Pair (in Column)
- X-Wing (on Row) and
- XY-Wing
was enough to crack it.

I am almost sure that I got to the same position as David.
And from here, it can be done, like this:

Code:

 6 not in r1c6, Hidden Pair 1 8 in r1c6 and r6c6 (in Column)
 9 not in r1c6, Hidden Pair 1 8 in r1c6 and r6c6 (in Column)
 6 not in r1c4, it is in r1c3 r9c3 r1c5 r9c5 (X-Wing on Row)
 6 not in r9c4, it is in r1c3 r9c3 r1c5 r9c5 (X-Wing on Row)
 6 not in r9c6, it is in r1c3 r9c3 r1c5 r9c5 (X-Wing on Row)
 5 not in r4c6, XY-Wing X=6 Y=9 in r8c4 X=6 Z=5 in r4c4 Y=9 Z=5 in r9c6
 6 in r4c6  - Sole Candidate ...


Of course, nothing against a "5 stars constellation" ...
Or against finding the "chains" ...

There was a saying: "All roads are leading to Rome ...".
The empire falled apart, but the saying is still valid.

see u,
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Tue Nov 29, 2005 6:43 pm    Post subject: I overlooked the "X-Wing" Reply with quote

I could kick myself -- I totally overlooked the "X-Wing" pattern in columns 3 & 5 ... with that, the "XY-Wing" pattern is relatively easy to spot. Good catch, someone!

Anyway, here's the "5 Star Constellation" I was talking about. Without noticing the X-Wing on "6" I had arrived at the following candidate table.
Code:
  2    5   6/9   1/6/9   6/8   1/8    4    7    3
  4   6/9   8     3/7    3/7    2     5    1   6/9
  7    3    1      4      5    6/9    8    2   6/9

  3    1    7     5/6     4    5/6    2    9    8
  6    8    5      2      9     7     3    4    1
  9    2    4     1/3    3/8   1/8    6    5    7

  5    7    2      8      1     3     9    6    4
  1   6/9   3     6/9     2     4     7    8    5
  8    4   6/9  5/6/7/9  6/7  5/6/9   1    3    2

The "Constellation" is in r8c4 (the "alpha star"), r4c4, r9c6, r4c6, and r3c6. One chain leads from r8c4 through r4c4 and r4c6 to r3c6 -- if r8c4 = 6 then r4c4 = 5, r4c6 = 6, and r3c6 = 9. The other chain leads from r8c4 through r9c6 & r4c6 to r3c6 -- if r8c4 = 9 then we have the {5, 6} pair in r4c6 & r9c6, so that r3c6 = 9 once again.

Interestingly, I found that I could also apply the "single chain" method starting from r8c4 -- assuming that r8c4 = 9 I deduce that r3c6 = 9 via r9c6 & r4c6, as before. But then there's a chain of {6, 9} pairs leading around the puzzle (r3c9, r2c9, r2c2, r8c2) that forces a contradiction, because it forces r8c2 = 9 (can't have two "9"s in the same row). 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: Wed Nov 30, 2005 8:26 am    Post subject: Reply with quote

Hi,

I am starting for an alpha star that has 2 digits.
This idea is important, because it gives me a good probability that I will get to a contradiction. In this case I could eliminate (maybe) a digit of this star and mark as sure/fixed the other.
I could also get to a contradiction that would eliminate one digit from an other star (cell). And if I am lucky, this elimination would be an "important one" meaning that a digit can be found and set in the table.
The less lucky possibility is to find an contradiction and eliminate a digit which is not so relevant. Or not to find a contradiction at all.

If I would start from a cell with more than 2 digits, the above described probabilities would be smaller.

My problem now is what to do when there are no pairs or only a small numbers of pairs in the table. And I have a few such examples.
I am trying to think about what I call "entropic algorithm".
Any suggestions are welcomed.

P.S. I can supply some example that the techniques that starts from a pair and is looking for a "n" stars constellation is now working.

see u,
Back to top
View user's profile Send private message
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