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 

Simple coloring

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
Marty R.



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

PostPosted: Tue May 09, 2006 12:48 am    Post subject: Simple coloring Reply with quote

This was the April 27 "Nightmare." With about 75% of the cells solved, I did a coloring chain on "1", starting from r7c2. As you can see, the chain ended up with two "+" in r7. I didn't think this was possible and I double- and triple-checked the chain to make sure that it was composed only of strong links.

I thought this meant that my solution thus far contained an error and that I would end up with duplicates. But just for laughs, I figured with the signs reversed, there would be two "-" in r7, which meant that r7c3 had to be the cell containing the "1", and that finished off the puzzle with the correct solution.

So I either made an error in the chain, despite triple-checking, or I learned something new. Which was it? Could that be a vaild chain?

Code:
-------------------------
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
-------------------------
| . . . | . . . | . . . |
| + . . | . - . | . . . |
| . - . | + . . | . . . |
-------------------------
| . + . | . + . | . . . |
| . . . | . . . | . . . |
| . . . | - . . | . . . |
-------------------------
Back to top
View user's profile Send private message
keith



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

PostPosted: Tue May 09, 2006 1:44 am    Post subject: Of Course! Reply with quote

Marty,

Of course! If you have an x-y (any other notation) chain of strong links, and you find that "x" is a contradiction, then "y" must be the solution.

In your example, "+" is a contradiction, "-" must be the cells that have the value.

The reasons this is so powerful:

Chains of strong links (conjugate pairs) are easy to find.

They can lead to solution of the whole chain, not just elimination of a possibility at the ends.

They are the foundation of many other colorfully named techniques.

Best wishes,

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



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

PostPosted: Tue May 09, 2006 11:59 am    Post subject: It was a smart move Reply with quote

Marty R wrote:
... I either made an error in the chain, despite triple-checking, or I learned something new. Which was it? Could that be a vaild chain?

I think you learned something new, Marty. Good work!

Think of it this way. The chain can only exist in two possible states. If one of those is impossible because it embodies a contradiction, then the other state must be the correct one.
Code:
-------------------------
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
-------------------------
| . . . | . . . | . . . |
| + . . | . - . | . . . |
| . - . | + . . | . . . |
-------------------------
| . + . | . + . | . . . |
| . . . | . . . | . . . |
| . . . | - . . | . . . |
-------------------------

In your example, one might reason as follows:

-- If I enter a "1" at r5c1 or at at r6c4, I will be forced to enter two "1"s in row 7. That can't be right.

-- Therefore there must be a "1" at r5c5, at r9c4, and also at r6c2.

Here's a post from last October that contains several excellent examples of puzzles to which the "coloring" technique can be applied, just in case you want the practice. dcb

PS I remember one example that had a chain like yours -- but it was so long it allowed one to solve for all 9 "9"s at one fell swoop! I can't locate it right now ... will pass it along when I run across it again.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Tue May 09, 2006 3:58 pm    Post subject: Reply with quote

Thanks Keith and David. I was obviously under a bad assumption. Having read so much about how these chains are reversible from true-false to false-true, it didn't seem that an invalid chain could exist. Live and learn!
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Fri May 12, 2006 1:59 am    Post subject: Reply with quote

This has always been my favorite kind of colouring chain for two reasons: Instead of just an exclusion one makes an assignment and that placement happens to a cell in the chain, not one outside it. Maybe I like it because it doesn't seem to occur that often.

I don't remember exactly how I found out about this possible result of colouring but I don't think it was in any of the websites that explain techniques. Do any of them use a chain like this in their examples?
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