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   

XY-Wings and Coloring, could they be merged?

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Oct 21, 2005 1:16 am    Post subject: XY-Wings and Coloring, could they be merged? Reply with quote

I have been experimenting with the combination of different techniques, to see whether some of these combinations can yield a better result than the techniques separately.

Here is a case that might be useful:

When an XY-Wing is found, either the XZ or the YZ cell must contain the Z-digit. They could also both contain that digit.

In multicoloring, where 2 conjugate pairs (A-a) and (B-b) are found, and A shares a house with B, either a or b must contain the digit you are coloring. They could also both contain that digit.

Sounds familiar?

This lead me to explore the possibility to combine (under certain circumstances) these 2 techniques.

This is the part I'm pretty sure of:

Quote:
When A and B are the XZ and YZ cells of an XY-Wing, and A is part of a conjugate pair (A-a) for digit Z, and B is part of a conjugate pair (B-b) for digit Z, a and b can never both contain digit Z.


Would it be safe to draw the following conclusion?

Quote:
because a and b can never both be true, they are mutually exclusive for digit Z, so a!b.


Of course, the a!b is useless when these are the only 2 conjugate pairs for digit Z. Since I've implemented multicoloring, I see lots of chains that are missing that vital connection to do some serious damage. This addition might be the trigger you need to solve a hard Sudoku.

Some notes:

There are 2 ways to deal with the shared peers of the A and B cells. Either they are taken care of by the XY-Wing routine, or just leave them to be detected and cleared by the coloring routine.

Even a "clean" XY-Wing (where nothing can be eliminated) can still be used in coloring.

If my logic is flawed, please tell me ASAP, because I've already started coding this...

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

Items
PostPosted: Fri Oct 21, 2005 2:29 am    Post subject: Reply with quote

Programming did not take that long...

It works! Very Happy

Found out that one more condition is required: When the XZ and the YZ cells are already conjugates for color Z, it is useless to pass them to coloring. Should have known that.

I found a few Sudokus where this method finds a solution faster than with multicoloring alone.

Need to do some mass testing with/without to see if more Sudokus can be solved with this.

Ruud
Back to top
View user's profile Send private message Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Fri Oct 21, 2005 3:22 am    Post subject: Reply with quote

It's certainly valid logic, it's something that would happen automatically with "advanced colouring" (when colouring single pencilmarks instead of whole cells).
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Oct 21, 2005 11:17 am    Post subject: Reply with quote

Nick70 wrote:
It's certainly valid logic.

Thanks. I am pleased with this confirmation.

Nick70 wrote:
it's something that would happen automatically with "advanced colouring" (when colouring single pencilmarks instead of whole cells).

That is true for a lot of techniques that subsume the "lower" ones.
Programming advanced coloring is a bit more complicated than merging the results of 2 existing techniques, as I did in this case.

Next combination: Remote Locked Pairs & Coloring
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Fri Oct 21, 2005 2:56 pm    Post subject: Reply with quote

Remote pairs is a lot easier to combine with coloring, since regular coloring already covers that case. With remote pairs you're working with a chain of conjugates already, one that exists for both candidates of the pair.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Oct 21, 2005 4:13 pm    Post subject: Reply with quote

Lummox JR wrote:
Remote pairs is a lot easier to combine with coloring, since regular coloring already covers that case. With remote pairs you're working with a chain of conjugates already, one that exists for both candidates of the pair.

True. But that is also the downside. It means that I gain nothing except a little performance improvement.

Hmmm... What other options do we have?
Back to top
View user's profile Send private message Visit poster's website
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