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 

Freep Oct 19

 
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: 3355
Location: near Detroit, Michigan, USA

PostPosted: Sun Oct 21, 2007 1:59 pm    Post subject: Freep Oct 19 Reply with quote

This one is worthy of attention, if you like them a little harder than "Very Hard".
Code:
Puzzle: FP101907
+-------+-------+-------+
| . 3 . | . 1 . | . 8 6 |
| . . 7 | . . . | 5 . . |
| 4 . . | . . . | . . 2 |
+-------+-------+-------+
| . . . | 2 . 9 | 6 . 8 |
| . 6 . | . 3 . | . 9 . |
| 7 . 5 | 1 . 8 | . . . |
+-------+-------+-------+
| 8 . . | . . . | . . 4 |
| . . 9 | . . . | 2 . . |
| 5 2 . | . 4 . | . 6 . |
+-------+-------+-------+


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



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Sun Oct 21, 2007 7:09 pm    Post subject: Reply with quote

I used the {45} UR to get rid of the <5>s in R5C46, followed by a Skyscraper on <9> in C57.
Back to top
View user's profile Send private message Visit poster's website
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Sun Oct 21, 2007 7:53 pm    Post subject: Reply with quote

Without the UR, this is as far as I got:
Code:

+--------------------------+--------------------------+--------------------------+
| 9       3       2        | 45      1       45       | 7       8       6        |
| 16      8       7        | 39      29      236      | 5       4       19       |
| 4       5       16       | 678     789     67       | 39      13      2        |
+--------------------------+--------------------------+--------------------------+
| 3       1       4        | 2       57      9        | 6       57      8        |
| 2       6       8        | 457     3       457      | 1       9       57       |
| 7       9       5        | 1       6       8        | 4       2       3        |
+--------------------------+--------------------------+--------------------------+
| 8       7       16       | 569     259     25       | 39      13      4        |
| 16      4       9        | 3678    78      367      | 2       57      157      |
| 5       2       3        | 79      4       1        | 8       6       79       |
+--------------------------+--------------------------+--------------------------+


... and that invoved some rather extreme coloring, too.

Tough nut.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Sun Oct 21, 2007 8:35 pm    Post subject: Reply with quote

nataraj,

One way to crack that nut is with an XY Chain with a twist. Start at R9C4 and note that if it is <7> then there is a {45} pair in C4 making R7C4 a {69} bivalue. We will exploit that in the chain:

(9=7)R9C4-(7=9)R9C9-(9=1)R2C9-(1=6)R2C1-(6=1)R3C3-(1=6)R7C3-(6=9)R7C4

<9> is eliminated from R7C5 and from R2C4.

After that, some more XY Chains solve the puzzle.

This example illustrates something I often find useful on really tough puzzles: exploiting an ALS that can provide a locked set in chaining.
Back to top
View user's profile Send private message Visit poster's website
Marty R.



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

PostPosted: Sun Oct 21, 2007 11:47 pm    Post subject: Reply with quote

Keith, is "Freep" a Keith creation? Very Happy

I used a Type 2 rectangle and three Finned X-Wings.
Back to top
View user's profile Send private message
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Mon Oct 22, 2007 6:54 am    Post subject: Reply with quote

Thanks, Asellus, for the "nutcracker". I couldn't log onto this site earlier so I tried some more coloring (starting from those "1"s in r2 and c9 and came up with a contradiction (color wrap) that made r2c9=1. The contradiction comes from assuming r2c9=9

a1) r2c9=9 => r2c5=2 => r7c5 not 2.
a2) r2c9=9 => r9c9=7 => r9c4=9 => r7c5 not 9

=> a) r2c9=9 => r7c5 = 5

but ...

b) r2c9=9 => r9c9=7 => r5c9=5 => r5c46 not 5 => r4c5=5

it is not possible that both r7c5 and r4c5 are 5, therefore r2c9=1

After that I did not encounter any more chains ... the puzzle solved easily
I will have a longer look into your technique of using an ALS in a chain because I feel this method could be useful quite often Smile

Thx

edit 1403 GMT: "color wrap" is definitely wrong. Since I used different numbers in the chain it should probably be called Medusa wrap, plus I'm not even sure if it is really a wrap or rather a trap. Someday there will be a standard textbook on all this terminology ...

edit 1949 GMT:
come to think of it, probably even Medusa is incorrect, since the elimination is not based on strong links alone, but uses weak links or even branched AICs.
In this case it is definitely easier to stick with UR.

BTW, Asellus, your pointing out my reasoning was ER got me interested in ERs and I read up on the topic. Neat.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Oct 22, 2007 9:29 pm    Post subject: Reply with quote

nataraj,

I agree with your suspicions: it is not coloring, Medusa or otherwise, in any conventional sense. I'd say it is implication chaining that leads to a contradiction. Some would probably call it "forcing." Note that in your third chain, you made use of the {457} ALS in R5C46. (It becomes a {47} locked pair if R5C9 is <5>.)

Usually, we use an AIC to create pincers at the ends that effect eliminations. Sometimes, in very difficult cases, the AIC will have a branch or two. Sometimes, we discover a contradiction instead of pincers. I can't see any reason to ignore the contradiction just because it isn't pincers. For me, it's still logic, not forcing.

It is certainly possible to use colors to mark an implication chain. However, down this path it is only a short tumble to what even I would consider to be forcing.

By the way... your reference elsewhere about GEM sent me to look it up. Turns out I've been doing it without knowing it. I use dots (rather than digits) in a 9-grid pattern to pencil mark. To color, I use the "^" character, oriented up and down, in place of the dot. If I need a second color cluster, I use the same shape oriented left and right. Admittedly, this approach isn't for everyone. (It's sort of like reading Braille!) But, it has worked for me.

I'm going to try exploring this puzzle further using Medusa.
Back to top
View user's profile Send private message Visit poster's website
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Oct 22, 2007 10:37 pm    Post subject: Reply with quote

Okay! Medusa does it. It's a nice example of the power of Medusa and only requires a single cluster (no Medusa multi-coloring... so only EM needed, not GEM, for P&P types).

Start coloring in R2C9 and quickly get here:
Code:
+--------------------+----------------------+----------------------+
| 9      3    2      | 45     1      45     | 7      8      6      |
| 1r6g   8    7      | 39     29     236r   | 5      4      1g9r   |
| 4      5    1g6r   | 678    789    67     | 3r9g   1r3g   2      |
+--------------------+----------------------+----------------------+
| 3      1    4      | 2      57     9      | 6      57     8      |
| 2      6    8      | 457    3      457    | 1      9      57     |
| 7      9    5      | 1      6      8      | 4      2      3      |
+--------------------+----------------------+----------------------+
| 8      7    1r6g   | 56r9   259    25     | 3g9r   1g3r   4      |
| 1g6r   4    9      | 3678   78     367    | 2      57     1r57   |
| 5      2    3      | 7g9r   4      1      | 8      6      7r9g   |
+--------------------+----------------------+----------------------+

Some might think this is the end of the road, but look at Box 9. Every unresolved cell except one has a red candidate. That means that the <5> in R8C8 is red. This immediately eliminates <7> in R8C9 (due to the strongly linked <5>s) and the coloring continues to here:
Code:
+--------------------+----------------------+----------------------+
| 9      3     2     | 45     1      45     | 7      8      6      |
| 1r6g   8     7     | 39     29     236r   | 5      4      1g9r   |
| 4      5     1g6r  | 678    789    67     | 3r9g   1r3g   2      |
+--------------------+----------------------+----------------------+
| 3      1     4     | 2      5r7g   9      | 6      5g7r   8      |
| 2      6     8     | 457    3      457    | 1      9      5r7g   |
| 7      9     5     | 1      6      8      | 4      2      3      |
+--------------------+----------------------+----------------------+
| 8      7     1r6g  | 56r9   25g9   25     | 3g9r   1g3r   4      |
| 1g6r   4     9     | 3678   78     367    | 2      5r7g   1r5g   |
| 5      2     3     | 7g9r   4      1      | 8      6      7r9g   |
+--------------------+----------------------+----------------------+

Again, this is not the end of the road. Look at R8C5. It has a green <5> and can see a red <9>. So, it cannot contain <9>. Eliminating that <9> leads to some simplifications. But, I'm going to ignore them and point out that the remaining <2> is now red. This means that in R2C5, the <2> is green and the <9> red. But, there is already a red <9> in R2. So, it's a Medusa Wrap: all the reds are eliminated and all the greens placed.

For most, this is probably more satisfying than any of the chaining.

In any case, nataraj, it's too bad you object to DP techniques since they sure can save a lot of trouble!
Back to top
View user's profile Send private message Visit poster's website
keith



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

PostPosted: Tue Oct 23, 2007 1:37 am    Post subject: Reply with quote

Marty R. wrote:
Keith, is "Freep" a Keith creation? Very Happy

I used a Type 2 rectangle and three Finned X-Wings.


Marty,

"Freep" is the local nickname for the Detroit Free Press.

www.freep.com

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



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Tue Oct 23, 2007 6:21 am    Post subject: Reply with quote

I really appreciate your taking the time, Asellus, to point out the (for me) previously unthought-of possibilities in finding clever and solid (as opposed to doubtful forcing) inferences.

To really understand what is going on I have to ask a few more questions, please bear with me:

1) I always thought coloring (and also Medusa) uses only strong links, so that ALL candidates of the same parity are either true or false and there is always a strong link between any two opposite parities (like in your grid, if r2c9<>9 then any of the greens must be true). All equivalence marks work in both directions. Pls confirm or correct this interpretation.

2) The reasoning in box 9, on the other hand, looks one-directional to me: if red then 5 must be true. (as it turns out, r is false and any implications based on r2c9=9 must be discarded - ex falso quodlibet). In my GEM coloring the 5 in r8c8 gets a "super" mark meaning (if red then r8c8=5) but not a parity mark. I must have missed a crucial step here.

And - as I said last night - I am not opposed to using the uniqueness argument, I just tried to avoid it if possible. Of course, it is SOOO much faster. Also, I don't mind the extra mile if the scenery is worth it, and I must say this time it was worth a hundred miles (learnt so much about solving techniques I wouldn't have looked into otherwise...)
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Tue Oct 23, 2007 11:21 am    Post subject: Reply with quote

nataraj,

I'm glad you share my appreciation of the scenery!

To answer your questions...

Going back and pondering some more, I'd say that you've got me!

Yes, in basic Coloring, whether single digit or Medusa (multi-digit), the Color Cluster is limited to strong ("conjugate") links. However, it is sometimes possible to assign polarities due to implied conjugate relationships, such as can occur in a Box-Line interaction (a form of "group coloring") or when a bivalue pair can each see an instance of opposite polarities.

I thought something like that was happening here in Box 9 ... something akin to "survivor promotion" from super to par parity in GEM. But, I went and scrutinized those GEM rules and I believe you are correct: it isn't the case here.

However, I have convinced myself that the reasoning is otherwise sound, it just isn't Medusa Coloring. That alternate implication has sneaked back in the door! If red is true, there is definitely a contradiction; so red can't be true.

So, while it isn't strictly Medusa, it's still seems to be a useful way to proceed when other approaches are running dry.
Back to top
View user's profile Send private message Visit poster's website
Earl



Joined: 30 May 2007
Posts: 677
Location: Victoria, KS

PostPosted: Tue Oct 23, 2007 5:37 pm    Post subject: FreeP Reply with quote

Asellus,

There must be something in this discussion that I am missing.
Starting with your grid, the UR eliminates the 7 in R5C9, making it a 5 which eliminates other 5's and leaves a pair (29) in C5, eliminating the 9 in R3C5 which makes R3 in Box 2 a triple and the rest is singles.

Did I miss something? Are you trying to solve it without using the UR?

Earl
Back to top
View user's profile Send private message Send e-mail
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Tue Oct 23, 2007 6:00 pm    Post subject: Reply with quote

yep.

Stictly speaking, Asellus didn't but I did (try to solve w/o UR)
Asellus is being helpful as always but just the same we are (ahem: I am* ) reaching the conclusion that it is pretty tedious to do it without UR.

As much as I enjoy the scientific debate about Medusa and other colorings - it is clear that the puzzle is already solved.

(still trying to digest the Asellus postings)

nataraj
_________

*: cf. "we are Bates" - Top Hat, 1935
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: Tue Oct 23, 2007 10:55 pm    Post subject: Reply with quote

Quote:
I don't mind the extra mile if the scenery is worth it


Exactly! It's not the destination, it's the journey.

Keith

PS: Which brings me to the kind of question Andy Rooney would ask: "Did you ever notice the wasted space used by printing a solution of yesterday's puzzle?"

If you cannot solve a Sudoku, how does knowing the solution help?
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Wed Oct 24, 2007 1:04 am    Post subject: Reply with quote

Quote:
If you cannot solve a Sudoku, how does knowing the solution help?


I've been pondering that one since Day 1. I haven't yet seen a print or Internet source that doesn't publish solutions, so maybe people are looking at these things, but for reasons not apparent to me. Question
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