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 

What should be easy, seems very difficult

 
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: Wed Feb 27, 2008 10:36 pm    Post subject: What should be easy, seems very difficult Reply with quote

I have been staring at this one, off and on, for a week now.

http://www.menneske.no/sudoku/eng/showpuzzle.html?number=1955784

Code:
Puzzle: M1955784vh(0)
+-------+-------+-------+
| . . 3 | 2 . . | 4 . . |
| 2 9 4 | . 8 . | 1 6 3 |
| . . . | . . 1 | . . . |
+-------+-------+-------+
| . 7 . | . . . | 6 . . |
| . 4 . | 6 . 5 | . 8 . |
| . . 6 | . . . | . 7 . |
+-------+-------+-------+
| . . . | . . 6 | . . . |
| 8 5 7 | . 9 . | 3 4 6 |
| . . 1 | 3 . . | 7 . . |
+-------+-------+-------+

I thought that a Menneske rating of 0 (zero) means that it can be solved by the list of techniques he describes. Clearly, I am wrong!

The basics get me to here:
Code:
+----------------+----------------+----------------+
| 17   18   3    | 2    6    9    | 4    5    78   |
| 2    9    4    | 5    8    7    | 1    6    3    |
| 567  68   58   | 4    3    1    | 289  29   2789 |
+----------------+----------------+----------------+
| 159  7    58   | 89   12   4    | 6    3    259  |
| 3    4    29   | 6    7    5    | 29   8    1    |
| 159  128  6    | 89   12   3    | 259  7    4    |
+----------------+----------------+----------------+
| 49   3    29   | 7    45   6    | 2589 1    2589 |
| 8    5    7    | 1    9    2    | 3    4    6    |
| 469  26   1    | 3    45   8    | 7    29   259  |
+----------------+----------------+----------------+

The only thing I can see is multicoloring (an extended skyscraper with the ground floors in R9) that takes out <2> in R3C7. Then, I am stuck.

I know there are a couple of chains, but am I missing some kind of named pattern?

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



Joined: 21 Apr 2006
Posts: 536

PostPosted: Thu Feb 28, 2008 10:46 am    Post subject: Reply with quote

Cant find something easy either. I solved it with this M-wing variation.
Code:
 *----------------------------------------------*
 | 17   18   3   | 2   6   9  | 4     5   78    |
 | 2    9    4   | 5   8   7  | 1     6   3     |
 | 567  6-8  58  | 4   3   1  |#89    29  2789  |
 |---------------+------------+-----------------|
 | 159  7    58  |*89  12  4  | 6     3  *259   |
 | 3    4    29  | 6   7   5  |*29    8   1     |
 | 159 @128  6   |#89  12  3  |*259   7   4     |
 |---------------+------------+-----------------|
 | 49   3    29  | 7   45  6  | 2589  1   2589  |
 | 8    5    7   | 1   9   2  | 3     4   6     |
 | 469  26   1   | 3   45  8  | 7     29  259   |
 *----------------------------------------------*
After the coloring elimination of 2 the 89's in r3c7 and r6c4 can be connected by
r3c7=9 => r56c7<>9 => r4c9=9 => r4c4<>9 => r6c6=9
(there is also a coloring for 8 r3c7=8 => r6c4=8, but not needed here)

So with the strong link for 8 in r6c2 we have r3c7=8 or r6c2=8
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Thu Feb 28, 2008 11:45 am    Post subject: Reply with quote

I can't find any named techniques, either. But, after that color wing removal of the <2>, the {29} UR allows removal of <9> from r9c9. This creates a "useless" XYZ Wing with one cell transported to remove <2> from r7c9, exposing an X-Wing.

After that, if we recall the <9> removed from r9c9 due to the UR, there is a 6-cell DP in b789 that requires r9c8=9 (through some roundabout implications).

I suspect that none of this is what you were looking for and the puzzle still isn't solved. To accomplish that, I resorted to Medusa multi-coloring (two clusters, no extensions) followed by a Medusa wrap (no extensions).

[Edit: Missed ravel's post while working on this. Wouldn't you know it!]
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: Thu Feb 28, 2008 11:59 am    Post subject: Reply with quote

Ravel's post made me revisit the Medusa. After that initial <2> removal, a simple Medusa multi-coloring (bridging <9>s in r35c7) removes <8> from r3c3. Then, a bit more basic Medusa removes <9> from r3c7 and solves the puzzle. Nothing else is required.
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: Thu Feb 28, 2008 4:33 pm    Post subject: simple Reply with quote

An xy-chain makes R3C7 an 8 and solves the puzzle.

Are such chains "dishonorable?"

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



Joined: 18 Oct 2007
Posts: 1741

PostPosted: Thu Feb 28, 2008 8:33 pm    Post subject: Re: simple Reply with quote

Earl wrote:
An xy-chain makes R3C7 an 8 and solves the puzzle.

Are such chains "dishonorable?"

Earl


wouldn't call it dishonorable... I'd say your eyes and deductive reasoning are working strongly.

some find fish hard to look for, some find xy-chains hard to look for. regardless of the difficulty of the technique, its still a technique... Exclamation

consider this... a xy-wing is a xy-chain. if you allow yourself to look for xy-wings, you are essentially looking for a 3 cell xy-chain.

therefore, xy-chains (A.K.A. xy-wings) are arguably one of the most, if not the most sought after PATTERNS. I didn't say chains on purpose...

Asellus can say more, but he was good at pointing out that a xy-chain is just one pattern within a broader class of chains. his description of an xy-wing in eureka notation is an example.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Thu Feb 28, 2008 8:37 pm    Post subject: Re: simple Reply with quote

Earl wrote:
Are such chains "dishonorable?"
Not at all for me.
I just dont like to search for them say from top left to right bottom. So i start to look for chains from a few UR patterns, remote pairs, "useless" xy-wings and similar.
I also dont find an xy-chain to eliminate 9 from r3c7, i just have one for r67c7<>9 or a "strong link chain" to eliminate 9 from r3c8 - either r3c8=2 or r9c8=2 => r3c7=9.
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Thu Feb 28, 2008 10:09 pm    Post subject: Reply with quote

ravel wrote:
Cant find something easy either. I solved it with this M-wing variation.
Code:
 *----------------------------------------------*
 | 17   18   3   | 2   6   9  | 4     5   78    |
 | 2    9    4   | 5   8   7  | 1     6   3     |
 | 567  6-8  58  | 4   3   1  |#89    29  2789  |
 |---------------+------------+-----------------|
 | 159  7    58  |*89  12  4  | 6     3  *259   |
 | 3    4    29  | 6   7   5  |*29    8   1     |
 | 159 @128  6   |#89  12  3  |*259   7   4     |
 |---------------+------------+-----------------|
 | 49   3    29  | 7   45  6  | 2589  1   2589  |
 | 8    5    7   | 1   9   2  | 3     4   6     |
 | 469  26   1   | 3   45  8  | 7     29  259   |
 *----------------------------------------------*
After the coloring elimination of 2 the 89's in r3c7 and r6c4 can be connected by
r3c7=9 => r56c7<9> r4c9=9 => r4c4<9> r6c6=9
(there is also a coloring for 8 r3c7=8 => r6c4=8, but not needed here)

So with the strong link for 8 in r6c2 we have r3c7=8 or r6c2=8

I'm missing something here (duh, what else is new?). I was under the impression that the essence of the M-Wing was connecting the pairs via two (or four) strong links. I count one from r4c4 to r6c4 and a second from r4c9 to r4c4. That's two, what about getting from r3c7 to r4c9? Question Question

Quote:
Are such chains "dishonorable?"

Like beauty, in the eye of the beholder?
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Thu Feb 28, 2008 11:02 pm    Post subject: Reply with quote

As to finding XY Chains, I recommend focussing first on locating potential pincers: two bivalue cells that share a digit and both "see" cells containing that digit. Next, look to see if they can be joined by a chain of bivalues. Often, it is immediately obvious that they cannot (e.g., the shared digit in one of the "pincer" bivalues cannot see another bivalue with that digit) and so that potential pincer can be abandoned. Also, this search for a connecting chain sometimes reveals another effective pincer even if it wasn't the one you set out to find a connection with.

Working in this way, one can do a top-left to bottom-right scan similar to that described in the Techniques forum by nataraj.
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: Fri Feb 29, 2008 12:06 am    Post subject: Reply with quote

1. Asellus, what is a "bivalue"? I imagine it is a cell with two candidates, but it seems it may also be a strong link?

2. "Honorable", I don't know. But I do have a mathematician's view of "elegant". What ravel does to find chains is elegant. See a pattern to exploit, add a twist, and you have something very clever. I can see how to get there, in time.

What my software does to find chains is not at all elegant. Maybe the algorithm is very clever, but the chains look, to me, like trial and error.

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



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

PostPosted: Fri Feb 29, 2008 9:15 am    Post subject: Reply with quote

keith wrote:
Asellus, what is a "bivalue"? I imagine it is a cell with two candidates, but it seems it may also be a strong link?

I was responding to the question of how easy, or not, it is to scan for XY Chains, so was only addressing the question of bivalue cells (cells that contain only two candidates).

The larger question of looking for AICs generally is more difficult to address. I don't believe that there any one way to go about it. I have found various things that work. To the extent that you focus on conjugates (bivalues and conjugate strong links in houses), then coloring seems the preferred approach... with some multicoloring thrown in here and there. That will ferret out those AICs pretty readily.

Another approach is that of transporting otherwise useless things, such as wing pincers or candidates that have a strong inference induced by a DP.

Also, one can focus on ALSs to see if they can form part of a useful chain.

At some point, however, the more one keeps at such things, the more it starts to resemble trial and error. One can focus on the technique and say, "Well, if I stick to strict coloring to find a chain, then that's okay," or "If I'm just transporting parts of a named technique, and not getting too fancy and involved in my transporting, then that's okay" or some such. But, bottom line, it's what works for you.

As for "elegance," I'd say that that arises when something involves a simple, clever, and insightful "twist" and produces significant results, as you note with ravel's M-Wing variant. I was annoyed, frankly, that I didn't find that implication with my Medusa multi-coloring. When I went back and looked again, it was evident that I would have had to have been quite lucky to have happened upon that particular chain by Medusa (excluding an exhaustive "all possiblities" approach, which is just about the antithesis of elegant, as I believe I demonstrated elsewhere).

Most often, the one thing one can be sure of is that if enough eyes look at a problem, someone else is likely to come up with a solution that is more elegant than yours. But now and then, they don't!
Back to top
View user's profile Send private message Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Fri Feb 29, 2008 10:38 am    Post subject: Reply with quote

Marty R. wrote:
I'm missing something here (duh, what else is new?). I was under the impression that the essence of the M-Wing was connecting the pairs via two (or four) strong links. I count one from r4c4 to r6c4 and a second from r4c9 to r4c4. That's two, what about getting from r3c7 to r4c9? :?: :?:
Yes, the classical M-wing is connected by 2 strong links for one candidate. This makes sure, that both cells, say A and C, always must have the same value, say x or y. Then, if there is a strong link for x (or y) from C (or A) to a cell D, one of A (or C) and D must be x (or y).

Now one variant is, that you connect A and C with 4, 6 or 8 strong links.
Another is, you have 2 chains. A=x => C=x and A=y => C=y (no strong links necessary here, it can be any chain, coloring, bivalue, bilocation etc.).
Both also make sure that A and C must have the same value.

A 3rd variant is, you only have one chain A=x => C=x. This one you can only use, if there is a strong link for y from C to a cell D. Then either A=y or A=x => C=x => D=y, i.e. one of A and D must be y.
This is, what i used here (A is r3c7, C is r6c4, D is r6c2, x=9, y=8).

Because in this case there is also a chain
r3c7=8 => r3c3=5 => r4c3=8 => r4c4=9 => r6c4=8
we know that (like in classical M-wing) r3c7 and r6c2 must have the same value. But there is no other strong link for 8 or 9 from r3c7 or r6c4, that could be used for an elimination.

btw with the strong link for 8 in c3 r3c7 and r4c4 is a w-wing for 9.
With
r3c7=9 => r56c7<>9 => r4c9=9 => r4c4=8
we a w-wing variation for 8 (one of r3c7 and r4c4 must be 8) by means of the grouped strong link r56c7=9 or r4c9=9 in box 6.
But also no eliminations possible.
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Fri Feb 29, 2008 4:44 pm    Post subject: Reply with quote

Thanks for the explanation, Ravel.
Back to top
View user's profile Send private message
storm_norm



Joined: 18 Oct 2007
Posts: 1741

PostPosted: Sat Mar 01, 2008 12:57 am    Post subject: Reply with quote

xy-chains...

1. dishonorable?? probably not

2. elegant?? probably not

3. applying them?? Priceless!! Laughing
Back to top
View user's profile Send private message
nataraj



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

PostPosted: Sat Mar 01, 2008 11:55 am    Post subject: Reply with quote

storm_norm wrote:
xy-chains...

1. dishonorable?? probably not

2. elegant?? probably not

3. applying them?? Priceless!! Laughing


I'm with you there, Norm Smile

And I'd add

4. finding them?? not impossible

(and no worse than finding some of those ERs, snake hairs, fish and fowl ...)
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: Sat Mar 01, 2008 10:41 pm    Post subject: Reply with quote

It's funny that I described my Medusa approach above as multi-coloring (which it is) when it is even easier to consider it as what I long ago described as a "special bivalue extension" in the Techniques forum (not that it is all that special, really). Here is the Medusa cluster derived from cell r5c7 (after that removal of <2> from r1c7 described by Keith):
Code:

+------------------+-----------+----------------+
| 17    18    3    | 2   6   9 | 4     5   78   |
| 2     9     4    | 5   8   7 | 1     6   3    |
| 56A7 #6a8A  58   | 4   3   1 |@89    29  2789 |
+------------------+-----------+----------------+
| 159   7     58   | 89  12  4 | 6     3   259  |
| 3     4     2a9A | 6   7   5 |#2A9a  8   1    |
| 159   12A8  6    | 89  12  3 | 259   7   4    |
+------------------+-----------+----------------+
| 49    3     2A9a | 7   45  6 | 2589  1   2589 |
| 8     5     7    | 1   9   2 | 3     4   6    |
| 46a9  2a6A  1    | 3   45  8 | 7     29  259  |
+------------------+-----------+----------------+

Now, look at that {89} r1c7 bivalue. The <8> can "see" 8A in r3c2 and the <9> can see 9a in r5c7. So, polarity is induced and we can color the bivalue as 8a9A and perform the resulting trap eliminations:
Code:

+------------------+-----------+------------------+
| 17    18    3    | 2   6   9 | 4     5    78    |
| 2     9     4    | 5   8   7 | 1     6    3     |
| 56A7  6a8A #5-8  | 4   3   1 | 8a9A  29  #27-89 |
+------------------+-----------+------------------+
| 159   7     58   | 89  12  4 | 6     3    259   |
| 3     4     2a9A | 6   7   5 | 2A9a  8    1     |
| 159   12A8  6    | 89  12  3 |#25-9  7    4     |
+------------------+-----------+------------------+
| 49    3     2A9a | 7   45  6 |#258-9 1    2589  |
| 8     5     7    | 1   9   2 | 3     4    6     |
| 46a9  2a6A  1    | 3   45  8 | 7     29   259   |
+------------------+-----------+------------------+

Nifty, no? However, it seems to occur rarely (which is why I forgot about it).
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: Sun Mar 02, 2008 3:46 am    Post subject: chains Reply with quote

Thanks for the comments on xy-chains. Very enlightening.

Earl
Back to top
View user's profile Send private message Send e-mail
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