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 tough one

 
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: Sat Dec 01, 2007 5:06 pm    Post subject: A tough one Reply with quote

This one prompted me to learn Medusa coloring ...
Code:
Puzzle: M4276831sh(10)
+-------+-------+-------+
| 5 . 7 | 8 . . | 9 . 1 |
| . 1 2 | 3 . . | 4 5 . |
| 9 . . | . . . | . . 8 |
+-------+-------+-------+
| . . . | . 6 . | . 8 5 |
| . . . | 9 . 8 | . . . |
| 7 8 . | . 1 . | . . . |
+-------+-------+-------+
| 2 . . | . . . | . . 6 |
| . 3 8 | . . 9 | 5 7 . |
| 4 . 1 | . . 5 | 8 . 9 |
+-------+-------+-------+


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



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

PostPosted: Sat Dec 01, 2007 5:25 pm    Post subject: A tough one Reply with quote

After basics, an xy-chain eliminates the 4 from R4C4, making possible an xy-wing pivoted at R5C5, and the rest is singles.

Although I really should learn the Medusa coloring technique.

Earl
Back to top
View user's profile Send private message Send e-mail
Marty R.



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

PostPosted: Sat Dec 01, 2007 6:37 pm    Post subject: Reply with quote

After the basics I was staring at a BUG+3, with all three trivalue cells in box 5. Keith gave me a recent lesson in this technique and I either got lucky or reasoned it out properly.

I also need to learn Medusa coloring (and various other techniques) if I'm going to get to the next level.
Back to top
View user's profile Send private message
Johan



Joined: 25 Jun 2007
Posts: 206
Location: Bornem Belgium

PostPosted: Sat Dec 01, 2007 6:49 pm    Post subject: Reply with quote

There is a potential [47] DP * in R47C46, either R4C4=2 or R4C6=3 or

both.

If R4C4=2 => R4C2=9 => R2C3 =4 => R6C3=5

OR

R4C6=3 => R6C6=4 => R6C3=5 which means R6C3=5, solving the
puzzle
Code:

+--------------------------+--------------------------+-------------------------+
| 5         6         7    | 8          4        2    | 9          3        1   |
| 8         1         2    | 3          9        6    | 4          5        7   |
| 9         4         3    | 57         57       1    | 2          6        8   |
+--------------------------+--------------------------+-------------------------+
| 13        29        49   |*247        6       *347  | 17         8        5   |
| 13        25        6    | 9          57       8    | 17         4        23  |
| 7         8         45   | 245        1        34   | 6          9        23  |
+--------------------------+--------------------------+-------------------------+
| 2         59        59   |*47         8       *47   | 3          1        6   |
| 6         3         8    | 1          2        9    | 5          7        4   |
| 4         7         1    | 6          3        5    | 8          2        9   |
+--------------------------+--------------------------+-------------------------+
Back to top
View user's profile Send private message Send e-mail
keith



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

PostPosted: Sat Dec 01, 2007 7:11 pm    Post subject: Medusa coloring Reply with quote

Medusa coloring is a systematic way to find (the same eliminations made by) XY-chains.

a) In coloring, the cells in a chain of strong links for a single candidate are colored alternately (say) red and green. Either all the red cells are true (have the value of the candidate), or the green ones are.

b) If a cell has only two candidates, only one is true.

Medusa coloring combines these two concepts by repeatedly applying the two steps:

1. Color a chain of strong links. (Only one end of each link is true.)

2. In each bivalue cell, color the other candidate. (Only one candidate is true.)

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


After basics, this is the position:

Code:
+-------------+-------------+-------------+
| 5   6   7   | 8   4   2   | 9   3   1   |
| 8   1   2   | 3   9   6   | 4   5   7   |
| 9   4   3   | 57  57  1   | 2   6   8   |
+-------------+-------------+-------------+
| 13  29  49  | 247 6   347 | 17  8   5   |
| 13  25  6   | 9   57  8   | 17  4   23  |
| 7   8   45  | 245 1   34  | 6   9   23  |
+-------------+-------------+-------------+
| 2   59  59  | 47  8   47  | 3   1   6   |
| 6   3   8   | 1   2   9   | 5   7   4   |
| 4   7   1   | 6   3   5   | 8   2   9   |
+-------------+-------------+-------------+


Color the strong links for candidate value <2>. r=red, g=green:

Code:
+-------------+--------------+-------------+
| 5   6   7   | 8    4   2   | 9   3   1   |
| 8   1   2   | 3    9   6   | 4   5   7   |
| 9   4   3   | 57   57  1   | 2   6   8   |
+-------------+--------------+-------------+
| 13  2r9 49  | 2g47 6   347 | 17  8   5   |
| 13  2g5 6   | 9    57  8   | 17  4   2r3 |
| 7   8   45  | 2r45 1   34  | 6   9   2g3 |
+-------------+--------------+-------------+
| 2   59  59  | 47   8   47  | 3   1   6   |
| 6   3   8   | 1    2   9   | 5   7   4   |
| 4   7   1   | 6    3   5   | 8   2   9   |
+-------------+--------------+-------------+


Note the two-candidate cells involving <2>. Color the second candidate the opposite color, and then extend the coloring on the strong links of that candidate. After coloring on <3> and <5> in R345:

Code:
+--------------+---------------+-------------+
| 5   6    7   | 8     4   2   | 9   3   1   |
| 8   1    2   | 3     9   6   | 4   5   7   |
| 9   4    3   | 57    57  1   | 2   6   8   |
+--------------+---------------+-------------+
| 13g 2r9  49  | 2g47  6   3r47| 17  8   5   |
| 13r 2g5r 6   | 9     5g7 8   | 17  4   2r3g|
| 7   8    45g | 2r45r 1   3g4 | 6   9   2g3r|
+--------------+---------------+-------------+
| 2   59   59  | 47    8   47  | 3   1   6   |
| 6   3    8   | 1     2   9   | 5   7   4   |
| 4   7    1   | 6     3   5   | 8   2   9   |
+--------------+---------------+-------------+


You are about to reach a contradiction: In R6, both C3 and C6 will contain <4r> on the next cycle. Thus red is false, green is true.

I believe I heard that Crayola now makes erasable colored pencils. I'll have to get a set!

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



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sat Dec 01, 2007 9:44 pm    Post subject: Reply with quote

Marty R. wrote:
After the basics I was staring at a BUG+3, with all three trivalue cells in box 5. Keith gave me a recent lesson in this technique and I either got lucky or reasoned it out properly.
Code:
*--------------------------------------------------*
 | 5    6    7    | 8    4    2    | 9    3    1    |
 | 8    1    2    | 3    9    6    | 4    5    7    |
 | 9    4    3    | 57   57   1    | 2    6    8    |
 |----------------+----------------+----------------|
 | 13   29   49   | 247  6    347  | 17   8    5    |
 | 13   25   6    | 9    57   8    | 17   4    23   |
 | 7    8    45   | 245  1    34   | 6    9    23   |
 |----------------+----------------+----------------|
 | 2    59   59   | 47   8    47   | 3    1    6    |
 | 6    3    8    | 1    2    9    | 5    7    4    |
 | 4    7    1    | 6    3    5    | 8    2    9    |
 *--------------------------------------------------*

I am no BUG expert, but as i see it this way:
If in a BUG+1 cell there is one candidate, that appears additionally 2 times in the same box, row and column, it must be true to avoid the deadly pattern (i.e a pattern with bivalue cells, that has 2 solutions).
btw there can be a grid, where none of the candidates in the single 3-value cell has the property, but this is very rare and needs complicated eliminations.
In a BUG+k things are clear, if in all k polyvalued cells there is exactly one candidate with this property and for the others there is a unit with less than 2 more occurences. Then one of them (with the property) must be true.
Here 3 polyvalued cells share the same unit. In r4c6 and r6c4 only 4 can have the property (though we have 4 4's in the box), but in r4c4 4 and 7 are possible candidates.
So i dont know, how to use it.
Back to top
View user's profile Send private message
nataraj



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

PostPosted: Sat Dec 01, 2007 10:19 pm    Post subject: Re: Medusa coloring Reply with quote

keith wrote:
Medusa coloring is a systematic way to find (the same eliminations made by) XY-chains...


Liked your medusa overview, keith!

I'd add to the above (quoted) statement:
Medusa goes beyond xy-chains in that it can combine the power of coloring (strong links in rows, columns, boxes even if there are more than two candidates in the cells!) with the power of xy-chains (strong links in the cells themselves and between those bi-value cells)
Back to top
View user's profile Send private message Send e-mail Visit poster's website
nataraj



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

PostPosted: Sat Dec 01, 2007 10:50 pm    Post subject: Reply with quote

"medusa is just a bi-value/bi-location plot"

sapienti sat Wink

________


in other words, medusa is a visualization technique to show sets of candidates connected by strong links

- either because there are only two occurrences of a number in a house
- or there are only two numbers in a cell
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: Sat Dec 01, 2007 11:05 pm    Post subject: Reply with quote

Quote:
Here 3 polyvalued cells share the same unit. In r4c6 and r6c4 only 4 can have the property (though we have 4 4's in the box), but in r4c4 4 and 7 are possible candidates.
So i dont know, how to use it.


I probably don't know either. I used 4 in all three trivalue cells. If either is a 4, then r6c6 must be 3. But Ravel makes a good point about the 7. If r4c4 is 7, then r6c6 is 3 as well.

Was my reasoning wrong then? Is the correct reasoning that r4c6 or r6c4 is 4 or r4c4 is 7?
Back to top
View user's profile Send private message
keith



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

PostPosted: Sat Dec 01, 2007 11:07 pm    Post subject: BUGging me! Reply with quote

Here is the BUG+3:
Code:
*---------------------------------------------------*
 | 5    6    7    | 8     4    2    | 9    3    1    |
 | 8    1    2    | 3     9    6    | 4    5    7    |
 | 9    4    3    | 57    57   1    | 2    6    8    |
 |----------------+-----------------+----------------|
 | 13   29   49   | 24(7) 6    3(4)7| 17   8    5    |
 | 13   25   6    | 9     57   8    | 17   4    23   |
 | 7    8    45   | 2(4)5 1    34   | 6    9    23   |
 |----------------+-----------------+----------------|
 | 2    59   59   | 47    8    47   | 3    1    6    |
 | 6    3    8    | 1     2    9    | 5    7    4    |
 | 4    7    1    | 6     3    5    | 8    2    9    |
 *---------------------------------------------------*

Consider R6C4 in R6: The DP is formed by <25>, it is destroyed by <4>.

Consider R4C6 in C6: The DP is formed by <37>, it is destroyed by <4>.

Having established these DP elements, consider R4C4 in its row, column, or block: The DP is formed by <24>, it is destroyed by <7>.

One of the values (x) must be true.

If either R4C6 or R6C4 is <4>, R6C6 is <3>, R6C9 is <2>, R5C9 is <3>, R5C1 is <1>, and R4C1 is <3>.

If R4C4 is <7>, R4C7 is <1>, and R4C1 is <3>.

R4C1 is <3> solves the puzzle.

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



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

PostPosted: Sat Dec 01, 2007 11:26 pm    Post subject: Another observation Reply with quote

It seems to me that removing <4> in R4C4 does not contribute to a Deadly Pattern, for there are now three <7>'s in C4, and no choice in R6C4 can make a DP in C4.

In other words, a candidate <4> in R4C4 does not break up a DP.

As I said in a previous post, with a BUG+n you must first establish that the puzzle has a "valid" DP. Then, the leftover values in the >2 value cells are the ones that destroy the DP.

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



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

PostPosted: Sun Dec 02, 2007 1:05 am    Post subject: Reply with quote

Quote:
It seems to me that removing <4> in R4C4 does not contribute to a Deadly Pattern, for there are now three <7>'s in C4, and no choice in R6C4 can make a DP in C4.

Thanks for the clarification, it means that I got the right answer with the wrong reasoning.

It continues to confuse me. I learned with BUG+1 to check for which number occurred three times in row, column and box. Now with BUG+3, we start out just checking a row or column because of the other trivalue cells and then somehow put it all together.

Maybe I should stick to crosswords (just kidding). Rolling Eyes
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Sun Dec 02, 2007 1:54 am    Post subject: Reply with quote

Regarding Medusa...

Medusa eliminations are not only those that would result from XY Chains. Medusa coloring reveals AIC (Alternate Implication Chain) relationships without doing the explicit chaining. An XY Chain is the simplest sort of AIC, but there are many ways to form an AIC. Any Medusa elimination could also be accomplished with an explicit AIC (which often would not be an XY Chain). However, the opposite statement isn't true. It is possible to construct AICs in a puzzle that perform eliminations that cannot be accomplished by Medusa. (If this weren't so, then Medusa would be the only technique we would need!)

By the way, little up and down "caret (^)" marks, or something similar, work fine for pencil coloring. No actual colors needed!
Back to top
View user's profile Send private message Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sun Dec 02, 2007 10:53 am    Post subject: Re: Another observation Reply with quote

keith wrote:
It seems to me that removing <4> in R4C4 does not contribute to a Deadly Pattern, for there are now three <7>'s in C4, and no choice in R6C4 can make a DP in C4.
Yes, i didn't do the whole work, just eliminated the numbers as candidates to destroy the DP, that would leave a single in a unit, not this one, which leaves 3 7's - instead of (possibly) 2 of each number in each unit.

Concerning Medusa coloring i only can say, that normally i find a forcing or contradiction chain faster diretly, like here
r4c2=2 => r5c2=5 => r6c3=5 => r6c2=2
The problem with both is to find the right beginning, so the t&e factor is the same.
Back to top
View user's profile Send private message
nataraj



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

PostPosted: Sun Dec 02, 2007 1:04 pm    Post subject: Re: Another observation Reply with quote

ravel wrote:

The problem with both is to find the right beginning, so the t&e factor is the same.


In a sense, yes. There is some amount of trial and error in both. But I strongly believe that the AMOUNT of t&e is vastly different between medusa and plain old forcing chains.

As you said: how to find the beginning?

I've done a fair amount of FC based sudoku solving (back when I had not yet heard of box/line interactions, later when I didn't know about x-wings, swordfish, xy wings ...) and I can remember quite clearly how frustrating it was to start at one cell, continue through the whole solving process, only to arrive at a dead end again. The puzzle was ruined. To try other starting points would mean to print the page again and start the puzzle from scratch....

Now medusa gives you the advantage of showing many remote relationships all at the same time and thus makes it VERY easy to look for that one implication that solves the puzzle. It sort of takes out the tedium of looking for AICs. That's all. But it is a lot.
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: Sun Dec 02, 2007 4:41 pm    Post subject: Reply with quote

Quote:
The puzzle was ruined. To try other starting points would mean to print the page again and start the puzzle from scratch....

Keeping a supply of blank grids handy to test chains, coloring, etc., eliminates that frustration. I use this site's six-blank-grids-to-a-page offering.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sun Dec 02, 2007 6:34 pm    Post subject: Reply with quote

On paper i never (since my early beginnings) inserted something, that might have to be erased before the next number is found - except when i made a mistake (what ruined many puzzles). What i cant "try" in my head, is too hard for me - then i give up. Often it turned out, that i just missed to spot a move within my skills. And 2 times, that the puzzle had multiple solutions - i hated the authors.

About "marking":

Puzzles up to this sites VH level i try without pencilmarks, later i only mark pairs (cant keep all in my mind and helps me with xy-wings) and eliminated candidates. But its very hard to find some naked triples, so i dont like these puzzles in newspapers (unfortunately no one seems to have a program, that creates interesting no PM puzzles, that never need them).

In harder puzzles i tried several help marks, especially for strong links. Here the problem are those in boxes.The marks inside cells more bothered than helped me, so i always try to keep them in my mind.
Same problem with "Medusa marks", which i would allow myself, as long as i dont have to re-color them (to combine 2 groups) or erase them for new starting points. But if they dont lead to an elimination i couldn't see the wood for the trees.

Anyway - this is history. Since i am "retired", i made no hard puzzle on paper. I just let my program do the basics (without UR, ER, finned fish or w-wings) and start with the pencilmark grid.
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Sun Dec 02, 2007 9:45 pm    Post subject: Reply with quote

Ravel's comments about Medusa marking are good ones. Here's an approach I have used, though it probably isn't for everyone. It would be best to use Marty's idea of marking up blank grids for exploring the coloring rather than marking on the original grid. Instead of marking actual numerals, I mark dots in a grid pattern within each cell as illustrated below. This shows a single Box from a larger grid. The conventionally marked Box is shown on the right for comparison.
Code:
+-----------------------+  +----------------+
|   ^   | ~ · · |       |  | 27   12345  .  |
|       | · ·   |       |  | .    35     78 |
| ~     |       |       |  | 359  23459  18 |
|-----------------------|  +----------------+
|       |     · |       |
|       |   ·   |       |
|       |       | ~ ^   |
|-----------------------|
|     · |   · · | ^     |
|   ·   | · ·   |       |
|     · |     · |   ~   |
+-----------------------+

Then, I overmark the dots of candidates I am coloring. Here, I've used a "~" where I would actually use an upside-down "^". Already in this example, I see that the <2> in the upper middle Cell can be removed and the <2> in the lower middle Cell marked "~".

Admittedly, it takes practice to get used to "reading" the spatial dot patterns. But, referring back and forth between the conventionally marked grid and the dot grid can help. (And, if you want to resort to a computer program for coloring, that is understandable!)


I have rarely ever used Medusa multi-coloring, so haven't had to deal with "converting" color symbols if a "Bridge" is converted to a strong link.

In single-digit multicoloring, I generally don't bother converting the symbols. I just write down the pairs that cause eliminations. For instance... I have Aa and Bb clusters with an Ab weak link Bridge: AaAaA-bBbBb
Here, eliminations occur with aB. If the Bridge collapses, then a=b and A=B; eliminations now occur with aB and Ab as well as with Aa and Bb.

Often, even this isn't necessary since in many cases of single digit multi-coloring, the second color cluster can be "marked" in ones head without making literal marks.

(In Medusa, I sometimes explore a possible multi-coloring in my head without making any marks. I usually find that it isn't useful.)


Like Ravel, I too begin a puzzle making minimal marks. First, obvious placements. Then, only digits limited to 2 Cells in a Box or to 3 colinear Cells in a Box. This exposes some locked sets and locked candidates and Box-Line restrictions better than a grid crowded with all possible candidates. If you combine this with a mental scan of incomplete Rows and Columns for restrictions that allow additional placements or restrict markings (due to a locked set in the Row or Column), then additional progress is often possible before resorting to exhaustive marking.

[Perhaps a moderator should make a link to this thead over in the "Techniques" section since it really seems to belong there.]
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: Sun Dec 02, 2007 10:39 pm    Post subject: Reply with quote

ravel wrote:

Anyway - this is history. Since i am "retired"


ravel,

you cannot be retired from this list. You do not have 999 posts!

Quote:
ravel
Joined: 21 Apr 2006
Posts: 151
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