Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

New addition to multicoloring?

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Hafting

Joined: 19 Dec 2006
Posts: 12
:
Location: Trondheim

Items
PostPosted: Thu Jan 25, 2007 12:39 pm    Post subject: New addition to multicoloring? Reply with quote

I don't know if this is new, I just haven't seen it anywhere else.

An important part of multicoloring is to recognize interactions between different chains. I.e. when color "A" see color "B", then both can't be true, implying that at least one of their conjugates "a" and "b" must be true.

Now that is of course well known. Another coloring technique is to note that whan a color eliminates all candidates in a house, then that color must be false. And when it eliminates all but one, then that one candidate can be forced true by that color.

All this is stuff I have read about, and implemented. It also got me thinking - what if <i>two</i> colors together happens to eliminate all candidates in a house? Then those two colors can't both be true - just as if they see each other. Checking this for all houses and all combinations of colors not already seeing each other takes some time, but it solves more puzzles.

I haven't seen this particular technique described anywhere, so I post it in case it really is new.

Helge Hafting
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Jan 25, 2007 7:11 pm    Post subject: Reply with quote

You're in the territory of Grouped Turbot Chains with this technique.

In essence, your logic creates the following chain fragment:
Code:
a=A-(candidates seen by A)=(candidates seen by B)-B=b

a and b can be end nodes (eliminating common peers) or part of a larger Turbot Chain.

To look at this from the coloring perspective is new AFAIK.

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Thu Jan 25, 2007 7:55 pm    Post subject: Re: New addition to multicoloring? Reply with quote

Hafting wrote:
It also got me thinking - what if <i>two</i> colors together happens to eliminate all candidates in a house? Then those two colors can't both be true - just as if they see each other. Checking this for all houses and all combinations of colors not already seeing each other takes some time, but it solves more puzzles.

I haven't seen this particular technique described anywhere, so I post it in case it really is new.

You mean like this?
Code:

2.6953........2....8.....3......9......3..1...53.4..7.1.2........8.....1...4..65.

 2      17     6      | 9      5      3      | 478    148    478
 3479   1379   14579  | 1678   1678   2      | 579    169    5679
 79     8      1579   | 167    167    4      | 2579   3      25679
----------------------+----------------------+---------------------
 4678   127    147    | 25678  2678   9      | 23458  2468   234568
 46789  279    479    | 3      2678   5678   | 1      24689  245689
 689    5      3      | 1268   4      168    | 289    7      2689
----------------------+----------------------+---------------------
 1      46     2      | 5678   39     5678   | 34789  489    34789
 5      46     8      | 267    39     67     | 23479  249    1
 379    379    79     | 4      128    18     | 6      5      28


 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . | B2  . b2
---------+----------+----------
 .  2  . |  2  2  . |  2  2  2
 .  2  . |  .  2  . |  .  2  2
 .  .  . |  2  .  . |  2  .  2
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . | A2  .  . |  2  2  .
 .  .  . |  . a2  . |  .  . A2

 Color A true implies color B true, which implies no candidates in row 6

 Therefore color A is false
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Jan 26, 2007 12:15 am    Post subject: Reply with quote

rkral,

Your example (a nice Sashimi Swordfish) reminds me of the Unified Coloring Technique, which I think now goes by the name X-Colors. (I hope this is an accurate depiction. I'm rusty on this technique.)

Code:
B      G       g      g       G      g      G
[r9c5]=[r9c9]-([r6c9],[r3c9])=[r3c7]-[r6c7]=[r6c4] => -([r45c5],[r8c4])

 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . | G2  . g2
---------+----------+----------
 .  2  . |  2 -2  . |  2  2  2
 .  2  . |  . -2  . |  .  2  2
 .  .  . | G2  .  . | g2  . g2
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . | -2  .  . |  2  2  .
 .  .  . |  . B2  . |  .  . G2

BTW: I have no idea if this is similar to what Hafting is describing!
Back to top
View user's profile Send private message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Fri Jan 26, 2007 8:49 am    Post subject: Reply with quote

I think Hafting is approaching it from the other direction

Code:
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . | B2  . b2
---------+----------+----------
 .  2  . |  2  2  . |  2  2  2
 .  2  . |  .  2  . |  .  2  2
 .  .  . |  2  .  . |  2  .  2
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . | A2  .  . |  2  2  .
 .  .  . |  . a2  . |  .  . A2


Colors B and A eliminate all possibilities from row 6. Therefore colors A and B must exclude each other. Thus color a or b must be true which eliminates the 2 in r9c9. A very clever and satisfying way of looking at it.
_________________
Myth Jellies
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Fri Jan 26, 2007 4:22 pm    Post subject: Reply with quote

Myth Jellies wrote:
I think Hafting is approaching it from the other direction

(...)

Colors B and A eliminate all possibilities from row 6. Therefore colors A and B must exclude each other. Thus color a or b must be true which eliminates the 2 in r9c9. A very clever and satisfying way of looking at it.

I suspect you're correct. And that might mean that none of the A-a colored candidates need see any of the B-b colored candidates.
Back to top
View user's profile Send private message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Fri Jan 26, 2007 5:00 pm    Post subject: Reply with quote

Right.

Or, as Ruud put it...
Code:

 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . | B2  . b2
---------+----------+----------
 .  2  . |  2  2  . |  2  2  2
 .  2  . |  .  2  . |  .  2  2
 .  .  . | c2  .  . | C2  . c2
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . | A2  .  . |  2  2  .
 .  .  . |  . a2  . |  .  . A2 

b = B - C = c - A = a => b or a must be true
_________________
Myth Jellies
Back to top
View user's profile Send private message
dpbobelisk

Joined: 27 Apr 2006
Posts: 16
:
Location: Kettering,UK

Items
PostPosted: Sat Jan 27, 2007 10:37 am    Post subject: Reply with quote

The example posted by rkral is resolved if we use the "weak colouring" extension of simple colouring http://www.sudopedia.org/wiki/Weak_Colors.
I'm not sure if this will be true in every case with Hafting's new way of looking at things though. Some more examples would be useful.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku 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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron