View previous topic :: View next topic 
Author 
Message 
Asellus
Joined: 05 Jun 2007 Posts: 865 Location: Sonoma County, CA, USA

Posted: Thu Jan 03, 2008 11:17 pm Post subject: An Extended Form of Medusa Coloring 


On really tough puzzles, it is sometimes possible to make progress by extending Medusa Coloring in a fairly simple way. I'll explain the idea first, then offer some suggestions on applying it. (Note: I don't claim any originality here. I haven't read a description of this approach elsewhere, but that's most likely due only to my lack of research. It is akin to a watered down GEM and has surely been done by others.)
Start with normal Medusa using, say, "R" and "G". This may not extend very far or even provide any eliminations, but that's okay. Next, one or both of these colors is extended by assuming that it is true and marking resulting placements with alternate markings. For instance, "r" can be used for placements that result if "R" is true and "g" for placements that result if "G" is true.
It is important to note that the "r" and "g" coloring is not Medusa. It is not valid to exploit bivalues, for instance, in rg marking. This should become clear in the examples.
The rules for using these color marks are fairly simple:
(1) Redgreen "trap" eliminations are possible between any redgreen combination EXCEPT "r" and "g". So, RG (normal Medusa), rG, and Rg are all valid "traps"; but rg is not a valid "trap". [Edit: This Rule is too restrictive. See the next post below for a correction.]
(2) Samecolor "wrap" contradictions are valid in all cases. HOWEVER, only the original Medusa color is proved false; the related inference color is not determined by a color "wrap". In other words, GG or Gg or gg for a single candidate in a single house or cell is a "green wrap" and means that all "G" values are false and all "R" and "r" values true. But, it says nothing about the "g" values, which would need to be erased before proceeding if the puzzle were not solved. [Edit to restate this rule more accurately.]
As far as deciding how to apply this approach, I suggest looking for and trying to exploit potential locked sets for finding useful chains of inferred "r" and/or "g" values. It helps if the normal Medusa colored portion is a bit extensive. But, that isn't always necessary or possible.
The nice thing about this approach is that it's not really much more difficult than basic Medusa, which isn't very difficult. But, it's quite a bit more powerful.
Here is an example using a puzzle that was posted on a neighboring thread:
Code: 
++++
@1R37 6 1237  13478 5 1478  2347 2378 9 
 37 2359 4  36789 39 6789  23567 1 278 
 8 359 13579  134679 2 14679  3456 3567 47 
++++
@1G4R 7 158 @24G59 19 3  129 28 6 
 2 @3R4G 136  4679 8 4679  1379 37 5 
 9 358 13568  2567 16 2567  1237 4 1278 
++++
 46 @24R89 289  125689 7 125689  12456 256 3 
 3467 1 2379  23569 369 2569  8 2567 247 
 5 238 2378  12368 4 1268  1267 9 127 
++++

I start with normal Medusa coloring using RG in the 5 cells marked @. That's as far as it goes. Note the potential {37} and {46} locked sets in c1. They might be useful.
Next, I start marking inferred values. If "R" is true, then the <6> in r7c1 is true, so is marked "r". And, the <8> in r9c2 would also be true. [Edit note: This 8r in r9c2 does not appear to be justified, as noted in a subsequent post. It is not exploited what follows.] That's it for "r" values at this time.
If "G" is true, we can go quite a bit further. First those {37} and {46} locked sets in c1 would be true, so keep that in mind. But also, c5 would be fully determined. This is how it looks:
Code: 
++++
 1R37 6 1237  13478 5 1478  2347 2378 9 
 37 2359 4  36789 3g9 6789  23567 1 278 
 8 359 13579  134679 2 14679  3456 3567 47 
++++
 1G4R 7 158  24G59 19g 3  129 28 6 
 2 3R4G 136  4679 8 4679  1379 37 5 
 9 358 13568  2567 1g6 2567  1237 4 1278 
++++
 46r 24R89 289  125689 7 125689  12456 256 3 
 3467 1 2379  23569 36g9 2569  8 2567 247 
 5 238r 2378  12368 4 1268  1267 9 127 
++++

Recall that the "G is true" assumption meant that r8c1 is {46}. But, the "6g" in r8c5 means that r8c1 contains 4g. That leads to a "trap" of the <4> in r7c1 against the "4R" in r4c1:
Code: 
++++
 1R37 6 1237  13478 5 1478  2347 2378 9 
 37 2359 4  36789 3g9 6789  23567 1 278 
 8 359 13579  134679 2 14679  3456 3567 47 
++++
 1G4R 7 158  24G59 19g 3  129 28 6 
 2 3R4G 136  4679 8 4679  1379 37 5 
 9 358 13568  2567 1g6 2567  1237 4 1278 
++++
#46r 24R89 289  125689 7 125689  12456 256 3 
 34g67 1 2379  23569 36g9 2569  8 2567 247 
 5 238r 2378  12368 4 1268  1267 9 127 
++++

Now, there is a strong link on <4> in c1. So, the "4g" in r8c1 can be promoted to "4G" and the Medusa coloring expanded. Also, r4 can be fully determined for "g" values (which was true earlier but not needed then). This also determines "8g" in r2c9:
Code: 
++++
@1R37 6 1237  13478 5 1478  2347 2378 9 
 37 2359 4  36789 $3g9 6789  23567 1 $278g 
 8 359 13579  134679 2 14679  3456 3567 @4G7R 
++++
@1G4R 7 $15g8  24G59 $19g 3 $12g9 $28g 6 
 2 @3R4G 136  4679 8 4679  1379 37 5 
 9 358 13568  2567 $1g6 2567  1237 4 1278 
++++
 6 @24R89 289  12589 7 12589 @124G5 25 3 
@34G7 1 2379  23569 $36g9 2569  8 2567 @24R7 
 5 $238r 2378  12368 4 1268  1267 9 127 
++++

To help in spotting things quickly, I've marked the Medusa cells @ and the extended coloring cells $.
There are more eliminations. The <7> in r2c9 sees 8g in the same cell and 7R in r3c9 so is trapped. The next elimination is a bit tricker to see. The <7> in r3c3 sees 7R in r3c9. But, where is the green <7>? Well, remember that green {37} locked pair in r12c1? That does the trick! <7> is trapped in r3c3 and is eliminated.
If you'd like to see more examples, including a color "wrap", then you can try following the solution in this thread.
Last edited by Asellus on Sun Jan 20, 2008 3:05 am; edited 3 times in total 

Back to top 


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

Posted: Sun Jan 06, 2008 11:30 pm Post subject: 


After some discussion in that alternate thread, I realize that my "Rule (1)" is too restrictive: rg pairings are allowable for trapping as well; no exception is necessary. This is good news since it makes this coloring approach even easier and more powerful. Here is the restated rule:
(1) Redgreen "trap" eliminations are possible between any redgreen combination. In other words, RG (normal Medusa), rG, Rg and rg are all valid "traps."
Applying this in the example above allows progress to be made more easily. For instance:
Code: 
++++
 1R37 6 1237  13478 5 1478  2347 2378 9 
 37 2359 4  36789 3g9 6789  23567 1 278 
 8 359 13579  134679 2 14679  3456 3567 47 
++++
 1G4R 7 158  24G59 19g 3  129 28 6 
 2 3R4G 136  4679 8 4679  1379 37 5 
 9 358 13568  2567 1g6 2567  1237 4 1278 
++++
 46r 24R89 289 #125689 7 #125689  12456 256 3 
#3467 1 2379  23569 36g9 2569  8 2567 247 
 5 238r 2378  12368 4 1268  1267 9 127 
++++ 
The <6>s marked # are eliminated immediately, fixing <6> in r7c1 without the previous <4> trapping.
Another note: While I wanted to show how implied locked sets can be exploited in that last <7> elimination (in box 1 using the "g" {37} pair), it wasn't necessary to do it that way. The 3g in r2c5 produces 7g in r2c1, allowing the <7> elimination in r3c3 without recourse to the implied {37} pair. (This also results in 3g in r1c1, trapping the <7> in that cell and allowing more color "promotion".)
The coloring and eliminations continue beyond what I have shown. So, this can be used as a practice puzzle. In fact, a color "wrap" involving "g" occurs without very many more steps. (The <1>s in r6c59 both are colored "g".) This makes all the "R" and "r" values true and all the "G" values false. The "g" values are not determined and must be erased. (After that, an XWing and an XYWing can solve the puzzle.)
[Edit to clarify the wrap results in the last paragraph.]
Last edited by Asellus on Sun Jan 20, 2008 3:08 am; edited 1 time in total 

Back to top 


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

Posted: Tue Jan 08, 2008 10:01 am Post subject: 


Exploring this approach further, I finally found instances of something I suspected might be possible. It deserves being mentioned as a third "Rule":
(3) If an instance of a candidate digit is inferred to be both "r" and "g", then it must be true and can be placed immediately.
I will work of preparing an example to post. 

Back to top 


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

Posted: Wed Jan 09, 2008 8:06 am Post subject: 


More regarding "Rule 3":
In going back over possible examples, I discovered that any time I found a candidate digit that must be both "r" and "g" there was one (or more) "Trap" eliminations nearby that accomplished the same thing by eliminating the alternatives. So it seems that, technically, "Rule 3" isn't necessary. However, it makes a nice short cut "rule of thumb" in actual practice since one sometimes spots a "this must be both red and green" candidate before one spots the Traps that force it to be so. (Setting the "both red and green" candidate True eliminates the candidates that would otherwise be Trapped. So, it's two ways to see the same thing.)
[Edit to remove text that described something that is not logically possible and would indicate that one had made a coloring error.]
Meanwhile, I continue to play with this technique on very difficult puzzles and find that it has been able, so far, to solve them fairly easily. For instance, the 8Jan2008 Daily Nightmare at sudocue.net can be solved entirely in this way. Otherwise, the only "traditional" technique apparent is a very difficult to spot Sashimi XWing that accomplishes little. After that it seems you have no choice but to dig deep! Among possible "deep" tools, this extended approach to Medusa is able to solve it without too much difficulty.
Last edited by Asellus on Sun Jan 20, 2008 2:52 am; edited 1 time in total 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Tue Jan 15, 2008 8:53 pm Post subject: 


Asellus,
I want to see if I can tiptoe into this thing without having much of an understanding of AICs, ALSs, Eureka notation, etc. There have been a lot of posts with a lot of examples and I'm trying to see if I can distill this thing down to a manageable size. Here's what I think I know.
I think I'm reasonably proficient at regular Medusa, or what is often called 3D Medusa.
I think "trap" is another term for what I'd call an elimination from a pincer situation.
I think "wrap" is another term for what I'd call a contradiction, such as two candidates in the same house with the same color or two numbers in one cell with the same color.
I've got the three "rules" written down, although I'm not sure if more can be done with the inferences over and above what is specifically stated in the rules.
Once you assume R or G is true, you can extend either with small r's or g's indefinitely. You can never place another capital letter except under the regular Medusa rules. But I assume regular Medusa can be extended if made possible by eliminations/placements from the three rules. Then you could start in with new assumptions.
Quote:  I start with normal Medusa coloring using RG in the 5 cells marked @. That's as far as it goes. Note the potential {37} and {46} locked sets in c1. They might be useful.
Next, I start marking inferred values. If "R" is true, then the <6> in r7c1 is true, so is marked "r". And, the <8> in r9c2 would also be true. That's it for "r" values at this time.
If "G" is true, we can go quite a bit further. First those {37} and {46} locked sets in c1 would be true, so keep that in mind. But also, c5 would be fully determined. This is how it looks:
Code:
Code:  ++++
 1R37 6 1237  13478 5 1478  2347 2378 9 
 37 2359 4  36789 3g9 6789  23567 1 278 
 8 359 13579  134679 2 14679  3456 3567 47 
++++
 1G4R 7 158  24G59 19g 3  129 28 6 
 2 3R4G 136  4679 8 4679  1379 37 5 
 9 358 13568  2567 1g6 2567  1237 4 1278 
++++
 46r 24R89 289  125689 7 125689  12456 256 3 
 3467 1 2379  23569 36g9 2569  8 2567 247 
 5 238r 2378  12368 4 1268  1267 9 127 
++++ 

I guess I'm not seeing why r9c2 = 8 if R is true. I presume all four g's in column 5 are one chain based on the assumed truth of r4c1 = 1.
Are my assumptions OK? Is this skeletal knowledge enough put into actual use? 

Back to top 


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

Posted: Thu Jan 17, 2008 2:14 am Post subject: 


Marty,
I believe you've got it. As for that 8r in r9c2, I can no longer see how I came up with it. However, it isn't used in any of the subsequent steps I illustrated, so let's just pretend I didn't mark it! My apologies for the confusion.
The nice thing about this technique is that it requires no knowledge of AICs or Eureka notation. As for ALSs... they can come in handy in a couple of ways when extending a color. For instance, in the grid we are considering above the green <1> in r4c1 converts the {137} ALS in r12c1 into a green {37} locked pair, as mentioned. This would have rendered the <4> in the {347} cell r8c1 green if there hadn't been the strong link in c1 with that 4R.
Additionally, any ordinary elimination technique can be exploited in extending the coloring. For instance, assuming red to be true might create three "red" bivalue cells that form an XYWing that would eliminate a candidate somewhere and leave only one possibility for red in a victim cell (which could be marked "r"). These sorts of complex ways of extending a color are only needed in the most difficult puzzles, but are worth mentioning.
So, one might even be able to find, say, a colorinferred "xz" ALS that allows the extended coloring to extend further. (I'd be impressed by someone who posted an example of such a thing!) Or, maybe a "red UR" might do the trick. Or maybe something else. This is where this approach can get very powerful in those really supertough puzzles.
[Edit to correct "XWing" to "XYWing".]
Last edited by Asellus on Thu Jan 17, 2008 8:19 am; edited 1 time in total 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Thu Jan 17, 2008 4:59 am Post subject: 


A,
Thanks very much, your assistance is always appreciated. I'm hoping that maybe this technique will help me solve some of the puzzles that now force me into T&E. I'm wondering how to do the markings for Ext. Medusa. For the regular, a blank grid works fine, not sure if it'll work for this.
Thanks again. 

Back to top 


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

Posted: Thu Jan 17, 2008 8:34 am Post subject: 


In terms of P&P marking, that depends on how one does ones marking. The single digit grids, while very useful, don't help for Medusa. I usually use a dot grid within boxes for marks. This allows for some flexibility, but might seem obscure to many. For instance, a cell that has candidates {123679} would look like this:
Code: 
++
 . . . 
 . 
 . . 
++

Then, for R, one can use "^" in place of a dot. For G, use the inverse (there is no such character on the keyboard, but it is a pointy thing pointing down). For "r" and "g", the extended colors, rounded arcs up and down work. If one of these get promoted, then the rounded arc can be turned into a pointy thing.
If the dot approach is too obscure, then I would suggest using a large grid and putting the "pointy things" or the "roundy things" above or below the numbers. Alternately, one can use the G.E.M. approach, with double and single lines vs. double and single dots above numbers.
If this extended Medusa method weren't so useful, it definitely wouldn't be worth the trouble of such marking. But, it seems that it is. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Thu Jan 17, 2008 4:31 pm Post subject: 


It didn't take me long to figure out that the blank grid that works so well for chains and Medusa won't work, at least for me, for the extended version. I don't know yet if I can use my regular grid for markings and salvage it if things don't work out. It seems the ideal solution is an impractical one: take my grid to the library and make a copy. Oh well, I'm sure something will work as I think about it more. I don't think the dot thing would work for me. Maybe it will require making a second grid by hand, saving the trip to the library. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Thu Jan 17, 2008 10:20 pm Post subject: 


Update:
I either screwed up and got lucky or else this thing worked on the puzzle I was stuck on. And I was able to do it on the blank grid, although things weren't real complicated with large number of polyvalued cells.
I do have a couple of questions which I hope are quick and easy:
1) Can anything be done based on one number in one cell having both an upper and lower case letter? For example, suppose the cell is 5Gg6R. This phenomenon occurred three times very quickly.
2) Can an unlimited number of assumptions be made? If there are, say, eight Rs on the grid, can I start an assumption from each R such that the grid would be heavily populated with small r's? 

Back to top 


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

Posted: Thu Jan 17, 2008 10:45 pm Post subject: 


Quote:  there is no such character on the keyboard, but it is a pointy thing pointing down 
v, perhaps?
As my first choice, I use a solid dot and a small circle o, then I use x and +, then I use ^ and v.
I also have a set of Crayola erasable colored pencils.
Keith 

Back to top 


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

Posted: Fri Jan 18, 2008 1:28 am Post subject: 


Marty wrote:  I either screwed up and got lucky or else this thing worked on the puzzle I was stuck on. 
Congrats! I find that it works on almost all puzzles.
Now, those questions:
(1) There is no advantage to marking a G value g. However, if an elimination causes a g value to become conjugate with an R value, then the g value can be "promoted" to G. Since G is standard Medusa, the promotion may allow extension of the Medusa coloring to other uncolored digits.
(2) Yes, there is no limit on the inferences that can be used to place r and g values. "r" can be inferred from any other red value, R or r. And the same for g.
As for marking, I'd suggest using marks that can be "promoted" easily. For instance, if you marked r and g as "." and ":" next to the digit (as in GEM), and R and G as "" and "=", then it is easy to promote a "." to a "" or a ":" to a "=". 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Fri Jan 18, 2008 1:38 am Post subject: 


A,
Once again, thanks. I hope the pace of my questions will quickly decelerate. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Sun Jan 20, 2008 2:11 am Post subject: 


Quote:  (2) Samecolor "wrap" contradictions are valid in all cases. HOWEVER, only the original Medusa color is proved false; the inference colorings are not determined by a color "wrap". In other words, GG or Gg or gg for a single candidate in a single house is a "green wrap" and means that all "G" values are false and all "R" values true. But, it says nothing about the "r" and "g" values. 
Just a observation here: even though it says nothing about the "r" and "g" values, my (limited) experience says that when you can solve for all "R" and "G", the puzzle will be solved anyways.
And my question: in regular Medusa, two colors in one cell means the uncolored candidates can be zapped. What about in extended Medusa where one cell contains an upper and lower case? Such as: 347G9r? Or two lower case, such as: 347g9r?
Finally, can I assume a GG, Gg or gg in one cell is a wrap contradiction with the same implications as if they were a on single candidate in the same house, as described in Rule 2? 

Back to top 


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

Posted: Sun Jan 20, 2008 2:34 am Post subject: 


Marty wrote:  Just a observation here: even though it says nothing about the "r" and "g" values, my (limited) experience says that when you can solve for all "R" and "G", the puzzle will be solved anyways. 
Two things:
First, it's unfortunately not true that a wrap will always solve the puzzle. Sometimes, it doesn't.
Second, my rule about wraps is too strict. (I'll need to edit the first post to clarify.) If you get a "red" wrap with RR or Rr or rr in the same house or cell, then all R are false and all G and g are true. It is only r that we don't know anything about (so any of those marks remaining would have to be erased). Since g marks result from the assumption that G is true, once a wrap determines G to be true, g must be true as well.
Quote:  And my question: in regular Medusa, two colors in one cell means the uncolored candidates can be zapped. What about in extended Medusa where one cell contains an upper and lower case? Such as: 347G9r? Or two lower case, such as: 347g9r? 
Yes: all redgreen trapping possible in regular Medusa is possible in extended Medusa. And, the regular (RG) versus extended (rg) coloring does not matter for this purpose. Any redgreen combination can create a trap.
Quote:  Finally, can I assume a GG, Gg or gg in one cell is a wrap contradiction with the same implications as if they were a on single candidate in the same house, as described in Rule 2? 
Yes. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Sun Jan 20, 2008 4:52 am Post subject: 


Once again, thanks. I hope my questions are done, as I think I've covered the situations that I can anticipate. Having both forms of Medusa available to me is sort of empowering.
Would you be kind enough to also add a short reply when you edit the first post, since there is no other indication when an edit is made. 

Back to top 


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

Posted: Sun Jan 20, 2008 7:32 am Post subject: 


I think I've got it all correct now! Let's hope there's no more edits. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Wed Jan 30, 2008 7:08 pm Post subject: 


This is about "promoting" a candidate from lower to upper case. I had a cell that contained 2g7 as a result of the 2 being inferred from a previous move. I was thinking about promoting the 2 because the 2 was a strong link in its row. But I checked and that would've led to an invalid solution.
Can we say as a generalization that a promotion can occur only after a strong link opens up as a result of eliminating excess candidates in a house? 

Back to top 


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

Posted: Thu Jan 31, 2008 12:41 am Post subject: 


Marty R. wrote:  Can we say as a generalization that a promotion can occur only after a strong link opens up as a result of eliminating excess candidates in a house? 
Regarding promotions...
Generally, when a "g" results in Trap eliminations against an "R", the "g" then becomes a "G" since it is now strongly linked to the "R". The resulting G might then result in some additional R and G determinations.
This situation applies to cells as well as houses. An rG Trap within a cell then results in promotion of the "r" to "R". Such promotions within a cell are even more likely, I believe, to lead to additional RG determinations.
So, the elimination of excess candidates in a house or a cell can produce a color promotion. I don't know if this is the "only" way in which a promotion can occur. However, I can't think of another at the moment. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5542 Location: Rochester, NY, USA

Posted: Thu Jan 31, 2008 12:57 am Post subject: 


Once again, thank you sir. You'll note that I went 10 days without a question. I think I'm catching on!! 

Back to top 




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
